PHP实现Huffman编码/解码

不言

发布时间：2018-04-20 10:45:08

1940人浏览过

来源于php中文网

原创

这篇文章主要介绍了关于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 树的根节点

立即学习“PHP免费学习笔记（深入）”；

根据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);