Levenshtein距離で近い文字列を検索するためのデータ構造

Question

たとえば、英語の単語から始めて、 "light"や "tight"などの文字列を1回高速に検索できる構造体/アルゴリズムがあります。単語 "right"をクエリとして使用しますか？つまり、クエリ文字列にLevenshteinの距離が小さい文字列を取得したいとします。

Answer 1

私は、O（1）時間にインデックスを作成してアクセスできる類似性のキャッシュを事前に構築するのが最速の方法だと考えています。このトリックは、一般的なスペルミスがキャッシュに追加されるのを発見することです。かなり大きくなる可能性があります。

私は、Googleが幅広い統計クエリ検索データを使って同様のことをすると思います。

Answer 2

長さnとmの文字列の場合、Levenshtein距離を計算するとO(nm)なので、すべてのLevenshtein距離を計算する単純なアプローチは非常に高価です。

しかし、Levenshteinアルゴリズムを視覚化すると、基本的に編集距離でn * mの表が塗りつぶされます。しかし、同じ数文字（接頭辞）で始まる単語の場合、Levenshteinテーブルの最初の数行は同じになります。 （もちろんクエリ文字列を修正してください）

trie (also called prefix tree)を使用することをお勧めします。クエリ文字列を読み取り、Levenshtein行のトライを作成します。その後、簡単にトラバースしてクエリ文字列に近い文字列を見つけることができます。

（これはは、新しいクエリ文字列のための新しいトライを構築する必要があることを意味します。私はすべてのペア距離に対しても同様に魅力的な構造があるとは思わない。）私は思っ

私は最近、素晴らしいpythonの実装でこれについての記事を見ました。見つけたらリンクを追加します。 編集：Here it is, on Steve Hanov's blog.

Answer 3

BK-treeデータ構造がここで適切かもしれません。これは、「クエリーワードから編集距離k以内のすべての単語は何ですか？」という形式のクエリーを効率的にサポートするように設計されています。その性能保証は合理的に優れており、実装するのが難しくありません。

希望すると便利です。