Huffman 编码是一种数据压缩算法。我们常用的 zip 压缩,其核心就是 Huffman 编码,还有在 HTTP/2 中,Huffman 编码被用于 HTTP 头部的压缩。
本文就来用 PHP 来实践一下 Huffman 编码和解码。
1. 编码
字数统计
Huffman编码的第一步就是要统计文档中每个字符出现的次数,PHP的内置函数 count_chars() 就可以做到:
$input = file_get_contents('input.txt'); $stat = count_chars($input, 1);
构造Huffman树
接下来根据统计结果构造Huffman树,构造方法在 Wikipedia 有详细的描述。这里用PHP写了一个简易版的:
$huffmanTree = []; foreach ($stat as $char => $count) { $huffmanTree[] = [ 'k' => chr($char), 'v' => $count, 'left' => null, 'right' => null, ]; } // 构造树的层级关系,思想见wiki:https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81 $size = count($huffmanTree); for ($i = 0; $i !== $size - 1; $i++) { uasort($huffmanTree, function ($a, $b) { if ($a['v'] === $b['v']) { return 0; } return $a['v'] < $b['v'] "htmlcode">function buildDict($elem, $code = '', &$dict) { if (isset($elem['k'])) { $dict[$elem['k']] = $code; } else { buildDict($elem['left'], $code.'0', $dict); buildDict($elem['right'], $code.'1', $dict); } } $dict = []; buildDict($root, '', $dict);写文件
运用字典将文件内容进行编码,并写入文件。将Huffman编码写入文件的有几个注意的地方:
将编码字典和编码内容一起写入文件后,就没法区分他们的边界了,因此需要在文件开始写入他们各自占用的字节数
PHP提供的 fwrite() 函数一次能写入 8-bit(一个字节)或者是 8的整数倍个bit。但Huffman编码中,一个字符可能只使用 1-bit 表示,PHP不支持只往文件中写入 1-bit 这种操作。所以需要我们自行对编码进行拼接,每凑齐 8-bit 才写入文件。
每凑齐8-bit才写入
与第二条类似,最终形成的文件大小一定是 8-bit 的整数倍。所以如果整个编码的大小是 8001-bit的话,还要在末尾补上 7个 0
$dictString = serialize($dict); // 写入字典和编码各自占用的字节数 $header = pack('VV', strlen($dictString), strlen($input)); fwrite($outFile, $header); // 写入字典本身 fwrite($outFile, $dictString); // 写入编码的内容 $buffer = ''; $i = 0; while (isset($input[$i])) { $buffer .= $dict[$input[$i]]; while (isset($buffer[7])) { $char = bindec(substr($buffer, 0, 8)); fwrite($outFile, chr($char)); $buffer = substr($buffer, 8); } $i++; } // 末尾的内容如果没有凑齐 8-bit,需要自行补齐 if (!empty($buffer)) { $char = bindec(str_pad($buffer, 8, '0')); fwrite($outFile, chr($char)); } fclose($outFile);解码
Huffman编码的解码相对简单:先读取编码字典,然后根据字典解码出原始字符。
解码过程有个问题需要注意:由于我们在编码过程中,在文件末尾补齐了几个0-bit,如果这些 0-bit 在字典中恰巧是某个字符的编码时,就会造成错误的解码。
所以解码过程中,当已解码的字符数达到文档长度时,就要停止解码。
<"_blank" href="https://justgetflux.com/" rel="external nofollow" >f.lux的安装程序 ,试验结果如下:编码前: 770,384 字节
编码后: 773,076 字节
编码后反而占用了更大的空间,一方面是由于我们存储字典时,并没有做额外的处理,占用了不少空间。另一方面,二进制文件中,各个字符出现的概率相对比较平均,无法发挥Huffman编码的优势。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
P70系列延期,华为新旗舰将在下月发布
3月20日消息,近期博主@数码闲聊站 透露,原定三月份发布的华为新旗舰P70系列延期发布,预计4月份上市。
而博主@定焦数码 爆料,华为的P70系列在定位上已经超过了Mate60,成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢?
根据目前爆料的消息来看,华为P70系列将推出三个版本,其中P70和P70 Pro采用了三角形的摄像头模组设计,而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智,但辨识度绝对拉满。