結果のアルファベットがバイナリではない状況で、ハフマン コーディング ツリーを簡単に一般化できますか? たとえば、あるテキストを 3 進数で書き出すことによって圧縮したい場合でも、書き出す文字ごとにプレフィックスのないコーディング システムを構築できます。ハフマン構成の単純な一般化 (二分木ではなく k 分木を使用) は、正しく効率的に機能するでしょうか? それとも、この構造は非常に非効率的なコーディング スキームにつながるのでしょうか?
7397 次
2 に答える
7
アルゴリズムは引き続き機能し、それでも単純です。実際、ウィキペディアには、元のハフマン論文をソースとして引用しているn-aryハフマンコーディングへの簡単な参照があります。
ただし、ハフマンが各シンボルに整数のビットを割り当てるためにわずかに最適ではないのと同じように（たとえば、算術符号化とは異なり）、3進数のハフマンは整数を割り当てる必要があるため、もう少し最適ではないはずです。トリットの。特に3つだけの場合は、目立たないものではありませんが、nを増やすと、n-aryHuffmanが他のコーディングアルゴリズムよりもさらに遅れることを示しています。
于 2011-03-27T21:27:52.530 に答える
4
経験的なテストとして、スクラブル タイルを配布するための 2 進および 3 進のハフマン ツリーを構築しました。
分布のエントロピーは、1 文字あたり 4.37 ビットを超えることはできないことを示しています。
二分ハフマン ツリーは、1 文字あたり平均 4.41 ビットを使用します。
三分ハフマン ツリーは、1 文字あたり平均 2.81 トリットを使用します。これは、1 文字あたり 4.45 ビットと同じ情報密度を持ちます。
于 2011-03-28T00:37:10.580 に答える