76

あいまい文字列検索用の高性能 Java ライブラリを探しています。

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

どのような Java 実装が存在しますか? それらの長所と短所は？私は Lucene を知っていますが、他のソリューションまたは Lucene が最適ですか?

私はこれらを見つけました、誰もそれらの経験がありますか？

4

8 に答える 8

41

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

Commons Codecには、soundexとmetaphoneが実装されています。

于 2008-11-29T14:58:12.067 に答える
18

主に短い文字列を比較していて、移植可能で軽量なものが必要な場合は、 Java に移植されたよく知られた Python アルゴリズム fuzzywuzzy を使用できます。

詳細については、こちらをご覧ください。

于 2016-09-14T17:54:33.570 に答える
11

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

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

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

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

注:

  • Bitap アルゴリズムは、プレーン ASCII などの比較的小さなアルファベットに最も適しているようです。実際、私がリンクした Simon Watiau のバージョンでArrayIndexOutOfBoundsExceptionは非 ASCII 文字 (>= 128) がスローされるため、これらを除外する必要があります。

  • アプリケーションで Bimap を使用して、メモリ内の人物リストを名前で検索してみました。レーベンシュタイン距離が 2 の場合、偽陽性が多すぎることがわかりました。レーベンシュタイン距離 1 の方がうまく機能しますが、「William」と「William」などの 2 文字を入れ替えたタイプミスは検出できません。これを解決するいくつかの方法を考えることができます。

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

    2 や 4 を行う場合は、とにかく Lucene のような適切な全文検索ライブラリを使用する方がよい場合があります。

  • あいまい検索の詳細については、このブログを参照してください。作成者は Java でと呼ばれる実装も作成しましたが、Alphabet クラスと一緒BitapOnlineSearcherに使用する必要があります。java.io.ReaderJavadoc はロシア語で書かれています。
于 2015-10-14T12:43:57.323 に答える
9

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

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

Lucene は非常に強力な全文検索エンジンですが、FT 検索はファジー文字列マッチングとまったく同じではありません (たとえば、文字列のリストが与えられた場合、候補文字列に最も類似するものを見つけます)。

于 2008-12-18T17:18:51.650 に答える
1

ビットタップを試すことができます。私は ANSI C で書かれた bitap で遊んでいましたが、かなり高速で、http://www.crosswire.orgに Java 実装があります。

于 2010-04-06T14:48:02.377 に答える
1

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

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

于 2008-11-29T13:40:29.510 に答える