Эффективный текстовый поиск строк

Question

Я хотел бы создать метод, который ищет небольшую строку текста (обычно не более 256 символов) для существования любого из примерно 20 разных слов. Если он находит одно в тексте независимо от случая, он возвращает true.

Метод будет выполнен совсем немного (не сумасшедшая сумма), поэтому он должен быть как можно более эффективным. Что вы предлагаете лучше всего здесь?

20 слов не меняются. Они статичны. Но текст для сканирования делает.

Answer 1

Я бы предложил: добавить все слова во входной текст в Set - это всего лишь 256 символов, и их добавление - это операция O(n).

После этого вы можете проверить каждое из 20 слов для членства, используя операцию Set, которая составляет O(1).

Answer 2

В классе String уже есть много способов делать подобные вещи. Например, метод indexOf будет решить вашу проблему:

String str = "blahblahtestblah"; 
int result = str.indexOf("test"); 

result будет содержать -1, если строка не содержит слово «тест». Я не уверен, что это достаточно эффективно для вас, но я бы начал здесь, поскольку он уже реализован!

Answer 3

Предполагая, что эти 20 слов находятся в Set<String> и все в нижнем регистре, то это так же просто, как:

public final boolean containsWord(final String input) 
{ 
    final String s = input.toLowerCase(); 
    for (final String word: wordSet) 
     if (s.indexOf(word) != -1) 
      return true; 
    return false; 
} 

Answer 4

С 20 слов для поиска не меняются, один из самых быстрых способов поиска они компилируют регулярное выражение, которое соответствует им и повторно использует его на разных входах. Сложность сопоставления регулярного выражения с заданной строкой линейна по отношению к длине строки для простых регулярных выражений, которые не требуют обратного отслеживания. В вашем случае длина ограничена, поэтому это O (1).

Answer 5

Я хотел бы сделать следующее:

String longStr //the string to search into 
ArrayList<String> words; //the words to check 

Iterator<String> iter = words.iterator(); 
while(iter.hasNext()) 
{ 
    if(longStr.contains(iter.next())) 
     return true;  
} 
return false; 

Answer 6

Вы можете получить все слова в список, сортировать и использовать Collections.binarySearch (...). Вы потеряете при сортировке, но binarySearch - log (n).

Answer 7

Если вы хотите найти несколько разных целей одновременно, то возможно Rabin-Karp algorithm. Если это особенно эффективно, если в списке из 20 целей имеется только несколько разных длин слов. Один проход через строку найдет все совпадения заданной длины.

Answer 8

Хорошо. Спасибо, что ответили и комментировали всех. Я понимаю, что вопрос, который я задал, может иметь широкие и разнообразные ответы. Но это то, что я в конечном итоге использовал, потому что производительность была очень важна, поэтому использование стандартных коллекций просто не сократит горчицу.

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

Если кому-то интересно, есть video here, вкратце объясняющий, как работает Патрисия Три. Вы поймете, почему это так показательно после просмотра. Также существует реализация Java структуры данных на github here.