indexOfを使用して文字列内の単語のすべての出現箇所を検索する

投稿日: 2019-10-18 2022-11-07
タグ: Java, Java Search, Java String

1. 概要

より大きなテキスト文字列で文字のパターンまたは単語を検索するという雑用は、さまざまなフィールドで行われます。たとえば、バイオインフォマティクスでは、染色体内のDNAスニペットを見つける必要がある場合があります。

メディアでは、編集者は膨大なテキストの特定のフレーズを見つけます。データ監視は、データに埋め込まれている疑わしい単語を探すことにより、詐欺やスパムを検出します。

いずれにせよ、この検索は非常によく知られており、面倒な雑用であるため、一般に「干し草の山の問題の針」と呼ばれています。このチュートリアルでは、Java StringクラスのindexOf（String str、int fromIndex）メソッドを使用して、内の単語のすべての出現箇所を検索する簡単なアルゴリズムを示します。文字列。

2. シンプルなアルゴリズム

大きなテキスト内の単語の出現を単純にカウントする代わりに、私たちのアルゴリズムは、特定の単語がテキスト内に存在するすべての場所を見つけて識別します。問題への私たちのアプローチは短くて単純なので、次のようになります。

を検索すると、テキストの単語内でもその単語が見つかります。したがって、「able」という単語を検索すると、「comfortable」と「tablet」で見つかります。
の検索では、大文字と小文字は区別されません。
アルゴリズムは、ナイーブな文字列検索アプローチに基づいています。これは、単語とテキスト文字列の文字の性質についてはナイーブなので、ブルートフォースを使用して、検索単語のインスタンスのテキストのすべての場所をチェックすることを意味します。

2.1. 実装

検索用のパラメーターを定義したので、簡単なソリューションを作成しましょう。

public class WordIndexer {

    public List<Integer> findWord(String textString, String word) {
        List<Integer> indexes = new ArrayList<Integer>();
        String lowerCaseTextString = textString.toLowerCase();
        String lowerCaseWord = word.toLowerCase();

        int index = 0;
        while(index != -1){
            index = lowerCaseTextString.indexOf(lowerCaseWord, index);
            if (index != -1) {
                indexes.add(index);
                index++;
            }
        }
        return indexes;
    }
}

2.2. ソリューションのテスト

アルゴリズムをテストするために、シェイクスピアのハムレットの有名な一節の抜粋を使用して、5回出現する「または」という単語を検索します。

@Test
public void givenWord_whenSearching_thenFindAllIndexedLocations() {
    String theString;
    WordIndexer wordIndexer = new WordIndexer();

    theString = "To be, or not to be: that is the question: "
      + "Whether 'tis nobler in the mind to suffer "
      + "The slings and arrows of outrageous fortune, "
      + "Or to take arms against a sea of troubles, "
      + "And by opposing end them? To die: to sleep; "
      + "No more; and by a sleep to say we end "
      + "The heart-ache and the thousand natural shocks "
      + "That flesh is heir to, 'tis a consummation "
      + "Devoutly to be wish'd. To die, to sleep; "
      + "To sleep: perchance to dream: ay, there's the rub: "
      + "For in that sleep of death what dreams may come,";

    List<Integer> expectedResult = Arrays.asList(7, 122, 130, 221, 438);
    List<Integer> actualResult = wordIndexer.findWord(theString, "or");
    assertEquals(expectedResult, actualResult);
}

テストを実行すると、期待どおりの結果が得られます。 「または」を検索すると、テキスト文字列にさまざまな方法で埋め込まれた5つのインスタンスが生成されます。

index of 7, in "or"
index of 122, in "fortune"
index of 130, in "Or
index of 221, in "more"
index of 438, in "For"

数学的には、アルゴリズムには O（m *（nm））のBig-O表記があります。ここで、 m は単語の長さ、 n テキスト文字列の長さです。このアプローチは、数千文字の干し草の山のテキスト文字列には適切かもしれませんが、数十億文字の場合は耐えられないほど遅くなります。

3. 改善されたアルゴリズム

上記の簡単な例は、テキスト文字列内の特定の単語を検索するための素朴で力強いアプローチを示しています。そのため、あらゆる検索ワードとあらゆるテキストで機能します。

検索ワードに「aaa」などの繰り返しパターンの文字が含まれていないことが事前にわかっている場合は、もう少し効率的なアルゴリズムを作成できます。

この場合、バックアップを実行して、テキスト文字列内のすべての場所を潜在的な開始場所として再チェックすることを安全に回避できます。 indexOf（）メソッドを呼び出した後、見つかった最新のオカレンスの終わりの直後の場所にスライドします。この単純な調整により、 O（n）の最良のシナリオが得られます。

以前のfindWord（）メソッドのこの拡張バージョンを見てみましょう。

public List<Integer> findWordUpgrade(String textString, String word) {
    List<Integer> indexes = new ArrayList<Integer>();
    StringBuilder output = new StringBuilder();
    String lowerCaseTextString = textString.toLowerCase();
    String lowerCaseWord = word.toLowerCase();
    int wordLength = 0;

    int index = 0;
    while(index != -1){
        index = lowerCaseTextString.indexOf(lowerCaseWord, index + wordLength);  // Slight improvement
        if (index != -1) {
            indexes.add(index);
        }
        wordLength = word.length();
    }
    return indexes;
}

4. 結論

このチュートリアルでは、大文字と小文字を区別しない検索アルゴリズムを使用して、より大きなテキスト文字列内の単語のすべてのバリエーションを検索しました。ただし、Java StringクラスのindexOf（）メソッドは本質的に大文字と小文字を区別し、「Bob」と「bob」を区別できるという事実を隠さないでください。例えば。

全体として、 indexOf（）は、部分文字列操作のコーディングを行わずに、テキスト文字列に埋め込まれた文字シーケンスを見つけるための便利なメソッドです。

いつものように、この例の完全なコードベースは、GitHub上のです。

getdocs

13036