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

1. Обзор

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

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

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

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

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

1. Поиск найдет слово даже среди слов в тексте . Таким образом, если мы ищем слово «способный», то найдем его в словах «удобный» и «планшет».
2. Поиск будет нечувствительным к регистру .
3. Алгоритм основан на наивном подходе к поиску строк . Это означает, что, поскольку мы наивно относимся к природе символов в слове и текстовой строке, мы будем использовать грубую силу для проверки каждого места текста на предмет наличия искомого слова.

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. Тестирование решения

Чтобы проверить наш алгоритм, мы воспользуемся фрагментом известного отрывка из шекспировского «Гамлета» и найдем слово «или», которое встречается пять раз:

@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);
}

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

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*(nm)) , где m — длина слова, а n — длина текстовой строки. Этот подход может подойти для текстовых строк стога сена из нескольких тысяч символов, но будет невыносимо медленным, если есть миллиарды символов.

3. Улучшенный алгоритм

Простой пример выше демонстрирует наивный подход к поиску заданного слова в текстовой строке методом грубой силы. Таким образом, он будет работать для любого поискового слова и любого текста.

Если мы заранее знаем, что искомое слово не содержит повторяющихся символов, таких как «ааа», то мы можем написать несколько более эффективный алгоритм.

В этом случае мы можем безопасно не делать резервную копию, чтобы перепроверить каждое местоположение в текстовой строке в качестве потенциального начального местоположения. После того, как мы вызовем метод 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. Вывод

В этом руководстве мы представили алгоритм поиска без учета регистра, чтобы найти все варианты слова в текстовой строке большего размера. Но не позволяйте этому скрывать тот факт, что метод indexOf() класса Java String по своей природе чувствителен к регистру и может различать, например, «Bob» и «bob». ``

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

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