indexOfを使って文字列中の単語の出現箇所をすべて見つける
1.概要
大きなテキスト文字列で文字のパターン、つまり単語を検索するという面倒な作業は、さまざまな分野で行われています。例えば、バイオインフォマティクスでは、染色体のDNA断片を見つける必要があるかもしれません。
メディアでは、編集者は大量のテキストの中から特定のフレーズを見つけます。
データ監視は、データに埋め込まれた疑わしい単語を探すことによって詐欺またはスパムを検出します。
どのような状況においても、この検索は非常によく知られており、雑用を厄介なものにしているので、「Haystack問題の針」と一般的に呼ばれています。このチュートリアルでは、
__https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#indexOf-java.lang.String-int-を使用した簡単なアルゴリズムについて説明します。[indexOf（String str、int fromIndex）]文字列内の単語のすべての出現箇所を検索するためのJavaの
String__クラスのメソッド。
2.簡単なアルゴリズム
より大きなテキストの単語の出現回数を単純に数える代わりに、私たちのアルゴリズムはテキストの中で特定の単語が存在するすべての場所を見つけて識別します。この問題に対する私たちのアプローチは、短くてシンプルなので、
-
検索
は、テキスト
内の単語内でも単語を検索します.
したがって、「可能」という単語を検索している場合は、「快適」および「タブレット」でそれがわかります。
-
検索では大文字と小文字が区別されません** .
-
アルゴリズムは単純な文字列検索アプローチに基づいています. この
つまり、単語とテキスト文字列の文字の性質についてはわかっていないので、検索単語のインスタンスについてテキストのすべての場所を確認するために強引な力を使用します。
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. ソリューションをテストする
アルゴリズムをテストするために、シェイクスピアのハムレットからの有名な一節の抜粋を使用して、「or」という単語を検索します。
@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);
}テストを実行すると、期待どおりの結果が得られます。 「or」を検索すると、テキスト文字列にさまざまな方法で埋め込まれた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"
数学的には、アルゴリズムのBig-O表記は
O（m ** （n-m））
です。ここで、
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（）
は、部分文字列操作をコーディングすることなく、テキスト文字列に埋め込まれた文字シーケンスを見つけるための便利な方法です。
いつものように、この例の完全なコードベースはhttps://github.com/eugenp/tutorials/tree/master/java-strings[over on GitHub]です。