Использование indexOf для поиска всех вхождений слова в строке

1. Обзор

Рутинная работа по поиску шаблона символов или слова в более крупной текстовой строке выполняется в различных полях. Например, в биоинформатике нам может потребоваться найти фрагмент ДНК в хромосоме.

В средствах массовой информации редакторы находят определенную фразу в объемном тексте. Наблюдение за данными обнаруживает мошенничество или спам, ища подозрительные слова, встроенные в данные.

В любом контексте поиск настолько хорошо известен и пугает рутиной, что в народе его называют “Проблемой иголки в стоге сена” . В этом уроке мы продемонстрируем простой алгоритм, который использует метод indexOf(String str, int fromIndex) класса Java String для поиска всех вхождений слова в строке.

2. Простой алгоритм

Вместо того, чтобы просто подсчитывать вхождения слова в более крупном тексте, наш алгоритм найдет и идентифицирует каждое место, где в тексте существует определенное слово. Наш подход к проблеме короток и прост, так что:

Поиск найдет слово даже внутри слов в тексте . Поэтому, если мы ищем слово “способный”, то мы найдем его в словах “удобный” и “планшет”.
Поиск будет осуществляться без учета регистра .
Алгоритм основан на наивном подходе поиска строк . Это означает, что, поскольку мы наивны в отношении природы символов в слове и текстовой строке, мы будем использовать грубую силу, чтобы проверить каждое местоположение текста на наличие экземпляра поискового слова.

2.1. Реализация

Теперь, когда мы определили параметры для вашего поиска, давайте напишем простое решение:

public class WordIndexer {

    public List findWord(String textString, String word) {
        List indexes = new ArrayList();
        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. Тестирование решения

Чтобы проверить наш алгоритм, мы используем фрагмент знаменитого отрывка из “Гамлета” Шекспира и ищем слово “или”, которое появляется пять раз:

@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 expectedResult = Arrays.asList(7, 122, 130, 221, 438);
    List actualResult = wordIndexer.findWord(theString, "or");
    assertEquals(expectedResult, actualResult);
}

Когда мы запускаем наш тест, мы получаем ожидаемый результат. Поиск “или” дает пять экземпляров, встроенных различными способами в текстовую строку:

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) .

Давайте рассмотрим эту расширенную версию более раннего метода find Word ( ) .

public List findWordUpgrade(String textString, String word) {
    List indexes = new ArrayList();
    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 class’ indexOf() по своей сути чувствителен к регистру и может различать, например, “Bob” и “bob”.

В целом, indexOf () – это удобный метод поиска последовательности символов, скрытой в текстовой строке, без какого-либо кодирования для манипуляций с подстроками.

Как обычно, полная кодовая база этого примера находится на GitHub .