0

文字列をエンコードするためにハフマン符号化アルゴリズムを読んでいます。キャラクターの頻度を考慮してツリーを作成していることがわかります。

度数分布表は次のとおりです。

a   b   d   e   f   h   i   k   n   o   r   s   t   u   v 
5   1   3   7   3   1   1   1   4   1   5   1   2   1   1   9

*space has frequency 9

これで作った木があるのがわかります。しかし、ツリーに要素を配置する方法のルールを導き出すことはできません。

この本は、頻度の高いすべての文字はルートの近くにあるべきだと言っています。ただし、3つ以上の文字が同じ頻度である場合は、ルートの異なる側にある必要があります。

問題は、どのようにポジションを決定するかということです。

私の本aにはコードがあり010、コードがあります。r011e100

誰か助けてもらえますか？

4

2 に答える 2

3

ウィキペディアを試しましたか？ハフマン符号化に関する素晴らしいデモンストレーションがあります。アルゴリズムは非常に単純です。優先キューが必要です。

アルゴリズムは次のようになります。

1. Create tree nodes with each character and their frequencies
2. Put all the letters and their frequencies in a priority queue Q
3. Do until Q contains only one element:
    3a. Pick two lowest-frequency items a, b
    3b. Create a tree node z with frequency(z) = frequency(a) + frequency(b)
    3c. Add a and b as left and right children of z
    3d. Put z in Q
4. Pick up the only element from Q. This would be the root of the tree.
5. Assign binary codes to each leaf node according to their root-to-leaf path.

優先度キューは、最小優先度キューとして設計する必要があります。つまり、頻度が最も低いノードが最初に出てくる必要があります。同頻度のアイテムを処理する場合は、タイブレーカーとして他の基準（アルファベット順など）を使用します。エンコードとデコードの両方のタイブレーク基準と一致している。

于 2012-05-23T16:29:49.823 に答える
2

ツリーを作成したら、道路の各分岐点にある2つのブランチに0と1を割り当てる方法を任意に選択できます。したがって、その割り当てを正規にする方法がなければ、各シンボルにビットを割り当てる方法に対する「正しい答え」はありません。たとえば、それはであるr必要があります011。 r任意の3ビット値にすることができます。（ただし、この周波数セットの長さは3ビットである必要があります。）

重要なのは、デコーダーがエンコーダーと同じ0と1の割り当てを取得することです。コードを直接送信することも、長さを送信して正規の方法で0と1を割り当てることもできます。例として、zip、gzip、pngなどで使用される圧縮アルゴリズムは、各シンボルのビット数のみを送信します。次に、最小の長さから始めて、その長さのすべてのシンボルに0から始まるコードが割り当てられます。シンボルには、表現整数でソートされたシンボルの順にコードが割り当てられます。例：ASCIIでソートされた文字の順序。次の長さでは、右側にビットが追加され、コードのカウントが続行されます。これにより、左から右にデコードする適切なプレフィックスコードが保証されます。

したがって、この場合、コードの長さは次のようになります。

2: _
3: a, e, r
4: d, f, n
5: b, h, t
6: i, k, o, s, u, v

したがって、次のようになります（各長さ内にアルファベット順に記号が表示されます）。

_: 00
a: 010
e: 011
r: 100
d: 1010
f: 1011
n: 1100
b: 11010
h: 11011
t: 11100
i: 111010
k: 111011
o: 111100
s: 111101
u: 111110
v: 111111

ここでのビット割り当ては、3つのシンボルのうちの2つについての本の内容とは異なります。他の完全に適切な正規プレフィックスコードの選択の例として、すべてのビットを反転することも、ビットの列のサブセットを反転することもできます。たとえば、最初の列全体を反転できます。各長さの記号の順序を変更できます。ビットの順序を逆にすることができます。実際、zipなどは上記のビットを逆の順序で格納するため、デコードは最下位ビットから最初に、つまり右から左に実行されます。

于 2012-05-23T20:24:03.443 に答える