PHP實作Huffman編碼/解碼-php教程-PHP中文網

PHP實作Huffman編碼/解碼

不言

發布： 2023-03-24 13:14:01

原創

1800 人瀏覽過

這篇文章主要介紹了關於PHP實作Huffman編碼/解碼，有著一定的參考價值，現在分享給大家，有需要的朋友可以參考一下

Huffman 編碼是一種資料壓縮演算法。我們常用的 zip 壓縮，其核心就是 Huffman 編碼，還有在 HTTP/2 中，Huffman 編碼被用於 HTTP 頭部的壓縮。

本文就來用 PHP 來實作 Huffman 程式碼和解碼。

1. 編碼

字數統計

Huffman編碼的第一步就是要統計文件中每個字元出現的次數，PHP的內建函數count_chars( ) 就可以做到：

$input = file_get_contents(&#39;input.txt&#39;);$stat = count_chars($input, 1);

登入後複製

建構Huffman樹

接下來根據統計結果建構Huffman樹，建構方法在Wikipedia 有詳細的描述。這裡用PHP寫了一個簡易版的：

$huffmanTree = [];foreach ($stat as $char => $count) {    $huffmanTree[] = [        &#39;k&#39; => chr($char),        &#39;v&#39; => $count,        &#39;left&#39; => null,        &#39;right&#39; => 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[&#39;v&#39;] === $b[&#39;v&#39;]) {            return 0;
        }        return $a[&#39;v&#39;] < $b[&#39;v&#39;] ? -1 : 1;
    });    $a = array_shift($huffmanTree);    $b = array_shift($huffmanTree);    $huffmanTree[] = [        &#39;v&#39; => $a[&#39;v&#39;] + $b[&#39;v&#39;],        &#39;left&#39; => $b,        &#39;right&#39; => $a,
    ];
}$root = current($huffmanTree);

登入後複製

經過計算之後，$root 就會指向Huffman 樹的根節點

根據Huffman樹產生編碼字典

有了Huffman 樹，就可以產生用於編碼的字典：

function buildDict($elem, $code = &#39;&#39;, &$dict) {
    if (isset($elem[&#39;k&#39;])) {        $dict[$elem[&#39;k&#39;]] = $code;
    } else {
        buildDict($elem[&#39;left&#39;], $code.&#39;0&#39;, $dict);
        buildDict($elem[&#39;right&#39;], $code.&#39;1&#39;, $dict);
    }
}$dict = [];
buildDict($root, &#39;&#39;, $dict);

登入後複製

寫入檔案

運用字典將檔案內容編碼，並寫入檔案。將Huffman編碼寫入檔案的有幾個注意的地方：

將編碼字典和編碼內容一起寫入檔案後，就沒法區分他們的邊界了，因此需要在檔案開始寫入他們各自佔用的位元組數
PHP提供的fwrite() 函數一次能寫入8-bit（一個位元組）或是8的整數倍個bit。但Huffman編碼中，一個字元可能只用 1-bit 表示，PHP不支援只往檔案中寫入 1-bit 這種操作。所以需要我們自行對編碼進行拼接，每湊齊 8-bit 才會寫入檔案。

PHP實作Huffman編碼/解碼

與第二條類似，最終形成的檔案大小一定是 8-bit 的整數倍。所以如果整個編碼的大小是8001-bit的話，還要在末尾補上7個0

$dictString = serialize($dict);// 写入字典和编码各自占用的字节数$header = pack(&#39;VV&#39;, strlen($dictString), strlen($input));
fwrite($outFile, $header);// 写入字典本身fwrite($outFile, $dictString);// 写入编码的内容$buffer = &#39;&#39;;$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, &#39;0&#39;));
    fwrite($outFile, chr($char));
}
fclose($outFile);

登入後複製

解碼

Huffman編碼的解碼相對簡單：先讀取編碼字典，然後根據字典解碼出原始字元。

解碼過程有個問題要注意：由於我們在編碼過程中，在檔案結尾補齊了幾個0-bit，如果這些0-bit 在字典中剛好是某個字元的編碼時，就會造成錯誤的解碼。

所以解碼過程中，當已解碼的字元數達到文件長度時，就要停止解碼。

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

登入後複製