Huffman 編碼是一種數(shù)據(jù)壓縮算法。我們常用的 zip 壓縮，其核心就是 Huffman 編碼，還有在 HTTP/2 中，Huffman 編碼被用于 HTTP 頭部的壓縮。
本文就來用 PHP 來實(shí)踐一下 Huffman 編碼和解碼。
1. 編碼
字?jǐn)?shù)統(tǒng)計(jì)
Huffman編碼的第一步就是要統(tǒng)計(jì)文檔中每個(gè)字符出現(xiàn)的次數(shù)，PHP的內(nèi)置函數(shù) count_chars() 就可以做到：
$input = file_get_contents('input.txt');
$stat = count_chars($input, 1);
構(gòu)造Huffman樹
接下來根據(jù)統(tǒng)計(jì)結(jié)果構(gòu)造Huffman樹，構(gòu)造方法在 Wikipedia 有詳細(xì)的描述。這里用PHP寫了一個(gè)簡易版的：
$huffmanTree = [];
foreach ($stat as $char => $count) {
$huffmanTree[] = [
'k' => chr($char),
'v' => $count,
'left' => null,
'right' => null,
];
}
// 構(gòu)造樹的層級(jí)關(guān)系，思想見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);
經(jīng)過計(jì)算之后，$root 就會(huì)指向 Huffman 樹的根節(jié)點(diǎn)
根據(jù)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);
寫文件
運(yùn)用字典將文件內(nèi)容進(jìn)行編碼，并寫入文件。將Huffman編碼寫入文件的有幾個(gè)注意的地方：
將編碼字典和編碼內(nèi)容一起寫入文件后，就沒法區(qū)分他們的邊界了，因此需要在文件開始寫入他們各自占用的字節(jié)數(shù)
PHP提供的 fwrite() 函數(shù)一次能寫入 8-bit（一個(gè)字節(jié)）或者是 8的整數(shù)倍個(gè)bit。但Huffman編碼中，一個(gè)字符可能只使用 1-bit 表示，PHP不支持只往文件中寫入 1-bit 這種操作。所以需要我們自行對(duì)編碼進(jìn)行拼接，每湊齊 8-bit 才寫入文件。
每湊齊8-bit才寫入
與第二條類似，最終形成的文件大小一定是 8-bit 的整數(shù)倍。所以如果整個(gè)編碼的大小是 8001-bit的話，還要在末尾補(bǔ)上 7個(gè) 0
$dictString = serialize($dict);
// 寫入字典和編碼各自占用的字節(jié)數(shù)
$header = pack('VV', strlen($dictString), strlen($input));
fwrite($outFile, $header);
// 寫入字典本身
fwrite($outFile, $dictString);
// 寫入編碼的內(nèi)容
$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++;
}
// 末尾的內(nèi)容如果沒有湊齊 8-bit，需要自行補(bǔ)齊
if (!empty($buffer)) {
$char = bindec(str_pad($buffer, 8, '0'));
fwrite($outFile, chr($char));
}
fclose($outFile);
解碼
Huffman編碼的解碼相對(duì)簡單：先讀取編碼字典，然后根據(jù)字典解碼出原始字符。
解碼過程有個(gè)問題需要注意：由于我們?cè)诰幋a過程中，在文件末尾補(bǔ)齊了幾個(gè)0-bit，如果這些 0-bit 在字典中恰巧是某個(gè)字符的編碼時(shí)，就會(huì)造成錯(cuò)誤的解碼。
所以解碼過程中，當(dāng)已解碼的字符數(shù)達(dá)到文檔長度時(shí)，就要停止解碼。
?php
$content = file_get_contents('a.out');
// 讀出字典長度和編碼內(nèi)容長度
$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，就去與字典比對(duì)是否能解碼出字符
$key .= $bits[$j];
if (isset($dict[$key])) {
$output .= $dict[$key];
$key = '';
$decodedLen++;
if ($decodedLen === $header['contentLen']) {
break;
}
}
}
$i++;
}
echo $output;
試驗(yàn)
我們將Huffman編碼Wiki頁 的HTML代碼保存到本地，進(jìn)行Huffman編碼測(cè)試，試驗(yàn)結(jié)果：
編碼前: 418,504 字節(jié)
編碼后: 280,127 字節(jié)
空間節(jié)省了 33%，如果原文的重復(fù)內(nèi)容較多，Huffman編碼節(jié)省的空間可以達(dá)到 50% 以上.
除了文本內(nèi)容，我們?cè)賴L試將一個(gè)二進(jìn)制文件進(jìn)行Huffman編碼，比如 f.lux的安裝程序 ，試驗(yàn)結(jié)果如下：
編碼前: 770,384 字節(jié)
編碼后: 773,076 字節(jié)
編碼后反而占用了更大的空間，一方面是由于我們存儲(chǔ)字典時(shí)，并沒有做額外的處理，占用了不少空間。另一方面，二進(jìn)制文件中，各個(gè)字符出現(xiàn)的概率相對(duì)比較平均，無法發(fā)揮Huffman編碼的優(yōu)勢(shì)。
以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
您可能感興趣的文章:- PHP 獲取視頻時(shí)長的實(shí)例代碼
- PHP多維數(shù)組指定多字段排序的示例代碼
- Php多進(jìn)程實(shí)現(xiàn)代碼
- PHP 計(jì)算兩個(gè)特別大的整數(shù)實(shí)例代碼
- PHP生成（支持多模板）二維碼海報(bào)代碼
- PHP實(shí)現(xiàn)數(shù)據(jù)庫的增刪查改功能及完整代碼
- php無限級(jí)評(píng)論嵌套實(shí)現(xiàn)代碼
- 如何避免PHP實(shí)例代碼中的一些壞代碼
