Edit Distanceアルゴリズムを使用して、名前データベースにあいまい検索を実装することを検討しています。
分割統治アプローチを通じてこれを高速化するのに役立つと思われるデータ構造を見つけました - Burkhard-Keller Trees。問題は、この特定の種類の木に関する情報があまり見つからないことです。
BK ツリーに任意のノードを設定すると、バランスの問題が発生する可能性はどのくらいありますか?
BK ツリーでバランスの問題が発生する可能性がある場合、構築後にそのようなツリーのバランスを取る方法はありますか?
BK ツリーのバランスを適切にとるためのアルゴリズムはどのようなものでしょうか?
これまでの私の考え：
子ノードは距離が異なるように見えるため、その下のツリー全体を再調整しないと、ツリー内の特定のノードを単純に回転させることはできません。ただし、最適な新しいルート ノードを見つけることができれば、これはまさに私がすべきことかもしれません。ただし、最適な新しいルート ノードを見つける方法がわかりません。
また、いくつかの方法を試して、空のツリーから開始し、事前に配布されたデータを挿入することによって、かなりバランスの取れたツリーを取得できるかどうかを確認します。
- アルファベット順にソートされたリストから始めて、真ん中からキューに入れます。（アルファベット順は編集距離での並べ替えとは異なるため、これが良いアイデアかどうかはわかりません）。
- 完全にシャッフルされたデータ。(これは運に大きく依存して、偶然に「それほどひどくない」ルートを選択します。ひどく失敗する可能性があり、最適ではないことが確率的に保証される可能性があります)。
- リスト内の任意の単語から始めて、残りの項目をその項目からの編集距離で並べ替えます。そして真ん中から並びます。(これにはコストがかかると思いますが、すべての単語間のメトリック空間の接続を計算するわけではないため、各単語と単一の参照単語だけで計算することはできません)。
- 任意の方法で最初のツリーを構築し、それを平坦化し (基本的には事前注文トラバーサルのように)、途中から新しいツリーのキューに入れます。(これもコストがかかります。事前にすべての単語間のメトリック空間の接続を計算せず、単に別の不均一な分布が得られるため、まだうまくいかない可能性があると思います)。
- 名前の頻度で並べ替え、最も人気のあるものを最初に挿入し、バランスの取れたツリーの概念を捨てます。(私のデータは均等に分散されておらず、純粋にランダムな単語が入ってくることはないので、これが最も理にかなっているかもしれません)。
参考までに、私は現在、同義語の問題 (Bill vs William) について心配していません。私はそれを個別に扱いますが、まったく異なる戦略が適用されると思います.