Lzw算法实现php-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
    $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;
}

?>