15

Trieについて読み始めています。ここの友人からも参照を得ました: Trie のチュートリアル

次の点については明確ではありません: 続け
てトライを使用すると、検索スペースになり、トライを構築するために使用されるすべての入力文字列が別個の単語境界で区切られていると想定されているようです。
たとえば、私が見たすべてのサンプル チュートリアルでは、次のような入力を使用しています。 

S={ball, bid, byte, car, cat, mac, map etc...}

次に、トライを構築し、検索を実行し ますS(非常に高速です) 。 つまり、試行について読み始める前に、それは恣意的に長いテキストになると想像していました。
S
SShakespeare

次に、Trie を使用すると、物事を非常に高速に見つけることができます。
しかし、そうではないようです。

Shakespeare入力パッセージ (たとえば) が最初に前処理され、取得するすべての単語が抽出されるという仮定はここにありますSか?

したがって、パターンを検索したい場合 (Google で検索クエリにスペースを含むすべてのページを表示する場合と同じ方法)、Trie は適切ではないでしょうか?
Trie が実際に使用できるデータ構造であるかどうかは、いつわかりますか?

4

4 に答える 4

12

トライは、すばやく調べたい固定辞書がある場合に便利です。ハッシュテーブルと比較すると、大きなディクショナリに必要なストレージは少なくて済みますが、ルックアップに時間がかかる場合があります。私がこれを使用した例の 1 つは、プレフィックスに基づいて機能が継承される可能性がある場合に、URL を Web サーバー上の操作にマッピングする場合です。ここで、トライを再帰することで、特定の URL に対して呼び出す必要のあるすべてのメソッドを適切に検索できます。辞書の保管にも効率的です。

テキスト検索を行う場合、通常、重み付きの語彙素のトークン ベクトルを使用してドキュメントを表し (おそらく発生頻度に基づく)、それに対して検索して、特定の検索ベクトルに対するドキュメントのランキングを取得します。これを行うための標準ライブラリがいくつかありますが、特にストップワードの削除、同義語の処理、ステミングについては、独自のライブラリを作成するのではなく、使用することをお勧めします。

于 2012-05-22T07:48:27.967 に答える
2

試行を使用する方法は複数あります。典型的な例は、あなたが提示したようなルックアップです。ただし、試行を使用して、完全なテキストに完全にインデックスを付けることもできます。Ukkonen接尾辞ツリーアルゴリズムを使用して接尾辞トライを生成するか、接尾辞を格納することによって接尾辞トライを明示的に構築します（Ukkonensアルゴリズムよりもはるかに低速ですが、はるかに単純です）。これは前処理であるため、速度がそれほど重要ではない場合にのみ実行する必要があります。

このためには、テキストを取得し、全文を挿入してから、最初の文字を切り刻み、結果のテキストを挿入し、2番目の文字を切り刻み、挿入します...

したがって、「The Text」というテキストがある場合は、次のセットを挿入します。

{"The Text", "he Text", "e Text", " Text", "Text", "ext", "xt", "t"}

結果の接尾辞trieで、任意の種類の接頭辞を簡単に検索できます。また、一般的なプレフィックスは1回だけ保存されるため、文字列全体を保存する必要がないため、これはスペース効率に優れています。

はるかに長い文字列スペースを効率的に格納する必要がある場合は、プレフィックスだけでなくサフィックスも一緒に格納するのが最善です。その場合、有向非巡回ワードグラフ（DAWG）を作成できます。これは、概念のトライと非常によく似ています。

したがって、その意味でのトライでは、部分的な単語を含む任意の部分文字列を見つけることができます。単語の保存のみに関心がある場合は、別のデータ構造を使用する必要があります。たとえば、転置リスト（順序が重要な場合）やベクトル空間ベースの検索アルゴリズム（単語の順序が重要でない場合）などです。

于 2012-05-22T12:45:28.520 に答える
2

他の例で述べたように、トライは高速な文字列ルックアップ (または、より一般的には任意のシーケンスのルックアップ) を提供するので便利です。私が試行を使用した場所のいくつかの例:

  • この質問に対する私の答えは、文の照合に (少し変更された) トライを使用します。これは、一連の文字ではなく、一連の単語に基づくトライです。(その質問に対する他の回答は、おそらく実行中のトライをより明確に示しています。)
  • また、名前付きの部屋が多数あるゲームでトライを使用しました (合計数と名前は実行時に定義されます)。これらの名前はそれぞれ一意である必要があり、検索できる必要があります。すぐに与えられた名前の部屋。ハッシュ テーブルを使用することもできますが、文字列を使用する場合は、いくつかの点でトライの方が実装が簡単で高速です。(私のトライの実装は、最終的に 50 行の C でした。)

タグには、おそらくもっと多くの例があります。

于 2012-05-22T08:26:08.183 に答える
2

毎回文字列を前処理することなく、線形時間で部分文字列検索に試行を使用できます。Ukkonen のサフィックス ツリー アルゴリズム @ Ukkonen のサフィックス ツリー生成に関する最高のチュートリアルを平易な英語で入手できます か?

于 2012-05-22T07:39:11.600 に答える