LZWアルゴリズムPHP実現方法lzw_decompress php

LZWアルゴリズムの概要
文字列と符号化の対応関係は、圧縮中に動的に生成するものであり、圧縮データに隠されており、解凍時にテーブルに基づいて復元する、無損圧縮である.
Lempel-Ziv-Welch Encoding、略称LZWの圧縮アルゴリズムにより、いずれの言語でも実現する.
LZW圧縮アルゴリズム[1]の基本概念:LZW圧縮には、データストリーム(CharStream)、符号化ストリーム(CodeStream)、コンパイルテーブル(String Table)の3つの重要なオブジェクトがある.符号化時、データストリームは入力オブジェクト(テキストファイルのシーケンス)であり、符号化ストリームは出力オブジェクト(圧縮演算された符号化データ)である.復号時、符号化ストリームは入力オブジェクトであり、データストリームは出力オブジェクトである.コンパイルテーブルは,符号化と復号化の両方に利用しなければならないオブジェクトである.文字(Character):最も基本的なデータ要素であり、テキストファイルでは1バイトであり、ラスタデータでは指定された色リストのピクセルの色のインデックス値である.文字列(String):いくつかの連続した文字で構成されます.プレフィックス(Prefix):文字列でもありますが、通常は別の文字の前に使用され、その長さは0です.ルート(Root):長さの文字列.符号化(Code):固定長(符号化長)で符号化ストリームから取り出し、テーブルのマッピング値をコンパイルする数字.パターン:データストリームから不定長で読み出す文字列をコンパイルテーブルエントリにマッピングする.
 
LZW圧縮アルゴリズムの基本原理:元のテキストファイルデータの異なる文字を抽出し、これらの文字に基づいてコンパイルテーブルを作成し、コンパイルテーブルの文字のインデックスを元のテキストファイルデータの対応する文字の代わりに使用し、元のデータサイズを減少させる.パレット画像の実現原理との差は少ないように見えるが、ここでのコンパイルテーブルは事前に作成するのではなく、元のファイルデータに基づいて動的に作成され、復号時に符号化データから元のコンパイルテーブルを復元することに注意すべきである.
 
オリジナル:

<?php
/** 
* @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 License, Version 2.0
*/

/** LZW compression
* @param string data to compress
* @return string binary data
*/
function lzw_compress($string) {
	// compression
	$dictionary = array_flip(range("\0", "\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;
		}
	}
	
	// convert codes to binary string
	$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 $return . ($rest_length ? chr($rest << (8 - $rest_length)) : "");
}

/** LZW decompression
* @param string compressed binary data
* @return string original data
*/
function lzw_decompress($binary) {
	// convert binary string to codes
	$dictionary_count = 256;
	$bits = 8; // ceil(log($dictionary_count, 2))
	$codes = array();
	$rest = 0;
	$rest_length = 0;
	for ($i=0; $i < strlen($binary); $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++;
			}
		}
	}
	
	// decompression
	$dictionary = range("\0", "\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));

 
最適化:

<?php
function lzw_compress($string) {
    // compression
    $dict = array_flip(range("\\0", "\\xFF"));
    $dict_size = 256;
    $word = $string[0];
 
    $dict_count = 256;
    $bits = 8; 
    $bits_max = 256;
    $return = "";
    $rest = 0;
    $rest_length = 0;
 
    for ($i = 1, $j = strlen($string); $i < $j; $i++) {
        $x = $string[$i];
        $y = $word . $x;
        if (isset($dict[$y])) {
            $word .= $x;
        } else {
            $rest = ($rest << $bits) + $dict[$word];
            $rest_length += $bits;
            $dict_count++;
            if ($dict_count > $bits_max) {
                $bits_max = 1 << ++$bits;
            }
            while ($rest_length > 7) {
                $rest_length -= 8;
                $return .= chr($rest >> $rest_length);
                $rest &= (1 << $rest_length) - 1;
            }
            $dict[$y] = $dict_size++;
            $word = $x;
        }
    }
 
    $rest = ($rest << $bits) + $dict[$word];
    $rest_length += $bits;
    $dict_count++;
    if ($dict_count > $bits_max) {
        $bits_max = 1 << ++$bits;
    }
    while ($rest_length > 0) {
        if($rest_length>7){
            $rest_length -= 8;
            $return .= chr($rest >> $rest_length);
            $rest &= (1 << $rest_length) - 1;
        }else{
            $return .= chr($rest << (8 - $rest_length));
            $rest_length = 0;
        }
    }
 
    return $return;
}
 
/** LZW decompression
 * @param string compressed binary data
 * @return string original data
 */
function lzw_decompress($binary) {
    // convert binary string to codes
    $rest = 0;
    $rest_length = 0;
    $out_count = 257;
    $bits = 9;
    $bits_max = 512;
      
    // decompression
    $dict = range("\\0", "\\xFF");
    $w = $binary[0];
    $return = $w;
      
    for ($i = 1, $j = strlen($binary); $i < $j; $i++) {
        $rest = ($rest << 8) + ord($binary[$i]);
        $rest_length += 8;
        if ($rest_length >= $bits) {
            $rest_length -= $bits;
              
            // decompression
            $e = $dict[$rest >> $rest_length];
            if (!isset($e)) {
                $e = $w . $w[0];
            }
            $return .= $e;
            $dict[] = $w . $e[0];
            $w = $e;
            //--decompression
              
            $rest &= (1 << $rest_length) - 1;
            if (++$out_count > $bits_max) {
                $bits_max = 1 << ++$bits;
            }
        }
    }
      
    return $return;
}
 
?> 

 
項目:https://code.google.com/p/php-lzw/