1

解凍のためのハフマンコーディングでは、ビットストリームをいくつかの値と比較する必要があります（プレフィックスなし）。私はPythonでハフマンコーダーデコーダーを実装しようとしています。これはビットストリームをASCII値に変換するための私のコードです。

c = ''
l = 0
x = 1
stime = time.time()
while l<len(string):
    if string[l:l+x] in table:
        c+=table[string[l:l+x]]
        l+=x
        x = 1
    else:
        x+=1

このループをより効率的にするために何ができますか？

4

2 に答える 2

1

一度に1バイトずつビットストリームを処理し、入力ストリームをシフトまたはマスクする必要がないようにテーブルのセットを構築できるため、テーブル構築により多くの時間を費やす準備ができている場合は、デコードを高速化できます。個々のビットを選択します。

バイトストリームのデコードが次のようになるようなテーブルのセットを作成する必要があります。

state = 0
for (input in inputBytes)
  output += outputTable[state][input]
  state = stateTable[state][input]

ここでの出力は、ASCII値の可変長文字列になります。状態は、まだ出力データになっていない前の1つまたは複数のバイトからのすべての情報を記憶する必要があります。これらのテーブルを作成する1つの方法は、状態0を初期状態にすることです。入力データの最初のバイトを読み取ろうとしているときです。次に、バイトごとに、可能な限りデコードし、それを使用してoutputTable[0][byte]を生成します。次に、バイトの最後にある未使用ビットのすべての文字列を確認します。これらの文字列ごとに、新しい状態を割り当てる必要があります。また、可能なすべてのバイトについて、これらの状態ごとに同じ種類のテーブル作成を行う必要があります。これを行うと、デコード後に未使用のビットの文字列も作成されます。これらがすでに状態を割り当てているビット文字列である場合は、それらを無視して続行できます。そうでない場合は、より多くの状態を割り当てる必要があります。最終的には、考えられるすべての状態に対処するためのテーブルを作成することになります。

于 2012-09-03T04:57:15.270 に答える
1

速い：

まず、正規のハフマンコードを作成したことを確認します。ここで、短いコードは長いコードの前に数値的に表示されます。これは、最初にハフマンコードを各シンボルのビット数として簡単に記述することで簡単に実行できます。次に、ハフマンコードをシンボル順に最短のコードに割り当て、次にシンボル順に最短のコードを割り当てます。例えば

Symbol   Bits
  A        2
  B        4
  C        3
  D        3
  E        2
  F        3
  G        4

ビットで並べ替え、シンボルで並べ替えを保持：

Symbol   Bits
  A        2
  E        2
  C        3
  D        3
  F        3
  B        4
  G        4

ゼロから始まるハフマンコードを割り当てます。

Symbol   Bits    Code
  A        2     00
  E        2     01
  C        3     100
  D        3     101
  F        3     110
  B        4     1110
  G        4     1111

この標準的なアプローチは、実際のコードやツリーを送信する必要がなく、各シンボルのコード長だけを送信する必要があるため、コンプレッサーからデコンプレッサーにハフマンコードを送信するコンパクトな手段を提供します。次に、もう一方の端で上記のようにコードをビルドできます。

次に、デコードテーブル、シンボルテーブル、、Symbol[] = "AECDFBG"およびコードインデックステーブルを作成します。

Bits    Start     Index
  2    0000 (0)     0
  3    1000 (8)     2
  4    1110 (14)    5

ここでデコードするために、2ビットから4ビットまでループして、コードが次のビットサイズの開始コードよりも小さいかどうかを確認できます。ストリームから4ビットを引き出して呼び出しますnyb（ストリームにさらに4ビットがない場合は、ゼロビットを追加して入力します）。ifループの代わりに'sを使用する擬似コードでは、>>ビットを下にシフトすることを意味します。

if nyb < Start[Bits are 3] (= 8) then
    output Symbol[Index[Bits are 2] (= 0) + (nyb - Start[Bits are 2] (= 0)) >> 2]
    remove top two bits from bitstream
else if nyb < Start[Bits are 4] (= 14) then
    output Symbol[Index[Bits are 3] (= 2) + (nyb - Start[Bits are 3] (= 8)) >> 1]
    remove top three bits from bitstream
else (must be four bits)
    output Symbol[Index[Bits are 4] (= 5) + (nyb - Start[Bits are 4] (= 14))]
    remove top four bits from bitstream

それをループに変換する方法を理解するのは非常に簡単で、最短のコード長から2番目に長いコード長になります。それが見つからない場合は、最長のコード長である必要があります。

もっと早く：

長さが2**（最長のコードの長さ）のルックアップテーブルを作成します。テーブルの各エントリには、コードのビット数と結果のシンボルが含まれています。ビットストリームのその数のビットをインデックスとして使用します。繰り返しますが、ビットストリームにそれほど多くのビットが残っていない場合は、ゼロを入力します。次に、そのインデックス付きエントリからシンボルを出力し、そのインデックス付きエントリのビット数をビットストリームから削除します（これは、インデックス用にプルしたビット数よりも少ない場合があります。未使用のビットは必ず残してください。ビットストリーム）。繰り返します。ここで、残りのビットストリームから最初の未使用ビットを引き出します。

次のレベルの洗練度では、zlibが行うことを実行できます。最長のコードが比較的長い場合（zlibでは最大15ビットになる可能性があります）、次のアプローチと比較して、テーブルの作成にかかる時間は、デコードで節約された時間に対して支払われない場合があります。2レベルのテーブルがあり、最初のレベルのテーブルは最長のコードよりも短いnビットまでカバーします。（zlibでは、15ビットコードnが最適な選択であることがわかります。）次に、コードがビット以下の場合、テーブルエントリはシンボルとビット数を提供し、上記のように進みます。コードがビットを超える場合は、そのためのサブテーブルに移動しますn == 9nnn-上記のように、残りのビットを処理するビット値。そのテーブルエントリは、サブテーブルに対してプルするビット数を示し、そのサブテーブルのサイズを定義します。これを呼び出しますk。ストリームから上位ビットを削除しn、次のビットをプルして、kそれをサブテーブルへのインデックスとして使用します。次に、コード内のシンボルと残りのビット数を取得し、シングルレベルテーブルのように続行します。n+kサブテーブルは短いコードしかカバーしない可能性があるため、必ずしも各サブテーブルの最長コードの長さであるとは限らないことに注意してください。最後の1つまたはいくつかのサブテーブルのみがn+k、最長のコードの長さに等しくなります。

ハフマンコードの構築により、コードが短くなる可能性がはるかに高くなるため、これは非常に高速になる可能性があります。ほとんどの場合、最初のレベルでシンボルを取得しますが、たまに2番目のレベルに移動する必要があります。メインテーブルとすべてのサブテーブルに入力するテーブルエントリの総数は、コードの長さ全体をカバーする大きなテーブルのエントリの数よりもはるかに少なくなる可能性があります。これにより、デコードの準備にかかる時間が短縮されます。

さらに長いハフマンコード（32ビットなど）がある場合は、より多くのレベルのサブテーブルを作成できます。サブテーブルの最適なブレークポイントを決定するには、ある程度の実験が必要です。これは、新しいコードが送信され、テーブルを作成する必要がある頻度によって異なります。

于 2012-09-03T17:46:05.627 に答える