PHP はハフマンエンコーディング/デコーディングを実装します-PHPチュートリアル-php.cn

PHP はハフマンエンコーディング/デコーディングを実装します

不言

リリース： 2023-03-24 13:14:01

オリジナル

1755 人が閲覧しました

この記事では、主に PHP でのハフマンエンコーディング/デコーディングの実装について紹介します。必要な友人はそれを参照してください。

ハフマンエンコーディングはデータ圧縮アルゴリズムです。一般的に使用される zip 圧縮の中核はハフマンエンコーディングであり、HTTP/2 では、ハフマンエンコーディングは HTTP ヘッダーの圧縮に使用されます。

この記事では、PHP を使用してハフマンエンコードとデコードを練習します。

1. エンコーディング

単語数

ハフマンエンコーディングの最初のステップは、PHP の組み込み関数 count_chars() を使用してこれを行うことです。 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()

$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);

ログイン後にコピー

ハフマン木を構築する

次に、統計結果に基づいてハフマン木を構築します。構築方法は Wikipedia に詳しく説明されています。以下は PHP で書かれた単純なバージョンです:

<?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;

ログイン後にコピー

計算後、$root はハフマンツリーのルートノードを指します

ハフマンを使用ツリー、エンコード用の辞書を生成できます:
rrreee

辞書を使用してファイルの内容をエンコードし、ファイルに書き込みます。ハフマンエンコーディングをファイルに書き込むときに注意すべき点がいくつかあります:

エンコーディング辞書とエンコーディングコンテンツを一緒にファイルに書き込んだ後は、それらの境界を区別することができないため、それらをファイルの先頭のバイト数

PHP が提供する `fwrite()` 関数は、一度に 8 ビット (1 バイト) または 8 ビットの整数倍を書き込むことができます。ただし、ハフマンエンコーディングでは、文字は 1 ビットのみで表現される可能性があり、PHP はファイルに 1 ビットのみを書き込む操作をサポートしていません。したがって、エンコーディングを自分で結合し、8 ビットが取得されるたびにのみファイルを書き込む必要があります。

2 番目の項目と同様に、最終的なファイルサイズは 8 ビットの整数倍でなければなりません。したがって、エンコード全体のサイズが 8001 ビットの場合、7 0

rrreee

デコード

ハフマンエンコードは比較的単純です。最初にエンコード辞書を読み取り、次に辞書に従って元の文字をデコードします。

デコードプロセスで注意する必要がある問題があります。エンコードプロセス中にファイルの最後にいくつかの 0 ビットを追加したため、これらの 0 ビットがたまたま特定のファイルのエンコードであった場合、辞書に文字が含まれていない場合、デコードエラーが発生します。

そのため、デコード処理中に、デコードされた文字数がドキュメントの長さに達すると、デコードは停止します。

rrreee

テスト

ハフマンエンコードWikiページのHTMLコードをローカルに保存し、ハフマンエンコードテストを実行しました。テスト結果:

エンコード前: 418,504バイト

エンコード後: 280,127バイト 🎜🎜🎜スペースの節約 33 %. 元のテキストに繰り返しのコンテンツが多く含まれる場合、ハフマンエンコードによって節約されるスペースは 50% 以上に達する可能性があります。🎜🎜 テキストコンテンツに加えて、f などのバイナリファイルもハフマンエンコードしようとします。 lux インストールプログラムのテスト結果は次のとおりです: 🎜🎜🎜エンコード前: 770,384 バイト 🎜🎜 エンコード後: 773,076 バイト 🎜🎜🎜 一方で、辞書を保存すると、より多くのスペースが必要になります。余分なスペースを必要としない追加の処理を行わないでください。一方、バイナリファイルでは、各文字の出現確率が比較的均一であり、ハフマン符号化の利点を活かすことができません。 🎜🎜関連する推奨事項: 🎜🎜🎜🎜PHP を使用して単一リンクリストを実装する🎜🎜

以上がPHP はハフマンエンコーディング/デコーディングを実装しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。