fuzzy-search - 大規模な文字列データベースで文字列の最もあいまいな一致を見つける方法

Question

100 万を超えるアイテム (潜在的にはそれ以上) を保持する文字列 (任意の長さ) のデータベースがあります。

ユーザーが指定した文字列をデータベース全体と比較し、存在する場合は同一の文字列を取得するか、最も近いあいまい一致 (60% 以上の類似性) を返す必要があります。検索時間は、理想的には 1 秒未満である必要があります。

私の考えは、長さに基づいてデータベースから候補を絞り込んだ後、各データベース文字列を検索文字列と比較するために編集距離を使用することです。

ただし、この操作を頻繁に実行する必要があるため、db 文字列のインデックスを構築してメモリに保持し、db を直接ではなくインデックスをクエリすることを考えています。

この問題に別の方法でアプローチする方法、またはメモリ内インデックスを構築する方法についてのアイデアはありますか?

score 5 · Accepted Answer

Lucene ( http://lucene.apache.org/ ) もレーベンシュタイン編集距離を実装しています。

score 2 · Accepted Answer

データベースシステムについては言及していませんが、PostrgreSQLの場合は、次のcontribモジュールを使用できます。trgm-PostgreSQLのトリグラムマッチング

pg_trgm contribモジュールは、トリグラムマッチングに基づいてテキストの類似性を判断するための関数とインデックスクラスを提供します。

score 2 · Accepted Answer

データベースでサポートされている場合は、全文検索を使用する必要があります。それ以外の場合は、lucene などのインデクサーとそのさまざまな実装を使用できます。

score 0 · Accepted Answer

データ量が多いため、レコードを挿入するときに、音声アルゴリズムの値を計算してインデックス付きの列に格納し、選択クエリをその列の範囲内に制限 (WHERE 句) します。

score 0 · Accepted Answer

SOUNDEX ハッシュ (多くの SQL データベースエンジンに組み込まれている) を計算し、それによってインデックスを作成します。

SOUNDEX は単語の音に基づくハッシュであるため、同じ単語のスペルミスは同じ SOUNDEX ハッシュを持つ可能性があります。

次に、検索文字列の SOUNDEX ハッシュを見つけて照合します。

score 0 · Accepted Answer

関連するアルゴリズムの非常に詳細な説明は、Dan Gusfield著Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biologyにあります。

score 0 · Accepted Answer

一部の DBMS ではレーベンシュタインアルゴリズムが実装されています。

7 に答える 7