実際にハフマンコーディングテーブルはどのように構築されていますか？

Question

私の質問は具体的です。私は、ハフマン符号化の理論が理解しやすいことを見ることができます。しかし、通常はバイト境界に揃えないコードを作成するようです。この特定の問題を緩和する実際的な方法は、私がまだ出てきたチュートリアルで扱われていません。

二つの問題がある：ファイルがエンコードされたら

（1）、ファイルの結果のハフマンコードファイルの末尾がバイト境界で整列しなくてもよいが。圧縮ファイルでハフマン符号化データの終わりに達したことをどのようにして知ることができますか？

（2）圧縮解除に役立つように、ファイルにハフマンテーブルが含まれている場合、実際には、バイト境界との位置合わせに遭遇しないので、このようなテーブルはどのように作成されますか？シンボル自体は8ビットまたは16ビットです。しかしながら、ハフマン符号は、任意の数のビットとすることができる。コードあたりのハフマンコードを含めると、ハフマンテーブルをデコーダーが使用してバイナリツリーやその他のデータ構造を作成して解凍に役立てることができるように、ビット数を含める必要があります。

ハフマンとArithmaticコーディングは、多くの圧縮システムで使用されているように見えます。したがって、この問題は引き続きポップアップしています。

これはJPEGでどのように行われているかを理解しようとしており、Nios IIソフトコアプロセッサをFPGAで使用してCでエンコーダを構築し、カメラからSDカードにJPEGファイルを保存します。

Answer 1

1. 追加のシンボルは、終了コードとして定義されます。そのコードに遭遇すると、あなたはストリームの終わりに達しています。次のような別のビットストリームがない限り、通常行われる処理は、最後のバイトの残りのビットを破棄して次のバイト境界に移動することです。

2. コード記述を圧縮することの重要性に応じて、洗練さを変える方法はたくさんあります。 RFC 1951の収縮の説明は片方向に、brotliの説明はRFC 7932で読むことができます。どちらの場合も、コード自体は送信されません。代わりに、各記号のコード長さが送られ、コード自体は、長さと記号の順番から標準的に構築されます。収縮状態では、各記号に対して長さが送信され、コード化されていない記号については長さ0が送信されます。この一連の長さは、ランレングス符号化され、次にハフマン符号化される。 そのコード長をデコードするハフマンコードが最初に送信され、各長さ（3）の固定数のビットを使用して送信され、再び標準的に構築されます。 （Canonical Huffmanコードを調べる）JPEGには、あらかじめ定義されたハフマンコードを使用しないときにコード長をエンコードするもう1つの方法があります。