0

Lossless 圧縮のための Huffman Coding について本当に助けが必要です。試験が迫っていて、これを理解する必要があります。これを理解するために作成された簡単なチュートリアルを知っている人はいますか、誰かが説明してくれますか?

試験の質問は次のようになります。

アルファベットが [A, B, C] で、既知の確率分布が P(A)=0.6、P(B)=0.2、P(C)=0.2 であるとします。簡単にするために、エンコーダーとデコーダーの両方が、メッセージの長さが常に 3 であることを認識していると仮定して、ターミネーターは必要ありません。

  1. メッセージ ACB をハフマン コーディングでエンコードするには、何ビットが必要ですか? シンボルごとにハフマン ツリーとハフマン コードを提供する必要があります。(3 点)

  2. 算術符号化でメッセージ ACB をエンコードするには、何ビットが必要ですか? エンコード プロセスの詳細を提供する必要があります。(3 点)

  3. 上記の結果を使用して、ハフマン符号化に対する算術符号化の利点について説明します。(1 点)

答え:

  1. ハフマンコード：A-1、B-01、C-00。エンコード結果は10001なので5ビット必要。(3 点)

  2. 算術符号化のエンコード プロセス: シンボル 低高範囲 0.0 1.0 1.0 A 0.0 0.6 0.6 C 0.48 0.6 0.12 B 0.552 0.576 0.024 最終的なバイナリ コードワードは 0.1001、つまり 0.5625 です。したがって、4 ビットが必要です。(3 点)

  3. ハフマン符号化では、各シンボルの符号語の長さは整数でなければなりません。しかし、算術符号化では分数になる可能性があります。したがって、上に示した結果のように、算術符号化は多くの場合、ハフマン符号化よりも効率的です。(1 点)

4

3 に答える 3

2

http://en.wikipedia.org/wiki/Huffman_coding

ツリー (右上) を見ると、各親ノードがその下の 2 つのノードの合計であることがわかります。ノードの値は文字の頻度です。バイナリ シーケンスの各ビットは、ツリーの右/左ブランチです。

それは役に立ちますか？

算術コーディングについてはよくわかりませんが、かなり賢いようです。

于 2011-04-15T15:01:39.240 に答える
1

ハフマン ツリーは、ルート付近で圧縮されたストリーム内の最高の分布を持つ値を表すノードと、ルートから遠ざかるにつれて分布が減少する値を表すノードを持つバイナリ ツリーです。したがって、より一般的な値をより短いビットでエンコードできます一般的でない値は長い文字列にエンコードされます。

ハフマン木は次のように構築されます。

  1. ソース ストリーム内のエンティティのテーブルを、それらの分布とともに作成します。
  2. 分布が最も低いテーブル内の 2 つのエントリを選択します。
  3. これら 2 つのエントリからツリー ノードを作成します。
  4. 使用したばかりのエントリをテーブルから削除します。
  5. 削除したばかりのノードとツリー ノードの組み合わせ分布を使用して、テーブルに新しいエントリを追加します。
  6. テーブルに複数のエントリが残っている場合は、ステップ 2 に進みます。
  7. テーブルに残っているエントリがルートです。
于 2011-12-07T17:43:33.357 に答える
0

基本的なハフマンの実装はまったく問題ありません。ただし、ゼロから構築する場合は、minHeap やビット ベクトルなどの作業を容易にするために、ツールボックスに複数の他のデータ構造が必要になる場合があります。エンコードとデコードの基本的なアルゴリズムは非常に単純です。算術符号化との比較に関する情報はありません。

実装例

于 2011-12-07T17:16:01.893 に答える