file - ハフマンツリーをエンコードされたビットストリームと一緒にファイルとして保存する基本的な手法は何ですか？

Question

ハフマンエンコードされたビットストリームをバイナリファイルとして保存するにはどうすればよいですか？

Answer 1

エンコーディングを保存するには、次の3つが必要です。

1. 各文字をビットパターンにマッピングするエンコーディングツリーを再構築する方法。
2. ストリームの実際のエンコーディング。
3. エンコードされたデータの終わりを検出する何らかの方法。

これらの問題のそれぞれを解決する方法はたくさんあります。各文字のビットパターンをテーブルに明示的に格納することも、圧縮するすべてのストリームに同じエンコーディングテーブルを使用することもできます。ストリームの終わりを検出する方法に関しては、1つのオプションは、疑似EOF文字を使用してこのストリームを終了することです。これを行うには、ハフマンエンコーディングツリーを構築するときに、ストリームの終わりを示す番兵として機能する多重度を持つ新しいキャラクターを追加します。結果を書き込むときは、最後にこの文字を書き込んで、バイトに完全に収まるビット数を使用していなくても、ストリームがどこで終了するかがわかるようにします。

実際のコンテンツを保存するには、エンコードされた表現をビットベクトルにバッファリングして、8ビットの倍数でファイルストリームに自動的にフラッシュすることをお勧めします。もちろん、これを行う唯一の方法ではないので、最も効果的な方法を選択してください。