5

現在、基数ツリー/パトリシア トライを実装しています (名前は何でも構いません)。非常に能力の低いハードウェアで辞書のプレフィックス検索に使用したいと考えています。多かれ少なかれオートコンプリートのように機能するはずです。つまり、入力されたプレフィックスが一致する単語のリストを表示します。

私の実装はこの記事に基づいていますが、そのコードにはプレフィックス検索が含まれていませんが、著者は次のように述べています。

[...] 共通のプレフィックス「AB」を持つキーを持つすべてのノードを列挙したいとします。そのルートから開始して、バック エッジに遭遇するたびに停止する深さ優先検索を実行できます。

しかし、それがどのように機能するのかわかりません。たとえば、次の単語から基数ツリーを構築するとします。

病気
想像上の
想像力
想像する
模倣
すぐ
に すぐ に
巨大

接頭辞「i」と「in」に対してまったく同じ「ベストマッチ」を取得するため、そのベストマッチからツリーをトラバースするだけで、一致するすべての単語を収集するのは難しいようです。

さらに、Java には基数ツリーの実装があり、 RadixTreeImpl.javaにプレフィックス検索が実装されています。そのコードは、すべてのノード (特定のノードから始まる) を明示的にチェックして、プレフィックスの一致を確認します。実際にはバイトを比較します。

基数ツリーでのプレフィックス検索の実装に関する詳細な説明を誰かに教えてもらえますか? Java 実装で使用されるアルゴリズムは、それを行う唯一の方法ですか?

4

4 に答える 4

8

トライが何をエンコードするかを考えてください。各ノードには、そのノードにつながるパスがあるため、この例では、空の文字列に対応するルート ノードである Λ (大文字の Lambda、このギリシャ フォントの種類は最悪です) から開始します。Λ には使用される文字ごとに子があるため、データ セットには「i」の 1 つの分岐があります。

  • Λ
  • ∧→「い」

「i」ノードには、「m」用と「n」用の 2 つの子があります。次の文字は「n」なので、それを取ります。

  • Λ→「い」→「ん」

また、データセットで「i」、「n」で始まる単語は「in」のみであるため、「n」からの子はありません。それは一致です。

ここで、データ セットに "in" ではなく "infindibulum" があったとします。(私が参照している SF は演習として残されています。) 同じ方法で "n" ノードに到達しますが、次に取得する文字が "q" である場合、単語が表示されないことがわかります。 「q」ブランチがないため、データセットにはまったくありません。その時点で、あなたは「わかりました、一致しません」と言います。(アプリケーションによっては、単語の追加を開始する場合もあれば、そうでない場合もあります。)

でも、次の文字が「f」なら続けられます。ただし、ちょっとした工夫でそれを回避できます。一意のパスを表すノードに到達したら、そのノードから文字列全体をぶら下げることができます。そのノードに到達すると、残りの文字列は「findibulum」でなければならないことがわかっているため、プレフィックスを使用して文字列全体に一致させ、それを返します。

あなたはそれをどのように使っていますか？古い VAX DCL のような多くの非 UNIX コマンド インタープリターでは、コマンドの任意の一意のプレフィックスを使用できます。したがって、ls(1)に相当するものはでしDIRECTORYたが、DIR で始まるコマンドは他にないため、入力することができDIR、単語全体を実行するのと同じくらい優れていました。正しいコマンドを思い出せない場合は、'D' と入力して ESC を押してください。DCL CLI はで始まるすべてDのコマンドを返し、非常に高速に検索できます。

于 2009-04-27T18:26:56.710 に答える
3

標準のc++libのGNU拡張機能には、Patriciatrieの実装が含まれていることがわかりました。これは、ポリシーベースのデータ構造拡張の下にあります。http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/trie_based_containers.htmlを参照してください

于 2010-03-02T16:14:27.650 に答える
1

別のアルゴリズム: ばかばかしい単純さを保つ!

キーワードのソート済みリストを作成するだけです。接頭辞がある場合は、その接頭辞がリスト内のどこにあるかを見つけるためにバイナリ検索を行います。可能なすべての補完がそのインデックスから開始され、すぐにアクセスできるようになります。

このアルゴリズムは、パトリシア トライのコードの 5% しか必要とせず、保守、理解、および更新が容易です。この単純なリスト検索もより効率的であることはほぼ確実です。

唯一の欠点は、同様の接頭辞を持つ長いキーワードが多数ある場合、すべてのエントリの完全な接頭辞を保持する必要がないため、トライを使用するとストレージを節約できることです。実際には、単語数が数百万未満の場合、ツリーのポインター オーバーヘッドが支配的であるため、節約にはなりません。この節約は、テキスト キーワードではなく、何百万もの文字を含む DNA 文字列のデータベースの検索などのアプリケーションに適しています。

于 2009-04-28T07:13:39.643 に答える