1

私が解決しようとしている問題は、この質問で説明されています: 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

4

1 に答える 1

2

最初に、ツリー全体を反復処理することを知ってください。ツリー全体を反復処理することで、最も類似した隣人を見つけることが保証されます。

平均的なケースでより効率的にするには、ツリーに DFS グラフ トラバーサルを使用します。これはツリーであるため、訪問したノードのカラーリング スキームは必要ないことに注意してください。

最も近いオブジェクトを null として、ツリーのルートから開始します。

ノードごとに、追加された編集距離が最も近いオブジェクトまでの距離よりも大きくない場合にのみ、編集距離に追加される順序で子をトラバースする必要があります。たとえば、ハミング距離では、最初に全体の距離に「O」を追加する子をトラバースし、次に全体の距離に「1」を追加する子をトラバースします。ただし、編集距離が現在の最も近い距離よりも大きくなる場合は、「1」の子にトラバースしないでください。

プレフィックス ツリー内で「単語」に遭遇した場合は、クエリ オブジェクトまでの距離が最も近いオブジェクトよりも短いかどうかを確認し、最も近いオブジェクトに割り当てます。

于 2013-06-24T21:40:31.137 に答える