LZW圧縮アルゴリズム

PHPによるLZW圧縮計算法

/**
* @link http://code.google.com/p/php-lzw/
* @author Jakub Vrana、http://php.vrana.cz/
* @copyright 2009 Jakub Vrana
* @license http: //www.apache.org/licenses/LICENSE-2.0 Apache ライセンス、バージョン 2.0
*/

/**LZW 圧縮
* @param 圧縮する文字列データ
* @return 文字列バイナリデータ
*/
function lzw_compress($string) {
 // 圧縮
 $dictionary = array_flip(range(" ", "xFF"));
 $word = "";
 $codes = array();
 for ($i=0; $i <= strlen($string); $i++) {
 $x = $string [$i];
 if (strlen($x) && isset($dictionary[$word . $x])) {
 $word .= $x;
 } elseif ($i) {
 $codes[] = $dictionary[$word];
 $dictionary[$word . $x] = count($dictionary);
 $word = $x;
 }
 }

 // コードをバイナリ文字列に変換します
 $dictionary_count = 256;
 $bits = 8; // ceil(log($dictionary_count, 2))
 $return = "";
 $rest = 0;
 $rest_length = 0;
 foreach ($codes as $code) {
 $rest = ($rest < < $bits) + $code;
 $rest_length += $bits;
 $dictionary_count++;
 if ($dictionary_count > (1 << $bits)) {
 $bits++;
 }
 while ($rest_length > 7) {
 $rest_length -= 8;
 $return .= chr($rest >> $rest_length);
 $rest &= (1 << $rest_length) - 1;
 }
 }
 $return を返します。 ($rest_length ? chr($rest << (8 - $rest_length)) : "");
}

/**LZW解凍
* @param文字列圧縮バイナリデータ
* @return文字列元データ
*/
function lzw_decompress($binary) {
 // バイナリ文字列を変換コードへ
 $dictionary_count = 256;
 $bits = 8; // ceil(log($dictionary_count, 2))
 $codes = array();
 $rest = 0;
 $rest_length = 0;
 for ($i=0; $i  $rest = ($rest << 8) + ord($binary[$i]);
 $rest_length += 8;
 if ($rest_length >= $bits) {
 $rest_length -= $bits;
 $codes[] = $rest >> $rest_length;
 $rest &= (1 << $rest_length) - 1;
 $dictionary_count++;
 if ($dictionary_count > (1 << $bits)) {
 $bits++;
 }
 }
 }

 // 解凍
 $dictionary = range(" ", "xFF");
 $return = "";
 foreach ($codes as $i => $code) {
 $element = $dictionary[ $code];
 if (!isset($element)) {
 $element = $word . $word[0];
 }
 $return .= $element;
 if ($i) {
 $dictionary[] = $word . $element[0];
 }
 $word = $element;
 }
 return $return;
}
$data = "";
$compressed = lzw_compress($data);
var_dump($data === lzw_decompress ($compressed));
?>