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

每凑齐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编码，比如 ，试验结果如下：

编码前: 770,384 字节

编码后: 773,076 字节

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

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