1. 云栖社区>
  2. PHP教程>
  3. 正文

Lzw算法实现php-lzw优化版

作者:用户 来源:互联网 时间:2017-12-01 18:49:34

php算法优化实现LZW

Lzw算法实现php-lzw优化版 - 摘要: 本文讲的是Lzw算法实现php-lzw优化版, /**  * @link http://code.google.com/p/php-lzw/  * @author Jakub Vrana, http://php.vrana.cz/  * @copyright 2009 Jakub


/**  * @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算法php实现的原版,发现有很多可以优化的地方,于是改写了这个优化版,粗测压缩效率提升30%,解压缩效率提升15%(1.2M文本)。 2013年2月16日 13:48:37 修正一个小bug,原061行和062行对调,不然会导致最后一个解压缩错误。代码已修正。

<?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("","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("","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;
}
?>

以上是云栖社区小编为您精心准备的的内容,在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索php , 算法 , 优化 , 实现 LZW ,以便于您获取更多的相关知识。