PHP实现Huffman编码/解码的示例代码
|
Huffman 编码是一种数据压缩算法。我们常用的 zip 压缩，其焦点就是 Huffman 编码，尚有在 HTTP/2 中，Huffman 编码被用于 HTTP 头部的压缩。 本文就来用 PHP 来实践一下 Huffman 编码息争码。 1. 编码字数统计Huffman编码的第一步就是要统计文档中每个字符呈现的次数，PHP的内置函数 count_chars() 就可以做到： 结构Huffman树接下来按照统计功效结构Huffman树，结构要领在 Wikipedia 有具体的描写。这里用PHP写了一个浅显版的： $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 颠末计较之后，$root 就会指向 Huffman 树的根节点 按照Huffman树天生编码字典有了 Huffman 树，就可以天生用于编码的字典： 写文件运用字典将文件内容举办编码，并写入文件。将Huffman编码写入文件的有几个留意的处所： 将编码字典和编码内容一路写入文件后，就没法区分他们的界线了，因此必要在文件开始写入他们各自占用的字节数 PHP提供的 fwrite() 函数一次能写入 8-bit（一个字节）可能是 8的整数倍个bit。但Huffman编码中，一个字符也许只行使 1-bit 暗示，PHP不支持只往文件中写入 1-bit 这种操纵。以是必要我们自行对编码举办拼接，每凑齐 8-bit 才写入文件。
与第二条相同，最终形成的文件巨细必然是 8-bit 的整数倍。以是假如整个编码的巨细是 8001-bit的话，还要在末端补上 7个 0 // 写入编码的内容$buffer = ''; $i = 0; while (isset($input[$i])) { $buffer .= $dict[$input[$i]]; while (isset($buffer[7])) { $char = bindec(substr($buffer,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 在字典中刚巧是某个字符的编码时，就会造成错误的解码。 以是解码进程中，当已解码的字符数到达文档长度时，就要遏制解码。 // 读出字典长度和编码内容长度 $header = unpack('VdictLen/VcontentLen',$content); $dict = unserialize(substr($content,$header['dictLen'])); $dict = array_flip($dict); $bin = substr($content,8 + $header['dictLen']); 试验我们将Huffman编码Wiki页 的HTML代码生涯到当地，举办Huffman编码测试，试验功效：
空间节减了 33%，假如原文的一再内容较多，Huffman编码节减的空间可以到达 50% 以上. 除了文本内容，我们再实行将一个二进制文件举办Huffman编码，好比 f.lux的安装措施 ，试验功效如下：
编码后反而占用了更大的空间，一方面是因为我们存储字典时，并没有做特另外处理赏罚，占用了不少空间。另一方面，二进制文件中，各个字符呈现的概率相比拟力均匀，无法施展Huffman编码的上风。 以上就是本文的所有内容，但愿对各人的进修有所辅佐，也但愿各人多多支持编程之家。 （编辑：湖南网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
