2 つの異なる単語間の距離の計算について、レーベンシュタイン距離について読みました。
ソース文字列が 1 つあり、それを 10,000 のターゲット ワードすべてと一致させる必要があります。最も近い単語が返されます。
問題は、10,000 のターゲット ワードのリストを指定したことと、入力ソース ワードも巨大であることです。ここで適用する最短かつ効率的なアルゴリズムは何でしょうか。n ごとの組み合わせごとのレーベンシュタイン距離の計算 (ブルート フォース ロジック) は、非常に時間がかかります。
ヒントやアイデアは大歓迎です。
言葉の構成にもよると思います。たとえば、この男は、単語を順番に処理し、一般的なプレフィックスの計算を繰り返さないという事実に基づいて、実装を改善しました。しかし、あなたの 10,000 語すべてがまったく異なっていたら、それはあまり役に立ちません。Python で書かれているので、C に移植するには少し手間がかかるかもしれません。
そこには自作のアルゴリズムもいくつかあります（つまり、それについて書かれた公式の論文はありません）が、それでうまくいくかもしれません。
これには 2 つの一般的なアプローチがあり、私は両方についてブログを書いています。より簡単に実装できるのはBK-Treesです。これは、ツリーの関連部分のみを検索することにより、レーベンシュタイン距離に基づいてルックアップを高速化するツリー データ構造です。それらはおそらくあなたのユースケースには完全に十分でしょう.
より複雑ですが、より効率的なアプローチは、レーベンシュタイン オートマトンです。これは、ターゲット文字列のレーベンシュタイン距離 x 内にあるすべての単語を認識する NFA を構築し、それと辞書をロックステップで反復処理して、効果的にマージ結合を実行することによって機能します。