Как эффективно искать на строке

Question

У меня есть текст около 300 - 500 слов. Кроме того, я получил около 200 тыс. Ключевых слов, и я хочу знать, содержится ли каждое из ключевых слов в тексте. Строка содержит довольно медленно, есть ли способ предварительной обработки строки?

Я думал об использовании SuffixTree, но не уверен, что это лучший выбор.

Кроме того, есть ли хорошие библиотеки для этой задачи? Например, semanticdiscoverytoolkit имеет реализацию суффиксного дерева, но после добавления строки я не могу понять, как искать, содержится ли строка в дереве.

Привет,

Nico

Answer 1

вы можете попробовать алгоритм поиска строк rabin-karp. поскольку вы в основном выполняете сравнения хешей (целых чисел), производительность намного лучше, чем сравнения строк.

1. вычислить хеш ключевого слова
2. вычисляет переходящий хэш текста
3. сравните эти 2 хэша. если они совпадают, выполните фактическое сравнение строк.
4. продвигать позицию на 1 символ и повторять с шага 2, пока не дойдете до конца текста.

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

Answer 2

Вы можете использовать StringTokenizer, чтобы получить каждое из слов, а затем заполнить хэш-карту, которую вы проверяете впоследствии.Это требует прохождения каждого списка только один раз.Время поиска должно быть очень быстрым, что важно, учитывая количество ключевых слов, которые у вас есть.

Может быть, стоит профилировать этот метод для чего-то вроде Lucene.