2

入力数字0または1に基づいて左または右に移動するよりも良い方法はありますか?

4

3 に答える 3

2

ハフマン ツリーの効率的なデコード アルゴリズムに関する論文がいくつかあります。個人的には、学術的な理由から、そのうちの 1 つしか使用していませんでしたが、それはずっと前のことです。論文のタイトルは、Hong-Chung Chen、Yue-Li Wang、Yu-Feng Lan による「A Memory Efficient and Fast Huffman Decoding Algorithm」でした。

アルゴリズムはO(log n)時間内に結果を返します。このアルゴリズムを使用するには、ツリー (葉) のすべてのシンボルを含むテーブルを作成する必要があり、シンボルごとに重みを指定する必要があります。

w(i) = 2 ^ (h - l)

ここで、h はハフマン ツリーの高さ、l はシンボルのレベル、およびカウントです。

count(i) = count(i-1) + w(i)

根の数 は、count(0)その重さに等しい。

これらがすべて揃っている場合、アルゴリズムには 3 つの簡単なステップがあり、それについては論文で説明されています。

これがあなたが探していたものかどうかはわかりません。

于 2010-01-31T05:47:24.170 に答える
1

はい、ルックアップ テーブルを使用できます。

これらのテーブルを格納するためにかなりの量のメモリを使用することに注意してください。また、そのテーブルをデータとともに出荷する (おそらく圧縮の効果を完全に無効にする) か、解凍する前にテーブルを作成する必要があります (これにより、一部が無効になる場合があります)。それによって得られるスピードアップのすべてではありません。)

テーブルがどのように機能するかを次に示します。

たとえば、圧縮データのサンプル部分のシンボルのビット シーケンスは次のとおりです。

1 -> A
01 -> B
00 -> C

ここで行うことは、次のようなエントリを含む、バイトでインデックス付けされたテーブルを作成することです (最初のシンボルをデコードするには、少なくとも 1 バイトを読み取る必要があるため)。

key      symbol       bit-shift
1xxxxxxx    A             7
01xxxxxx    B             6
00xxxxxx    C             6

x は、それらの x のすべての可能な組み合わせとそのデータを含むエントリを格納する必要があることを意味します。最初の行では、これは、上位ビット セットを持つすべてのバイト キーが A/7 にマップされるテーブルを作成することを意味します。

テーブルには 256 個のキー値すべてのエントリがあり、上記のルールに従って、その半分が A/7 にマップされ、25% が B/6 および C/6 にマップされます。

もちろん、シンボルの最長ビットシーケンスが 9 ～ 16 バイトの場合は、16 ビット整数をキーとするテーブルが必要です。

さて、デコードするときは、次のようにします。

read first and second byte as key, append them together

loop:
   look up the first 8 bits of the current key in the table
   emit symbol found in table
   shift the key bitwise to the left the number of bits specified in the table
   if less than 8 bits left in the key, get next byte and append to key

最後に 0 バイトをパディングするだけです。すべての Huffman 解凍と同様に、開始する前に発行するシンボルの数を知る必要があります。

于 2010-01-31T09:58:11.187 に答える
0

確かに、2 ツリーの代わりに k ツリーを使用して O(ln_k(n)) の高速化を得ることができます。たいしたことじゃない。

最大キー サイズが小さい場合 (たとえば < 8 ビット)、または大量のメモリがある場合は、単純なルックアップ テーブルを使用して O(1) を取得できます。

于 2010-01-31T09:34:52.497 に答える