5

私はインターネット上の記事を読み、ルートからトラバースすることによるデコードの自然な方法を知っていますが、ルックアップテーブルを使用してより速くそれを実行したいと思います。

読んだ後もまだポイントが取れません。

元：

入力： "abcdaabaaabaaa"
コードデータ
0 a
10 b
110 c
111日

記事によると、可変長のため、最大コード長の文字列を少し取って長さを決定し、それをインデックスとして使用します。 

出力： "010110111001000010000"
インデックスインデックス（バイナリ）コードビットが必要
0 000 a 1
1 001 a 1
2 010 a 1
3 011 a 1
4100 b 2
5101 b 2
6110 c 3
7111 d 3

私の質問は次のとおりです。

  1. それはどういう意味due to variable length, it determine the length by taking a bit of string of max code lengthですか？長さを決定する方法は？

  2. ルックアップテーブルを生成する方法とその使用方法は？背後にあるアルゴリズムは何ですか？

4

1 に答える 1

6

たとえば、最大コード長は3ビットです。したがって、ストリーム（010）から最初の3ビットを取得し、それを使用してテーブルにインデックスを付けます。これにより、コード'a'およびビット=1が得られます。入力ストリームから1ビットを消費し、コードを出力して続行します。2回目の移動で、（101）が得られます。これは、「b」および2ビットなどとしてインデックス付けされます。

テーブルを作成するには、テーブルを1 << max_code_lengthの大きさにし、インデックスをハフマンコードとしてデコードするかのように詳細を入力します。あなたの例を見ると、「0」で始まるすべてのインデックスはaであり、「10」で始まるインデックスはbです。

于 2012-12-10T16:13:46.060 に答える