webdevqa.jp.net

Javaのファジー文字列検索ライブラリ

私は高性能なJavaライブラリを探しています。

同様の文字列、レーベンシュタイン距離、Daitch-Mokotoff Soundex、n-gramなどを見つけるための多くのアルゴリズムがあります。

Java実装が存在しますか?実装の長所と短所はありますか?Lucene、他のソリューション、またはLuceneが最適ですか?

私はこれらを見つけました、誰かがそれらを使った経験がありますか?

67
dario

Commons Langには、 レーベンシュタイン距離 の実装があります。

Commons Codecには、 soundex および metaphone の実装があります。

36
JodaStephen

Apache Luceneを使用できますが、ユースケースによってはこれが重すぎる可能性があります。非常に単純なファジー検索では、使用するのが少し複雑になる場合があります(間違っている場合は修正してください)。インデックスを作成する必要があります。

簡単なオンライン(=インデックスを維持しない)アルゴリズムが必要な場合は、ファジー Bitapアルゴリズム を使用できます。私はJava here で実装を見つけました。これは、ほとんど自己説明的なシグネチャを持つ単一の比較的短いメソッドに収まるコードです。

public static List<Integer> find(String doc, String pattern, int k)

Apache Commons StringUtilsには、ファジー文字列マッチングのためのレーベンシュタインアルゴリズムの実装があります。 String.equalsのファジーバージョンとして見ることができます。BitapはString.indexOfのファジーバージョンに似ており、まだレーベンシュタイン距離測定を使用しています。通常、Levenshteinを単純に使用して、検索パターンと一致する可能性のある各部分文字列を比較するよりも効率的です。

  • Bitapアルゴリズムは、比較的小さなアルファベット、たとえばプレーンASCII。実際、私がリンクしたSimon Watiauバージョンは、非ASCII文字(> = 128)でArrayIndexOutOfBoundsExceptionをスローするため、これらを除外する必要があります。
  • 名前でメモリ内の人のリストを検索するアプリケーションでBimapを使用してみました。レーベンシュタイン距離が2の場合、誤検出が多すぎることがわかりました。 Levenhsteinの距離1はより効果的ですが、2つの文字を入れ替えるタイプミスを検出できません。 「ウィリアム」と「ウィラム」。これを解決するいくつかの方法を考えることができます。

    1. 正確な検索で一致するものが見つからない場合にのみファジー検索を実行します(これについてユーザーにメッセージを表示します)
    2. bitapを調整して、スワップの距離が2ではなくDamerau-Levenshteinの距離を使用するようにします。 wikipedia によると、これは可能ですが、Javaの既存の実装が見つかりませんでした。
    3. 「含む」の代わりに「startsWith」を実行します。 ファジー検索ツール には、Damerau-Levenshteinのプレフィックスバージョンが含まれていますが、ArrayIndexOutOfBoundsException
    4. アルゴリズムを調整して、完全一致のスコアが高い検索結果ランキングを導入します

    2または4を実行する場合は、とにかくLuceneのような適切なフルテキスト検索ライブラリを使用した方が良い場合があります。

  • ファジー検索の詳細については、 このブログ をご覧ください。作成者は、BitapOnlineSearcherと呼ばれる Javaでの実装 を作成しましたが、Java.io.ReaderをAlphabetクラスと一緒に使用する必要があります。 Javadocはロシア語で書かれています。
11
Henno Vermeulen

主に短い文字列を比較していて、ポータブルで軽量なものが必要な場合は、よく知られているpython algorithm fuzzywuzzy ported to Java を使用できます。

詳しくはこちらをご覧ください こちら

SimMetricsはおそらく必要なものです: http://sourceforge.net/projects/simmetrics/

編集距離のさまざまなフレーバーを計算するためのいくつかのアルゴリズムがあります。

Luceneは非常に強力な全文検索エンジンですが、FT検索はファジー文字列一致とまったく同じものではありません(たとえば、文字列のリストから、ある候補文字列に最も近いものを見つけることができます)。

8
Darren
3
Mond Raymond

Completely ライブラリを試すことができます。これは、テキスト前処理に依存してメモリ内インデックスを作成し、大規模なデータセットで(ファジー)検索に効率的に応答します。 Luceneやその他のフル機能のテキスト検索ライブラリとは異なり、APIは小さくて簡単に開始できます。

Bitapを試すことができます。私はANSI Cで書かれたbitapで遊んでいましたが、Java http://www.crosswire.org で実装されています。

1
Mojo Risin

Apache Lucene が唯一の方法だと思います。より良い検索ライブラリは知りません。

Apache Lucene(TM)は、完全にJavaで記述された高性能でフル機能のテキスト検索エンジンライブラリです。これは、フルテキスト検索を必要とするほぼすべてのアプリケーション、特にクロスプラットフォームに適したテクノロジーです。

0
Vugluskr