大規模なデータベースで長いおおよその部分文字列を検索しようとしています。たとえば、クエリは 1000 文字の部分文字列であり、数百の編集のレーベンシュタイン距離によって一致と異なる可能性があります。インデックス付き q-gram でこれができると聞いたことがありますが、実装の詳細はわかりません。Lucene でもできると聞いたことがありますが、Lucene のレーベンシュタイン アルゴリズムは何百回もの編集に対して十分に高速ですか? おそらく盗作検出の世界から何か？アドバイスをいただければ幸いです。
2 に答える
1
ここでは、Lucene は適切なツールではないようです。Mikos の素晴らしい提案に加えて、 AGREP、FASTA、およびLocality-Sensitive Hashing(LSH)について聞いたことがあります。効率的な方法は、最初に検索スペースを大幅に削減し、その後で残りの候補に対してより洗練されたスコアリングを行う必要があると私は信じています。
于 2010-08-08T11:55:35.013 に答える
1
Qグラムは1つのアプローチかもしれませんが、タンパク質、ヌクレオチドマッチなどに使用されるBlast、BlastPなどの他のアプローチがあります.
Simmetricsライブラリは、文字列距離アプローチの包括的なコレクションです。
于 2010-08-08T01:24:09.613 に答える