ハフマンエンコーディングとは何ですか? PHP でハフマンエンコーディングとデコーディングを実装する方法

ハフマン コーディングとは何ですか? ハフマン コーディングはデータ圧縮アルゴリズムです。一般的に使用される zip 圧縮の中核はハフマン エンコーディングであり、HTTP/ では、ハフマン エンコーディングは HTTP ヘッダーの圧縮に使用されます。この記事では、phpでのハフマンエンコードとデコードの実装方法を紹介します。

1. ハフマン エンコード

単語数

ハフマン エンコードの最初のステップは、ドキュメント内の各文字の出現数をカウントすることです。 PHP 組み込み関数 count_chars() でこれを行うことができます:

$input = file_get_contents('input.txt');
$stat = count_chars($input, 1);

ハフマン ツリーの構築

次に、統計結果に基づいてハフマン ツリーを構築します。ウィキペディアで。以下は 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[&#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 はハフマン ツリーのルート ノードを指します

ハフマン ツリーに基づいてコーディング辞書を生成します

はい ハフマン ツリーを使用すると、エンコード用の辞書を生成できます。

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

ファイルの書き込み

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

エンコーディング ディクショナリとエンコーディング コンテンツを一緒にファイルに書き込んだ後は、それらの境界を区別できないため、次の場所に書き込む必要があります。ファイルの先頭 占有バイト数

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

8 ビットが得られるたびに書き込みます

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

2. ハフマン エンコードのデコード

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

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

したがって、デコード プロセス中に、デコードされた文字の数がドキュメントの長さに達すると、デコードは停止します。

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

3. テスト

ハフマン コーディング Wiki ページの HTML コードをローカルに保存し、ハフマン コーディング テストを実施します。テスト結果は次のとおりです:

コーディング前: 418,504 バイト

エンコード後: 280,127 バイト

スペースが 33% 節約されます。元のテキストに繰り返しの内容が多くある場合、ハフマン エンコードによってスペースが節約されます。

テキスト コンテンツに加えて、f.lux インストール プログラムなどのバイナリ ファイルをハフマン エンコードしようとしました。テスト結果は次のとおりです:

エンコード前: 770,384 バイト

エンコード後: 773,076 バイト

エンコード後はさらに多くのスペースを必要としますが、これは辞書を格納する際に追加の処理を行わないためですが、それは多くのスペースを占めます。一方、バイナリファイルでは、各文字の出現確率が比較的均一であり、ハフマン符号化の利点を活かすことができません。

関連する推奨事項:

php は URL パラメーターをエンコード、デコード、解析します

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