java - Javaでの文字列検索アルゴリズム

Question

大量のデータで文字列照合を行っています。

編集：私はいくつかのオントロジーテキストファイルと大きなリストに含まれている単語を一致させています。オントロジーから各ファイルを取得し、各ファイル行の3番目の文字列とリストの任意の単語との一致を検索します。

私がしなければならないのは純粋なマッチングではない（結果が悪い）という事実を監視するのを間違えましたが、文字列が別の文字列内に含まれている場合にも結果を返す、より緩いマッチング関数が必要です。

私はこれをRadixTrieで行いました。非常に高速でうまく機能しましたが、トライは完全一致のみを返すため、今では私の作業は役に立たないと思います。：/

アルゴリズムは高速である必要がありますが、最優先事項ではなく、速度と複雑さで妥協します。

すべてのアドバイス/例/説明/リンクにとても感謝しています！

ありがとうございました！

score 4 · Accepted Answer

接尾辞木が役立つ場合があります（概念は試行に似ています）。

各文字列の前に^を付け、最後に$を付けて、追加されたすべての文字列の接尾辞木を作成します。スペース使用量はO（n）になり、おそらくトライの場合よりも悪くなります。

文字列sを検索する必要がある場合は、トライのようにO（| s |）時間で簡単に検索でき、得られる一致は部分文字列の一致になります（基本的に、文字列の接尾辞と一致します）。）。

~~申し訳ありませんが、便利なJava実装への参照がありません。~~

有用なスタックオーバーフローの答えが見つかりました：一般化されたサフィックスツリーJavaの実装

score 2 · Accepted Answer

BMアルゴリズムを使用して、単一パターンのテキストファイルを検索し、リストにあるすべてのパターンに対してこのアルゴリズムを繰り返すことができます。

もう1つの最善の解決策は、次のようなマルチパターン検索アルゴリズムを使用することです。Aho–Corasick文字列照合アルゴリズム

score 1 · Accepted Answer

正規表現は間違いなくあなたの最善の策です。それらは書くのが少し面倒かもしれませんが、理解できない一連のif / elseまたはswitchステートメントがなくても、より緩いマッチングを行うことができる唯一の方法です。

さらに、他の方法よりもはるかに高速になります。

score 0 · Accepted Answer

質問を正しく理解したかどうかは完全にはわかりませんが、正規表現でうまくいくようです。

score 0 · Accepted Answer

JavaでindexOfメソッドを使用してみませんか。メモリの可用性に従って、コンテンツを読みます。indexOfを実行して、必要なすべての行を取得します。次のコンテンツセットをロードします。

ファイルから読み取る場合は、nioストリームを使用します。

アイデアが悪いかもしれませんが、私はJavaを信じています。最良のアルゴリズムを使用します。

正規表現を使用するとよいでしょう。

5 に答える 5