3

ハフマンツリーを脱水するための最良の方法は何ですか。脱水とは、ハフマンツリーと各葉の文字を指定して、このツリーの構造を効率的に保存し、後で再構築する方法を意味します。

以下の木を取ります：

---------------garbage------
 -------------/-------\------
 ------------A-------garbage-
 --------------------/-----\-
 -------------------B-------C-

1つのアイデアは、各レベルでシンボルを格納し、この情報を使用してツリーを再構築することです。この場合：A1B2C2。では、最初にレベルを取得し、各レベルをキャラクターに関連付けるにはどうすればよいですか。

4

2 に答える 2

5

ほぼ確実に、ツリー自体を保存する必要はありません。あなたはそうすることができます、そしてそれはあなたがそうすると思うスペースを取るべきではありません、しかしそれは一般的に必要ではありません。

ハフマンコードが正規の場合、正規のコーディングを生成するために必要なすべての情報であるため、各シンボルのビット長のみを格納する必要があります。これはシンボルあたりのビット数が比較的少ないため、かなりコンパクトにする必要があります。その情報をさらに圧縮することもできます（Aki Suihkonenの回答を参照）。

当然、コードのビット長は基本的にツリーの深さと同じなので、これはおおよそあなたが求めていることだと思います。重要な部分は、長さを考慮して、正規のコードを作成する方法を知ることです。これは、ツリーをトラバースすることによって生成されるコードと必ずしも同じではありません。これからツリーを再生成することもできますが、必ずしも最初に作成したツリーである必要はありません。ただし、通常、最初にコードの長さを決定する以外にツリーは必要ありません。

正規コードを生成するためのアルゴリズムはかなり単純です。

  1. コードを生成するすべてのシンボルを取得し、最初にコード長（最初に最短）でソートし、次にシンボル自体でソートします。
  2. 長さゼロのコードから始めます。
  3. 次のシンボルが現在コードにあるよりも多くのビットを必要とする場合は、正しい長さになるまでコードの右側（最下位ビット）にゼロを追加します。
  4. コードを現在のシンボルに関連付け、コードをインクリメントします。
  5. すべてのシンボルを生成するまで、（3）にループバックします。

文字列「バナナ」を取ります。明らかに、「b」、「a」、および「n」の3つの記号が使用されており、それぞれ1、3、および2のカウントがあります。

したがって、ツリーは次のようになります。

    *
   / \
  * a
 / \
bn

素朴に、それはコードを与える可能性があります：

a = 1
b = 00
n = 01

ただし、代わりに、正規のコード生成への入力としてビット長を使用する場合は、次のようになります。

a = 0
b = 10
n = 11

コードは異なりますが、明らかに同じ長さの圧縮出力が生成されます。さらに、コードを再現するために必要なのはコード長のみです。

したがって、シーケンスを保存するだけで済みます。

0 ... 1 2 0 ... 20..。

ここで、「...」は簡単に圧縮できる繰り返しを表し、値はすべて非常に小さくなります（おそらく、それぞれ4ビットのみです。シンボルはまったく保存されないことに注意してください）。この表現は非常にコンパクトになります。

本当にツリー自体を格納する必要がある場合、1つの手法は、ツリーをトラバースして1ビットを格納し、ノードが内部かリーフかを示し、リーフノードの場合はシンボルコードを格納することです。これは、すべてのシンボルを含まないツリーではかなりコンパクトであり、かなり完全なツリーでもそれほど悪くはありません。これの最悪の場合のサイズは、すべてのシンボルの合計サイズに加えて、ノードを持つことができる限り多くの単一ビットになります。標準の8ビットバイトストリームの場合、320バイトになります（コードの場合は256バイト、ツリー構造自体の場合は511ビット）。

この方法は、ルートノードから開始し、ノードごとに次のようにします。

  • ノードが親の場合は、0を出力してから、左から右の子を出力します。
  • ノードがリーフの場合は、1を出力してからシンボルを出力します

再構築するには、同様の再帰的な手順を実行しますが、明らかにデータを読み取り、必要に応じて、子を再帰的に作成するか、シンボルを読み込むかを選択します。

上記の例では、ツリーのビットストリームは次のようになります。

0、0、1、'b'、1、'n'、1、'a'

これは、ツリーの場合は5ビット、シンボルの場合は3バイトであり、4バイトのストレージに切り上げられます。ただし、シンボルを追加すると急速に大きくなりますが、コード長を格納することはできません。

于 2013-02-26T07:23:43.957 に答える
2

zlib 仕様では、ハフマン ツリーを格納するには、各シンボルのビット長のみが必要であると説明されています。たとえば、A=101、B=111、C=110、D=01 のツリーを構築する場合、単純にビット長をカウントし、キーワードが連続するように長さからツリーを再生成します --> A=101、 B=110、C=111、D=01。(または、次のコードが生成するもの)

設定bl_count[2]=1, bl_count[3]=3して繰り返す:

code = 0;   // From z-lib specification, RFC 1951
bl_count[0] = 0;
for (bits = 1; bits <= MAX_BITS; bits++) {
    code = (code + bl_count[bits-1]) << 1;
    next_code[bits] = code;
}

シンボルの最大長は 16 未満であるため、これらの長さを格納するにはシンボルあたり最大 4 ビットが必要です。ただし、zlib/deflate の方が優れています。16 == run of 3、17: run of 4 などのエスケープ記号を使用してこれらの記号を長さエンコードし、記号の長さのストリームをさらに圧縮します。また、RLE は長さ 0 の場合、つまり欠落した文字を扱います。

于 2013-02-27T07:49:29.550 に答える