効率的なハフマンツリー検索で、取得したパスを記憶している

Question

私のquestion regarding efficient way of storing huffman tree'sに関連するフォローアップの質問として、（ハフマン符号化出力に基づいて）バイナリツリーを検索し、特定のノードに送信する。

これは私が現在持っているものです。

• キューが空でない間、それは我々が を探しているものであれば、キュー、
• をキューに
  • チェックをポップアイテムをルートノードをオフに追加
    • yes： ルートノードに戻るヘッドポインタに従います。各ノードでは、左または右であるかどうかを確認し、それのノート。
    • 検索
  • 左エンキュー、および右ノード

のうち休憩これはハフマン木ですので、私が探していますすべてのエントリが存在します。上記のものは幅広い最初の検索で、ハフマンの木に最も適していると考えられています。なぜなら、ソース内のアイテムがツリー内でより高い圧縮率を得るために高くなっているからです。しかし、追跡する良い方法はわかりません私がノードに置いたヘッドポインタを使ってバックトラックせずに特定のノードに到達した方法。

この場合、左右のパスのすべてを逆の順序で取得しています。たとえば、ルートにヘッドを追いかけると、ルートから右、左、左に移動する、左、左、右になります。私が探しているのは効率的な方法で100を得ることです。

ノード内に別の値としてルートからノードへのパスを格納することも提案されていましたが、その目的で作成した変数が保持できる多くのビットその時点でデータを格納すると膨大な量のメモリを占有することになります。

Answer 1

最速の検索を可能にする値 - >ビット列の辞書を作成します。

値が既知のサイズの場合、おそらくビットストリングの配列だけで取得し、そのインデックスで値をルックアップすることができます。

Answer 2

ハフマンエンコードされたデータを一度に1ビットずつデコードすると、パフォーマンスが低下します。ルックアップテーブルの使用を避けたいのと同じくらい、パフォーマンスを気にするなら、これは唯一の方法です。ハフマンコードが作成される方法は、左から右に固有のものであり、高速なテーブル検索に完全に役立ちます。