1

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

それは基本的に：

class WordTree Inherits Dictionary(of Char, WordTree)

単語内の各文字（すべて大文字）は、新しいWordTrieのキーとして使用されます。リーフのヌル文字は、単語の終了を示します。接頭辞で始まる単語を見つけるために、接頭辞が尽きるまでトライを歩き、すべての子の単語を収集します。

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

ありがとう。

アップデート：

明確にするために、私は基本的に、辞書の分岐アプローチが他の方法よりも明らかに劣っているかどうかを尋ねています。このデータ構造を使用しているアプリケーションでは大文字のみを使用しているため、配列アプローチが最適な場合があります。将来、より複雑な先行入力状況（より多くの文字）に同じデータ構造を使用する可能性があります。その場合、辞書が正しいアプローチのように思えます。一般的にもっと複雑なものを使用する必要があるところまでです。

4

5 に答える 5

3

26文字の場合は、26エントリの配列として。次に、ルックアップはインデックスによるものです。バケットリストが26より長い場合は、おそらくディクショナリよりも少ないスペースを使用します。

于 2009-03-23T19:26:31.257 に答える
3

スペースが心配な場合は、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 );
    }
};

ビット カウントを行う方法は他にもあります。ここで、ベクトルへのインデックスは、有効なビットセットに設定されたビットの数です。もう 1 つの選択肢は、直接インデックス付けされた状態の配列です。

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

    State getNextState( int ch )
    {
        return transitions[ ch ];
    }
};
于 2009-03-23T21:01:20.687 に答える
2

空間で効率的で、潜在的に劣線形プレフィックスルックアップを提供する優れたデータ構造は、三分探索木です。PeterKankowskiがそれについて素晴らしい記事を書いています。彼はCを使用していますが、データ構造を理解すれば、それは簡単なコードです。彼が述べたように、これはispellがスペル修正に使用する構造です。

于 2009-03-23T19:46:02.660 に答える
2

私はこれ（トライの実装）を8ビット文字のCで行い、単純に配列バージョンを使用しました（「26文字」の答えでほのめかされています）。

ただし、完全なUnicodeサポートが必要だと思います（.NET文字はUnicodeであるため、他の理由もあります）。Unicodeをサポートする必要があると仮定すると、各ノードの64Kエントリ配列は実際にはうまく機能しないため、ハッシュ/マップ/辞書ルックアップがおそらく最善の策です。

これについて私が考えることができる唯一のハックアップは、ツリーがどれだけまばらであるかに応じて、まだ分割されていないブランチに文字列全体（サフィックスまたは場合によっては「インフィックス」）を格納することです。ただし、これにより、複数文字の文字列を検出し、代替パスが導入されたときにそれらを分割するための多くのロジックが追加されます。

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

----2013年7月更新---

.NET文字列に（UTF-8として）文字列のバイトを取得するjavaのような関数がある場合、現在の位置のバイト値を表す配列を各ノードに持つことはおそらく良い方法です。多くのノードには小文字のASCII文字のみ、場合によっては大文字または0〜9の数字のみが含まれるため、各ノードに最初/最後の境界インジケーターを使用して配列を可変サイズにすることもできます。

于 2009-03-23T19:49:11.840 に答える
0

バースト トライはスペース効率が非常に高いことがわかりました。GWT のトライ実装で見つけたいくつかのアイデアを再利用する、Scala で独自のバースト トライを作成しました。Stripe の Capture the Flag コンテストで、少量の RAM を備えたマルチノードの問題で使用しました。

于 2014-04-29T19:38:03.613 に答える