2

ハフマン ツリーを格納する効率的な方法に関する私の質問に関連するフォローアップの質問として、(ハフマン コーディング出力に基づいて) バイナリ ツリーを検索し、特定のノードへのパスを格納する最速かつ最も効率的な方法は何かと考えていました。 .

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

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

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

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

ルートからノードへのパスをノード内の別の値として保存することも提案されましたが、その目的のために作成した変数が保持できるビット数よりも大きなツリーがあった場合、これは失敗します。データを格納するポイントも大量のメモリを占有します。

4

2 に答える 2

2

値->ビット文字列の辞書を作成します。これにより、最速の検索が可能になります。

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

于 2009-04-30T16:56:55.823 に答える
0

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

于 2009-08-03T22:53:28.527 に答える