たとえば、英単語のセットから始めて、「right」という単語をクエリとして使用して、「light」や「tight」などの文字列を 1 回高速に取得できる構造/アルゴリズムはありますか? つまり、クエリ文字列とのレーベンシュタイン距離が小さい文字列を取得したいのです。
1547 次
3 に答える
4
ここでは、 BK-treeデータ構造が適切かもしれません。これは、「クエリ ワードから編集距離 k 以下の範囲内にあるすべての単語は?」という形式のクエリを効率的にサポートするように設計されています。そのパフォーマンスの保証はかなり良好であり、実装するのはそれほど難しくありません。
お役に立てれば！
于 2013-02-13T09:11:25.667 に答える
1
レーベンシュタイン距離の計算O(nm)は長さ n と m の文字列に対して行われるため、すべてのレーベンシュタイン距離を計算する単純な方法L(querystring, otherstring)は非常にコストがかかります。
ただし、レーベンシュタイン アルゴリズムを視覚化すると、基本的に n*m テーブルに編集距離が入力されます。ただし、同じ数文字 (接頭辞) で始まる単語の場合、レーベンシュタイン テーブルの最初の数行は同じになります。(もちろん、クエリ文字列を修正します。)
これは、トライ (プレフィックス ツリーとも呼ばれます)を使用することを提案します。クエリ文字列を読み取り、レーベンシュタイン行のトライを構築します。その後、簡単にトラバースして、クエリ文字列に近い文字列を見つけることができます。
(これは、新しいクエリ文字列に対して新しいトライを作成する必要があることを意味します。すべてのペアの距離について同様に興味深い構造はないと思います。)
私は最近、素敵な python 実装でこれに関する記事を見たと思いました。見つけたらリンクを追加します。編集: これは、Steve Hanov のブログにあります。
于 2013-02-13T02:34:22.497 に答える
0
最速の方法は、インデックスを作成して O(1) 時間でアクセスできる類似性のキャッシュを事前に構築することだと思います。秘訣は、よくあるスペルミスを見つけてキャッシュに追加することです。キャッシュはかなり大きくなる可能性があります。
Google は、幅広い統計クエリ検索データを使用して同様のことを行うと思います。
于 2013-02-13T02:17:53.887 に答える