0

私はハフマン アルゴリズムを介して圧縮の 2 つの異なるシナリオを手動で解決しようとしています。それぞれのシナリオで(symbol, frequency)、アイテムとしてタプルを含む順序付けられたキューから開始し、辞書を作成しようとします。

step 0:
[c:3] [b:4] [a:5]

step 1:
[a:5]    [7]
     [c:3] [b:4]

step 2:
     [12]
[a:5]    [7]
     [c:3] [b:4]

左が 0 で右が 1 であると考えると、辞書として次のようになります。

a -> 0
b -> 11
c -> 10

これまでのところ、すべてが正しく見えます。しかし、代わりに、最初のキューが次のようなものであると仮定しましょう。

step 0:
[c:1] [b:2] [a:4]

step 1:
    [3]      [a:4]
[c:1] [b:2]

step 2:
         [7]
    [3]      [a:4]
[c:1] [b:2]

次の辞書が得られます。

a -> 1
b -> 01
c -> 00

これは正しくないようです (aとの両方bが等しい)。

私は何を間違っていますか？ツリーのルートで枝の 1 つが実際に葉であるのを確認し、その方向を 1 の方向として選択することもできますifが、これは私にはきれいに見えません。私は何かが欠けているに違いないと思いますか？

4

2 に答える 2

2

ビットシーケンスが等しくありません。次のようなビット文字列がある場合：

01100

その後、「bac」としてのみ解凍できます。シーケンスの先行ゼロを保持する方法で圧縮結果を保存する必要があるため、たとえば、上記を01100000または00001100に埋め込んで出力のバイトを埋め、長さ5とともに保存することができます。もちろん問題はどちら側をパディングするかによって、出力の最初または最後のバイトのみが使用されます。

于 2012-06-19T04:58:34.100 に答える
1

重要なのは、辞書のビットのシーケンスがデコード時にあいまいさを引き起こしてはならないということです。シーケンスの値は重要ではありません。

あいまいさは、コーディングツリーのリーフのみがエンコードされる文字を保持できるという条件によって、ハフマンコーディングで解決されます。上記のツリーはこのルールに従っているため、結果のエンコーディングに問題はありません。

于 2012-06-19T04:56:51.387 に答える