ハフマンのアルゴリズムを使用してファイル圧縮を実装しましたが、問題は、圧縮ファイルの解凍、使用されるコーディング ツリー、またはコード自体もファイルに書き込む必要があることです。問題は次のとおりです。圧縮ファイルの先頭にコーディング ツリーを記述する最良の方法は何ですか?
3907 次
9 に答える
5
Basic Compression Library (BCL)には、ツリーをファイルに書き出す再帰関数を含む、かなり標準的なハフマン コーディングの実装があります。huffman.C を見てください。デコーダーが同じツリーを再構築できるように、葉を順番に書き出すだけです。
BCL には他にも非常に単純な圧縮アルゴリズムの要素が含まれているため、BCL も優れています。独自のアルゴリズムを展開する必要がある場合、これは非常に便利です。
于 2009-05-24T09:11:54.530 に答える
3
まず、標準の圧縮ストリーム (.net の GZipStream など) の使用を検討しましたか?
データを書き込む方法/場所については、シークを使用してストリームの位置を操作できます (そのようにスペースを予約することもできます)。ツリーのサイズが事前にわかっている場合は、その位置から書き始めることができます。ただし、実際のデータの後にコーディング ツリーを配置し、それがどこから始まるかを確認したい場合があります。つまり、前に少しスペースを確保し、圧縮データを書き込み、位置を記録し、ツリーを書き込み、前に移動して位置を書き出します。
于 2009-05-24T09:05:40.610 に答える
2
8 ビット シンボル (つまりバイト) で圧縮し、アルゴリズムが非適応的であると仮定すると、最も簡単な方法は、ツリーではなく値の分布を格納することです。たとえば、バイト 0 を見つけた頻度、バイト 1 を見つけた頻度、...、バイト 255 を見つけた頻度を保存することにより、ファイルを読み戻すときに、ツリーを再構築できます。これは最も単純な解決策ですが、最も多くのストレージ スペースが必要です (たとえば、大きなファイルをカバーするには、値ごとに 4 バイト、つまり 1kb が必要になります)。
ファイル内で各バイトが検出される頻度を正確に保存するのではなく、値を 0..255 (0 = 最小検出、...) に正規化することで、これを最適化できます。この場合、256 バイトを保存するだけで済みます。 . これらの値に基づいてツリーを再構築すると、同じツリーになります。(これは、Edmund および質問759707で指摘されているようには機能しません。質問に対するその他のリンクと回答については、そこを参照してください)
PS: Henk が言ったように、seek() を使用すると、後で値を格納するためにファイルの先頭にスペースを確保できます。
于 2009-05-24T09:13:44.947 に答える
2
ほとんどの実装では、正規のハフマン エンコーディングが使用されています。シンボルの長さをコンパクトな方法で保存するだけで済みます。実装の階層: shcodec。もう 1 つの方法は、半静的なハフマン エンコーディング (定期的な再スケーリング) を使用することです。この場合、ツリーを保存する必要はありません。
于 2009-06-14T19:53:00.897 に答える
1
最も素朴な解決策は、圧縮ツリーを事前順に解析し、ファイルのヘッダーに 256 個の値を書き込むことです。
于 2009-05-24T09:13:28.740 に答える
1
ハフマン ツリーのすべてのノードは、2 つの子を持つブランチまたはリーフであるため、単一ビットを使用して各ノードを明確に表すことができます。リーフの場合、そのノードの 8 ビットがすぐに続きます。
たとえば、このツリーの場合:
/\
/\ A
B /\
C D
001[B]01[C]1[D]1[A]を保存できます
(これは、以前に投稿された huffman.c の例とまったく同じであることがわかりましたが、上記で説明した方法とは異なります)。
于 2009-05-24T09:28:20.597 に答える
1
コード ツリーをファイルに書き込む代わりに、各文字が見つかった頻度を書き込んで、解凍プログラムが同じツリーを生成できるようにします。
于 2009-05-24T09:07:58.873 に答える
0
適応ハフマン符号化を試しましたか? 一見したところ、ツリーを送信する必要はまったくないように見えますが、トレスを最適化して同期するためにさらに作業が必要です。
于 2011-12-07T17:19:07.943 に答える
0
文字の頻度を送信し、受信側でツリーを構築することをお勧めします。このデータは、固定アルファベットの一定サイズになります。これはシリアル化可能で、ファイルに入れる必要があると思います。ツリーの送信はその実装に依存します。私が試したところ、配列ベースのアプローチでは、ほとんどの場合、ツリーがバランスのとれたツリーではない可能性があるため、ツリーに未使用のメモリが残ります。ツリーのバランスがとれていれば、配列表現が最適なオプションを生成していたでしょう。
于 2011-12-07T17:07:00.400 に答える