問題タブ [bk-tree]

私は現在、スペルチェッカーを作成するためにBK-Treeを実装しています。私が使用している辞書は非常に大きい（数百万語）ので、非効率性をまったく許容できません。しかし、私が書いたルックアップ関数（おそらくプログラム全体の中で最も重要な部分）をより良くすることができることを私は知っています。私は同じことに関していくつかの助けを見つけることを望んでいました。これが私が書いたルックアップです：

ループを不必要に何度も実行していること、および検索スペースをトリミングしてルックアップを高速化できることを知っています。どうすればいいのかよくわかりません。

以下はBK-Treeを書くための私の試みです。150000ワードファイルの場合、それは周りにかかります8 seconds

この時間を短縮する方法はありますか？

以下は私のコードです

以下は私がやろうとしていることです。2つの単語W1とそれらの単語W2のforが1の場合は友達ですLevenshtein distance。私は友達の友達もすべて見つけることになっています。私はBk-Treeで同じことをしようとしました。小さいサイズの辞書（辞書には1行に1つの単語しか含まれていません）では機能しますが、大きい辞書では速度が大幅に低下し、1時間以上実行されても結果は得られません。

以下はこれまでの私のコードです

速度の向上に関するコメント、またはその他の適切なデータ構造。

以下が私の辞書だとしましょう。

私は答えのを見つけようとしてsocial networkいaaます5。

Cython で BK-Tree を実装しています。

100 万件の場合、検索時間が長すぎます。それは〜30秒です:(

ここに私のCythonコードがあります:

距離.h

例：

このツリーは、256 ビット ハッシュによる重複画像の検索を開始します。

findInTreeこの機能を最適化するにはどうすればよいですか?

Edit Distanceアルゴリズムを使用して、名前データベースにあいまい検索を実装することを検討しています。

分割統治アプローチを通じてこれを高速化するのに役立つと思われるデータ構造を見つけました - Burkhard-Keller Trees。問題は、この特定の種類の木に関する情報があまり見つからないことです。

BK ツリーに任意のノードを設定すると、バランスの問題が発生する可能性はどのくらいありますか?

BK ツリーでバランスの問題が発生する可能性がある場合、構築後にそのようなツリーのバランスを取る方法はありますか?

BK ツリーのバランスを適切にとるためのアルゴリズムはどのようなものでしょうか?

これまでの私の考え：

子ノードは距離が異なるように見えるため、その下のツリー全体を再調整しないと、ツリー内の特定のノードを単純に回転させることはできません。ただし、最適な新しいルート ノードを見つけることができれば、これはまさに私がすべきことかもしれません。ただし、最適な新しいルート ノードを見つける方法がわかりません。

また、いくつかの方法を試して、空のツリーから開始し、事前に配布されたデータを挿入することによって、かなりバランスの取れたツリーを取得できるかどうかを確認します。

• アルファベット順にソートされたリストから始めて、真ん中からキューに入れます。（アルファベット順は編集距離での並べ替えとは異なるため、これが良いアイデアかどうかはわかりません）。
• 完全にシャッフルされたデータ。(これは運に大きく依存して、偶然に「それほどひどくない」ルートを選択します。ひどく失敗する可能性があり、最適ではないことが確率的に保証される可能性があります)。
• リスト内の任意の単語から始めて、残りの項目をその項目からの編集距離で並べ替えます。そして真ん中から並びます。(これにはコストがかかると思いますが、すべての単語間のメトリック空間の接続を計算するわけではないため、各単語と単一の参照単語だけで計算することはできません)。
• 任意の方法で最初のツリーを構築し、それを平坦化し (基本的には事前注文トラバーサルのように)、途中から新しいツリーのキューに入れます。(これもコストがかかります。事前にすべての単語間のメトリック空間の接続を計算せず、単に別の不均一な分布が得られるため、まだうまくいかない可能性があると思います)。
• 名前の頻度で並べ替え、最も人気のあるものを最初に挿入し、バランスの取れたツリーの概念を捨てます。(私のデータは均等に分散されておらず、純粋にランダムな単語が入ってくることはないので、これが最も理にかなっているかもしれません)。

参考までに、私は現在、同義語の問題 (Bill vs William) について心配していません。私はそれを個別に扱いますが、まったく異なる戦略が適用されると思います.

BK Trees に関するこの投稿を読んで、次のスニペットが少しわかりにくいことがわかりました。

「しばらくの間、クエリ、検索で使用している文字列、および文字列がクエリから離れて返される最大距離の 2 つのパラメータがあるとします。任意の文字列を取得し、それをテストしてクエリと比較するとします。 . 結果の距離を d と呼びます。三角形の不等式が成り立つことがわかっているため、すべての結果は最大で d+n の距離、少なくともテストからの距離は dn でなければなりません。

検索している単語から何かがd離れていて、エラーを許容できる場合、違いを「元に戻す」には、現在の単語からn少なくとも距離が必要になることが直感的にわかります。d-n同様にd+n、違いを「逆転」させた後、さらにn個の違いを導入できるため、最大でも持つことができます。

これを得るために三角形の不等式がどのように使用されたか混乱しています。d(test, query) = d および d(query, found) <= n とすると、次の不等式によります。

どうすれば見つけることができますか

私は多くの 異なる 言語で BK ツリーのさまざまな実装を見てきましたが、文字通り、ツリーからノードを削除する方法を含むものはないようです。

BK ツリーが最初に紹介された元の記事でさえ、ノードの削除について意味のある洞察を提供していません。著者は、削除するノードをマークして無視するように提案しているだけです。

構造 1 [BK ツリー] および 2 のキーの削除は、削除するキーが代表 x° [ルート キー] である場合を特に考慮して、上記と同様のプロセスに従います。この場合、キーは構造情報に不可欠であるため、単純に削除することはできません。代わりに、キーが実際にレコードに対応するかどうかを示す余分なビットを各キーに使用する必要があります。検索アルゴリズムは、レコードに対応しないキーを無視するように対応して変更されます。これには、更新手順で余分なビットをテストすることが含まれます。

BK ツリーのノードを適切に削除することは理論的には可能かもしれませんが、線形/準線形時間で削除することは可能ですか?