取られたパスを思い出しながら効率的なハフマンツリー検索

Question

私のハフマンツリーの効率的な保存方法に関する質問（ハフマンコーディングの出力に基づいて）バイナリツリーを検索し、特定のノードにたどるパスを保存する最も高速で効率的な方法は何だろうと思っていました。

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

• ルートノードをキューに追加
• キューが空ではない間、アイテムをキューからポップします
  • 探しているものかどうかを確認する
    • はい： ヘッドポインターをたどってルートノードに戻り、各ノードで左か右かを確認し、メモします。
    • 検索から抜け出す
  • 左ノードと右ノードをキューに入れる

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

この場合、すべての右/左パスも逆の順序で取得します。たとえば、ルートに向かってヘッドをたどると、ルートから右、左、左、左、左、右に行きます。または、001をバイナリで、探しているのが100を効率的な方法で取得することである場合。

ルートからノードへのパスを別の値としてノード内に保存することも提案されましたが、その目的のために作成した変数が保持できるビット数よりも大きいツリーがある場合、これは壊れます。また、その時点でデータを保存すると大量のメモリを消費します。

Answer 1

価値のある辞書を作成-＆gt;ビット文字列、それはあなたに最速のルックアップを与えるでしょう。

値が既知のサイズである場合は、ビット文字列の配列だけで取得でき、インデックスで値を検索できます。

Answer 2

ハフマンエンコードデータを1ビットずつデコードしている場合、パフォーマンスが低下します。ルックアップテーブルの使用を避けたい限り、それがパフォーマンスを重視する場合の唯一の方法です。ハフマンコードの作成方法は、左から右に一意であり、高速なテーブルルックアップに最適です。