Javaでの文字列のファジー文字列一致

Question

NoSQL DBに格納されている文字列のリストが非常に大きいです。入力クエリは文字列であり、この文字列がリストにあるかどうかをチェックしたいと思います。完全一致の場合、これは非常に簡単です。 NoSQL DBがStringを主キーとして持つことがあり、その文字列を主キーとするレコードがあるかどうかをチェックします。しかし、私はファジーマッチもチェックする必要があります。

リスト内のすべての文字列をトラバースし、入力文字列とリスト内の文字列との距離を調べる方法がありますが、この方法はO（n）の複雑さをもたらし、リストのサイズは非常に大きくなります）さらに増加する可能性があります。このアプローチにより、私のソリューションの待ち時間が長くなります。

この問題を解決するには、より良い方法がありますか？

Answer 1

まず最初に、もしあなたがやっていることがあれば、検索エンジンを使うべきです（ElasticSearchはほとんどデフォルトです）。彼らはこれで良いですし、あなたは再び発明車輪ではありません。

第2に、お探しのテクニックはstemmingです。元のStringと一緒に、正規化された文字列をDBに保存します。同じメカニズムで検索クエリを正規化します。そうすれば、より良い検索結果が得られます。明らかに、これは検索エンジンがフードの下で使用する技術の1つです。

Answer 2

Solr（またはLucene）を使用すると、適切なソリューションが得られますか？

Luceneは、Levenshtein DistanceまたはEdit Distanceアルゴリズムに基づいてファジー検索をサポートしています。ファジィ検索を行うには、単一単語用語の最後にティルダ「〜」記号を使用します。この検索は、泡のような用語を検索し、ローミングします

roam~ 

：例は、「ローミング」することと似たスペルの用語を検索するためにあいまい検索を使用しています。

Lucene 1.9から追加の（オプションの）パラメータで必要な類似性を指定できます。値は0と1の間であり、値が1に近いほど類似度の高い項のみが一致します。たとえば：

roam~0.8 

https://lucene.apache.org/core/2_9_4/queryparsersyntax.html

Answer 3

ファジーマッチングは、あなたが発見した理由のために複雑になります。検索用語とデータベース用語の組み合わせごとに距離メトリックを計算することは、パフォーマンス上の理由から実用的ではありません。

これに対する解決策は、通常、nグラムインデックスを使用することです。これはスタンドアロンで結果を出すために使うことも、計算する距離スコアが小さくなるように可能な結果のサイズを小さくするフィルターとして使うこともできます。

基本的に、単語 "スタック"があれば、 "s"、 "st"、 "sta"、 "ack"、 "ck"、 "k"などのnグラム（通常はトリグラム） "あなたのデータベース内のものをデータベース行に対して索引付けします。入力に対して同じ処理を行い、同じnグラムが一致するデータベース行を探します。

これはすべて複雑で、あなたのためにnグラムの処理を行うLucene/Solrなどの既存の実装を使用するのが最善の方法です。

Return only results that match enough NGrams with Solr

データベースによっては、nグラムのマッチングを実装するように見える：私は独自のソリューションで動作しますが、関連するかもしれないstackoverflowの質問があるように私はそれを自分自身を使用していません。ここではそのいくつかの議論を提供するSybaseのページへのリンクです：

Sybase n-gram text index

残念ながら、nグラムの議論は長い記事になると、私は時間がありません。おそらく、stackoverflowや他のサイトのどこかで議論されているでしょう。私はその言葉をグーグルにし、それについて読むことを提案する。