Trie実装の質問

Question

私はVB.NETでの予測的なテキスト入力のためのトライを実装しています - 基本的には、トライの使用に関する限りオートコンプリートです。私は、ジェネリック辞書クラスに基づいて再帰的なデータ構造を作成しました。

それは基本的にあります：

class WordTree Inherits Dictionary(of Char, WordTree) 

単語内の各文字（すべての同棲上）新しいWordTrieへのキーとして使用されます。リーフのヌル文字は、単語の終了を示します。接頭辞で始まる単語を見つけるには、私の接頭辞がすべての子供の言葉を収集する限り、トライを歩きます。

私の質問は、基本的にトライ自体の実装です。辞書ハッシュ関数を使ってツリーを分岐しています。私はリストを使用し、リストの上で線形検索をするか、何か他のことをすることができます。ここで円滑な動きは何ですか？これは私の分岐を行うための合理的な方法ですか？

ありがとうございました。

更新：アプローチを分岐辞書は明らかにいくつかの他の代替に比べて劣る場合

だけ明確にする、私は基本的に求めています。私がこのデータ構造を使用しているアプリケーションでは、大文字しか使用しないので、おそらく配列のアプローチが最適です。私は、将来のより複雑な先制的な状況（より多くの文字）に同じデータ構造を使用するかもしれません。その場合、辞書が正しいアプローチであるように聞こえます。一般的にはもっと複雑なものを使う必要があります。

Answer 1

26文字であれば、26個のエントリ配列です。その後、索引による検索が行われます。バケットリストが26よりも長い場合は、おそらくDictionaryよりもスペースが少なくなります。

Answer 2

空間的に効率的で潜在的にサブリニアのプレフィックスルックアップを与える優れたデータ構造は、3値探索ツリーです。約Peter Kankowski has a fantastic article彼はCを使っていますが、データ構造を理解すればそれは簡単なコードです。彼が言及したように、これはスペルの修正にispellが使用する構造体です。

Answer 3

私はこれを8ビットの文字でCで行い、単純に配列のバージョンを使用しました（「26文字」という答えになります）。

しかし、私はあなたが完全なユニコードサポートを望んでいると推測しています（.NETのcharはユニコードなので、他の理由もあります）。あなたがユニコードをサポートしなければならないと仮定すると、各ノードの64Kエントリ配列は実際にはうまく動作しないので、おそらくハッシュ/マップ/辞書ルックアップが最善の策です。

これについて私が考えることのできる唯一のハックアップについては、木がどれほど疎であるかに応じて、まだ分割されていない枝に文字列全体（サフィックスまたは「インフィックス」）を格納することです。しかし、これはマルチ文字列を検出するための多くのロジックを追加し、代替パスが導入されたときにそれらを分割します。

読み取りと更新のパターンは何ですか？

---- .NETストリングは、次に表すために、各ノードの配列を有する、（UTF-8など）は、文字列のバイトを取得するためのJavaのような機能を持っている場合は2013年7月---

を更新現在の位置のバイト値はおそらく良い方法です。 MANYノードには小文字のASCII文字のみ、場合によっては大文字または0-9の数字しか持たないので、各ノードの最初/最後の境界インジケータを使用して配列を可変サイズにすることもできます。

Answer 4

スペースが心配な場合は、有効なバイトトランジションでビットマップ圧縮を使用できます（26文字の制限があるとします）。

class State // could be struct or whatever 
{ 
    int valid; // can handle 32 transitions -- each bit set is valid 
    vector<State> transitions; 

    State getNextState(int ch) 
    { 
     int index; 
     int mask = (1 << (toupper(ch) - 'A')) -1; 
     int bitsToCount = valid & mask; 

     for(index = 0; bitsToCount ; bitsToCount >>= 1) 
     { 
      index += bitsToCount & 1; 
     } 
     transitions.at(index); 
    } 
}; 

Hereをカウントビットを行うための他の方法があり、ベクトルへのインデックスは、有効ビット集合にセットされたビットの数です。もう1つの選択肢は、状態の直接インデックス配列です。

class State 
{ 
    State transitions[ 26 ]; // use the char as the index. 

    State getNextState(int ch) 
    { 
     return transitions[ ch ]; 
    } 
}; 

Answer 5

私はburst trie'sが非常に効率的であることを発見しました。私は自分自身でburst trie in Scalaと書いて、GWTのトライ実装で見つけたアイディアを再利用しています。私はStripeのCapture the Flagコンテストで、多量のRAMを持つマルチノードの問題について使用しました。