个人中心
gpt4 book ai didi

PHP实现Huffman编码/解码的示例代码

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 26 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章PHP实现Huffman编码/解码的示例代码由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

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'] ? -1 : 1;  });  $a = array_shift($huffmanTree);  $b = array_shift($huffmanTree);  $huffmanTree[] = [    'v' => $a['v'] + $b['v'],    'left' => $b,    'right' => $a,  ];}$root = current($huffmanTree);

经过计算之后，$root 就会指向 Huffman 树的根节点 。

根据Huffman树生成编码字典 。

有了 Huffman 树，就可以生成用于编码的字典:

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 才写入文件.

PHP实现Huffman编码/解码的示例代码

每凑齐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 在字典中恰巧是某个字符的编码时，就会造成错误的解码.

所以解码过程中，当已解码的字符数达到文档长度时，就要停止解码.

<?php$content = file_get_contents('a.out');// 读出字典长度和编码内容长度$header = unpack('VdictLen/VcontentLen', $content);$dict = unserialize(substr($content, 8, $header['dictLen']));$dict = array_flip($dict);$bin = substr($content, 8 + $header['dictLen']);$output = '';$key = '';$decodedLen = 0;$i = 0;while (isset($bin[$i]) && $decodedLen !== $header['contentLen']) {  $bits = decbin(ord($bin[$i]));  $bits = str_pad($bits, 8, '0', STR_PAD_LEFT);  for ($j = 0; $j !== 8; $j++) {    // 每拼接上 1-bit，就去与字典比对是否能解码出字符    $key .= $bits[$j];    if (isset($dict[$key])) {      $output .= $dict[$key];      $key = '';      $decodedLen++;      if ($decodedLen === $header['contentLen']) {        break;      }    }  }  $i++;}echo $output;

试验 。

我们将Huffman编码Wiki页 的HTML代码保存到本地，进行Huffman编码测试，试验结果:

编码前: 418,504 字节 。

编码后: 280,127 字节 。

空间节省了 33%，如果原文的重复内容较多，Huffman编码节省的空间可以达到 50% 以上. 。

除了文本内容，我们再尝试将一个二进制文件进行Huffman编码，比如 f.lux的安装程序 ，试验结果如下:

编码前: 770,384 字节 。

编码后: 773,076 字节 。

编码后反而占用了更大的空间，一方面是由于我们存储字典时，并没有做额外的处理，占用了不少空间。另一方面，二进制文件中，各个字符出现的概率相对比较平均，无法发挥Huffman编码的优势.

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我.

最后此篇关于PHP实现Huffman编码/解码的示例代码的文章就讲到这里了,如果你想了解更多关于PHP实现Huffman编码/解码的示例代码的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

26 4 0
文章推荐： PHP排序算法之简单选择排序(Simple Selection Sort)实例分析
文章推荐： PHP排序算法之直接插入排序(Straight Insertion Sort)实例分析
文章推荐： PHP排序算法之堆排序(Heap Sort)实例详解
文章推荐： PHP排序算法之基数排序(Radix Sort)实例详解
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com