問題タブ [prefix-tree]

私が解決しようとしている問題は、この質問で説明されています: O(1) でプレフィックス ツリーを使用して、単一の最近傍を検索しますか?

私の質問は、その質問ページの提案された解決策セクションに関するものです。そのセクションでは、ノードから開始してツリーをトラバースすることにより、各プレフィックス ツリーから最近傍を見つけることが言及されています。プレフィックスツリーにキーが存在するかどうかを調べるのは簡単ですが、最も類似したキーを取得することはまったくわかりません。これを達成する方法は？

誰かがこれを私に説明してくれたらいいのにと思いますが、グラフィックではない場合 (これが好ましいです)、少なくともいくつかの詳細を説明してください。

編集：

これが論文のコードです。これは Python で書かれていますが、残念ながら私は Python を使ったことがありません。誰かが python に精通していて、コードを検索して、プレフィックス ツリーを使用して最近傍を見つける方法を確認できる場合。https://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/nearest_neighbor_lsh.py

https://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/classes.py

str1 が str2 のプレフィックスかどうかを判断する簡単な関数を書き留めました。これは非常に単純な関数で、(JS では) 次のようになります。

ご覧のとおり、プレフィックス文字列の全長をループして、候補文字列のプレフィックスであるかどうかを判断します。これは、複雑さが O(N) であることを意味します。これは悪くありませんが、プレフィックス文字列がプレフィックスの一部として含まれる文字列を決定するためにループを検討する巨大なデータ セットがある場合、これは問題になります。これにより、複雑さが O(M*N) のように倍増します。ここで、M は特定のデータ セット内の文字列の総数です。良くない。

私はインターネットを少し調べて、最良の答えはパトリシア/基数のトライであると判断しました。文字列がプレフィックスとして格納される場所。それでも、文字列を挿入/検索しようとすると、前述のプレフィックスゲージ機能を使用すると、文字列の照合にかなりのオーバーヘッドが発生します。

プレフィックス文字列「rom」と候補単語のセットがあるとします

var dataset =["random","rapid","romance","romania","rome","rose"];

基数トライでこれが欲しい：

これは、すべてのノードに対して、プレフィックス一致関数を使用して、インデックスのプレフィックス文字列に一致する値を持つノードを特定することを意味します。どういうわけか、この解決策はまだ難しいようで、私にはあまりうまくいきません。もっと良いものはありますか、とにかくコアプレフィックスマッチング機能を改善できますか?

単語の膨大なコレクションを格納するプレフィックス ツリーがあります。現在、「a」という一般的な接頭辞を持つすべての単語を見つけたい場合は、最初に a を含む最初のノードを取得し、次に最初のノードの子ノードで深さ優先方式で徹底的に検索します。このアイデアは素朴で簡単に見えますが、共通の接頭辞を持つ単語の数が非常に多い (>20K) 場合、実際には非常に遅くなります。共通の接頭辞で始まるすべての単語を効率的に取得する他の方法はありますか? または、他のデータ構造を採用する必要がありますか? よろしくお願いします。

EDIT1 基本的に、すべてのノードにアクセスして文字を段階的に追加することにより、完全な単語を作成しています。すべての単語は、後でベクター コンテナーに格納されます。はい、再帰的な実装があります。

EDIT2

編集3 解決!!! 実際、私の実装には問題がありました。私はこの巨大なベクトル文字列コンテナを再帰呼び出しで渡していましたが、これが実際の問題でした。皆さん、親切なアドバイスをありがとうございます。

英語辞書の AZ からのすべての辞書単語のリストがあると仮定します。

これらの単語のリストに対して実行する 3 つのケースがあります。

1)特定の断片で「始まる」すべての単語を見つける

2)部分文字列としてフラグメントを「含む」すべての単語を見つける

3)特定の断片で「終わる」すべての単語を見つける

インターネットで検索を行った結果、1) トライ/圧縮トライを使用して実行でき、3) サフィックス ツリーを使用して実行できることがわかりました。

2）をどのように達成できるかわかりません。さらに、これら 3 つのケースすべてを処理できる、より良いシナリオはありますか? プレフィックス ツリーとサフィックス ツリーの両方を維持することは、メモリを集中的に使用するタスクになる可能性があるためです。

他に気を付けるべきエリアがあれば教えてください。

前もって感謝します。

PS: これを実現するために C++ を使用します

EDIT 1:当分の間、ここから多大な助けを借りてサフィックスツリーを構築しました。

C 言語での単一単語サフィックス ツリーの生成

ここでは、英語辞書の単語全体のサフィックス ツリーを構築する必要があります。だから私は作成する必要があります

a) 単語ごとに個別のサフィックス ツリーまたは

b) すべての単語の一般化された接尾辞ツリーを作成します。

a) の場合の部分文字列の照合中に、単語ごとに個々のツリーを追跡する方法がわかりません

ポインタはありますか？

トライ (プレフィックス ツリーとも呼ばれます) があります。接頭辞を指定して、その接頭辞で始まる10 個の単語のリストを取得したいと考えています。

この問題のユニークな点は、与えられたプレフィックスで始まる10 個の単語だけが必要であり、すべてではないということです。これを考慮して、実行できる最適化があります。

私が知っている以下の私のコードは正常に動作します。トライの各ノードには、childrenプロパティとプロパティがありthis_is_the_end_of_a_wordます。たとえば、「hi」を挿入すると、トライは次のようになります。

.

問題: 接頭辞を指定して、その接頭辞で始まる10 個の単語のリストを取得したいと考えています。

prefix問題に対する私のアプローチは次のとおりです。の最後の文字に対応するノードに到達するまで、 の文字をたどってプレフィックス ツリーを下りますprefix。ここで、このノードで DFS を実行し、リストにあるノードを追跡する必要this_is_the_end_of_a_word === trueがあります。ただし、リストの長さが 10 になったら検索を停止し、リストを返す必要があります。

私のアプローチは健全だと思いますが、特に再帰的な DFS を使用しようとしているため、実装に問題があります。そのため、再帰呼び出し間で「グローバル」リストを渡す方法がわかりません。クロージャーを使用する必要があることはわかっていますが、JavaScript は初めてで、どうすればよいかわかりません。私がすでに試したことの例を以下に示します。

私の Trie クラス (このコードが機能することはわかっています。これは、データ構造をどのように編成したかを確認できるようにするためです。)

私の最初のアプローチ（多くのバグがあります）

}

2番目のアプローチ：私が見ているPythonの例も見つけました： http://v1v3kn.tumblr.com/post/18238156967/roll-your-own-autocomplete-solution-using-tries 彼の例をJavaScriptに翻訳してみました。しかし、まだ何かがうまくいかないall_suffixes。