Быстрый алгоритм поиска подстрок в строке
Мне нужен эффективный алгоритм (или библиотека), который я могу использовать в Java для поиска подстрок в строке.
Что я хотел бы сделать, это:
Учитывая входную строку -INSTR:
"BCDEFGH"
И набор строк-кандидатов -CAND:
"AB", "CDE", "FG", "H", "IJ"
Найти любойCAND строки, которые совпадают как подстроки вINSTR
В этом примере я бы сопоставил «CDE», «FG» и «H» (но не «AB» и «IJ»)
Может быть много тысяч строк-кандидатов (в CAND), но что более важно, я буду выполнять этот поиск много миллионов раз, поэтому он должен быть БЫСТРОМ.
Я хотел бы работать с массивами символов. Кроме того, я не интересуюсь архитектурными решениями, такими как распределение поиска - просто самая эффективная функция / алгоритм для локального выполнения.
Кроме того, все строки в CAND и INSTR будут относительно небольшими (<50 символов) - т.е. целевая строка INSTR НЕ длинна относительно строк-кандидатов.
Обновить Я должен был упомянуть, что набор строк CAND инвариантен для всех значений INSTR.
Обновить Мне нужно только знать, что был матч - и мне не нужно знать, что это был за матч.
Окончательное обновление Я решил попробовать AhoCorsick и Rabin-Karp, из-за простоты реализации. Поскольку у меня есть шаблоны переменной длины, я использовал модифицированный шаблон Рабина-Карпа, который хэширует первые n символов каждого шаблона, где n - длина наименьшего шаблона, тогда N была длиной моего окна поиска подвижной подстроки. Для Aho Corsick я использовалэто
В моем тесте я искал 1000 шаблонов в двух документах, в новостных статьях, в среднем по 1000 итераций и т. Д.
AhoCorsick: 1
RabinKarp: 1.8
Наивный поиск (проверьте каждый шаблон и используйте string.contains): 50
* Некоторые ресурсы, описывающие алгоритмы, упомянутые в ответах ниже:
http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module5/module5.html
http://www.cs.princeton.edu/courses/archive/spr09/cos226/lectures/18SubstringSearch-2x2.pdf