1

記事をハフマンコードにエンコードしてコードテーブルを出力するプログラムを作成しました。

H：000
d：1011
e：100
l：11
o：01
r：1010
w：001
総ビット数：27
エンコードされたコード：000100111101001011010111011

そして、ファイルを入力として受け取り、それをデコードするプログラムを書きたいと思います。

しかし、私はそれを再構築する方法がわかりません。

私の質問は、ハフマンツリーをどのように再構築するかです。

4

2 に答える 2

3

私の質問は、ハフマンツリーをどのように再構築するかです。

二分木になります。ルートノードを作成し、コードで始まるすべての文字を0左側のサブツリーに配置し、コードで始まるすべての文字を1右側のサブツリーに配置します。すべてのコードの最初の桁を削除して、（再帰的に）すすぎ、繰り返します。特定のコードの数字が足りなくなったら、対応する文字のリーフノードを作成します。

于 2012-12-16T16:08:38.963 に答える
3

コードが正規の方法で構築されている場合は、ハフマンツリーを再構築する必要はありません。これにより、短いコードは長いコードよりも数値的に小さくなります。ハフマン二分木の各ブランチに0と1を任意に割り当てる方法はたくさんあり、すべてがコードの同じ最適性をもたらします。多くの選択肢の1つを選択すると、コードのデコードと伝達に利点があります。

ハフマンアルゴリズムから必要な情報は、コードの長さ、つまり各シンボルのビット数だけです。これにより、短いコードから長いコードに進む標準ハフマンコードを作成し、任意のコード長内で字句順にシンボルを並べ替えることができます（たとえば、長さ3のすべてのコードをH、e、wの順序で並べ替えます）。コード長内でソートするポイントは、コードを再構築するために受信者に送信されるデータの量を減らすことです。

次に、次の代替コードに到達します。

l:00
o:01
H:100
e:101
w:110
d:1110
r:1111

これで、2つの単純なテーブルを使用してデコードを実行できます。1つは順番に並んだシンボル、つまり「loHewdr」と、次のコード長にステップアップするコード値です。ステップは0000、1から2ビット、10003ビット、11104ビットです。最長のコードに十分なビットを読み込みます（必要に応じて最後にゼロを追加しますが、後続のステップでコードの開始としてゼロを使用しないでください）。次に、値が次のコード長の先頭の値よりも小さい場合は、コードの現在のビット数を考慮して、その値をテーブルへのインデックスとして使用します。それ以外の場合は、その次の値までの値の数をインデックスに追加し、次の手順を確認します。スキップされた値の数を計算するには、現在のステップのコードのビット数も追跡する必要があります。

シンボルをデコードすると、それが何ビットであったかがわかります。それらのビットをストリームから削除して繰り返します。

このアプローチには、最も一般的な最短のコードに対して最速であるという利点もあります。結果として得られるデコード速度は非常に良好です。（他にも高速なテーブル駆動型の方法がありますが、はるかに複雑です。）

于 2012-12-16T19:14:32.477 に答える