4

ハフマンコーディングの問題を解決しようとしていますが、常にコードワードの値が異なります (長さではなく値)。たとえば、文字「c」のコードワードが 100 の場合、私のソリューションでは 101 です。

以下に例を示します。

文字頻度コードワード my solution
   あ 22 00 10
   B 12 100 010
   C 24 01 11
   D 6 1010 0110
   E 27 11 00
   F 9 1011 0111

両方のソリューションのコードワードの長さは同じであり、別のコードワードのプレフィックスであるコードワードはありません。

これは私のソリューションを有効にしますか? または、最適なソリューションと最適なソリューションのビットを反転する2つのソリューションのみである必要がありますか?

4

2 に答える 2

5

その長さのセットに 0 と 1 を割り当てる方法は 96 通りあり、すべてが完全に有効で最適なプレフィックス コードになります。あなたはそれらのうちの2つを示しました。

あいまいさを解決する「正規の」ハフマン コードを定義する規則が存在します。標準コードを定義することの価値は、圧縮器から圧縮解除器へのコードの送信にあります。双方が 0 と 1 を明確に割り当てる方法を認識し、合意している限り、コード自体ではなく、各シンボルのコード長のみを送信する必要があります。

deflate 形式は、最短コードのゼロから始まり、増加します。各コード長内で、コードはシンボル値によって並べ替えられます。つまり、シンボルでソートされます。したがって、コードの正規のハフマン コードは次のようになります。

A - 00
C - 01
E - 10
B - 110
D - 1110
F - 1111

したがって、2 ビット コードはシンボルの順序 A、C、E で割り当てられ、同様に、4 ビット コードは D、F の順序で割り当てられます。短いコードは長いコードの前に割り当てられます。

コード長を見つける際に発生する、別の興味深いあいまいさがあります。等周波数ノードの組み合わせの順序に応じて、つまり、2 つ以上の最低周波数ノードを選択できる場合、実際には、正確に等しく最適な異なるコード長のセットになる可能性があります。コードの長さは異なりますが、長さに周波数を掛けて合計すると、2 つの異なるコードでまったく同じビット数が得られます。

ここでも、さまざまなコードがすべて最適であり、等しく有効です。結合するノードが選択されるときに、そのあいまいさを解決する方法もあります。この場合、ツリーの深さを最小限に抑えることができます。これにより、テーブル駆動型ハフマン デコードのテーブル サイズを減らすことができます。

たとえば、周波数 A: 2、B: 2、C: 1、D: 1 を考えます。最初に C と D を組み合わせて 2 を取得します。次に、A、B、および C+D をすべて周波数 2 で取得します。 A と B、または C+D を A または B と組み合わせることができます。これにより、2 つの異なるビット長のセットが得られます。A と B を組み合わせると、A-2、B-2、C-2、D-2 の長さになります。C+D と B を組み合わせると、A-1、B-2、C-3、D-3 になります。2x2 + 2x2 + 1x2 + 1x2 = 2x1 + 2x2 + 1x3 + 1x3 = 12 なので、どちらのコードも 12 ビットを使用してこれらのシンボルを何回も表現します。

于 2013-06-01T16:31:39.130 に答える