PHP でのハフマンエンコード/デコード手順の詳細な説明-PHPチュートリアル-php.cn

PHP でのハフマンエンコード/デコード手順の詳細な説明

php中世界最好的语言

リリース： 2023-03-26 06:18:01

オリジナル

2065 人が閲覧しました

今回は、PHP でハフマンエンコード/デコードを実装する手順について詳しく説明します。PHP でハフマンエンコード/デコードを実装する際の注意点とは何ですか。実際のケースを見てみましょう。

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

1. エンコード

単語数

ハフマンエンコードの最初のステップは、PHP の

組み込み関数 count_chars() でこれを行うことができます。 :

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

ログイン後にコピー

ハフマン木を構築する

次に、統計結果に基づいてハフマン木を構築します。

構築方法は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 はハフマンツリーのルートノードを指します

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

ハフマンツリーを使用すると、次のことができます。コーディング辞書辞書:

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

ログイン後にコピー

ファイルの書き込み

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

エンコーディングディクショナリとエンコーディングコンテンツを一緒にファイルに書き込んだ後、それらの境界を区別することは不可能なので、それらが占めるバイトを最初に書き込む必要があります。 PHP が提供する fwrite() 関数は、一度に 8 ビット (1 バイト) または 8 ビットの整数倍を書き込むことができます。ただし、ハフマンエンコーディングでは、文字は 1 ビットのみで表現される可能性があり、PHP はファイルに 1 ビットのみを書き込む操作をサポートしていません。したがって、エンコーディングを自分で結合し、8 ビットが取得されるたびにのみファイルを書き込む必要があります。

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

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

ログイン後にコピー

デコード

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

デコードプロセスで注意する必要がある問題があります。エンコードプロセス中にファイルの最後にいくつかの 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;

ログイン後にコピー

テスト

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

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