Поиск подстроки

Поиск информации — одно из основных использований компьютера. Одна из простейших задач поиска информации — поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна — она применяется в текстовых редакторах, СУБД, поисковых машинах…

В задачах поиска традиционно принято обозначать шаблон поиска как needle (англ. «иголка»), а строку, в которой ведётся поиск — как haystack (англ. «стог сена»). Также обозначим через Σ алфавит, на котором проводится поиск.

Несостоятельность примитивного алгоритма

Если считать, что строки нумеруются с 1, простейший алгоритм (англ. brute force algorithm, naïve algorigthm) выглядит так.

for i=0...|haystack|-|needle|
  for j=1...|needle|
    if haystack[i+j]<>needle[j] 
      then goto 1
  output("Найдено: ", i+1)
  1:

Простейший алгоритм поиска даже в лучшем случае проводит |haystack|−|needle|+1 сравнение; если же есть много частичных совпадений, скорость снижается до O(|haystack|·|needle|).

Показано, что примитивный алгоритм отрабатывает в среднем 2h сравнений.

Для чего нужно так много алгоритмов?

Программисту приходится выбирать нужный алгоритм в зависимости от таких факторов.

1. «Враждебность» пользователя. Другими словами: будет ли пользователь намеренно задавать данные, на которых алгоритм будет медленно работать? Существуют очень простые алгоритмы, оценка которых O(|haystack|·|needle|) в худшем случае, но на «обычных» данных количество сравнений намного меньше |haystack|. Только в 1990-е годы были созданы алгоритмы, дающие сложность O(|haystack|) в худшем случае и меньше |haystack| в среднем.
2. Архитектура процессора. Некоторые процессоры имеют автоинкрементные или SIMD-операции, которые позволяют быстро сравнить два участка ОЗУ (например, rep cmpsd на x86). На таких процессорах заманчиво применить алгоритм, который просто бы сравнивал needle с haystack — разумеется, не во всех позициях.
3. Размер алфавита. Многие алгоритмы (особенно основанные на сравнении с конца) имеют эвристики, связанные с несовпавшим символом. На больших алфавитах таблица символов будет занимать много памяти, на малых — соответствующая эвристика будет неэффективной.
4. Возможность проиндексировать haystack. Если таковая есть, поиск серьёзно ускорится.
5. Требуется ли одновременный поиск нескольких строк? Некоторые алгоритмы (например, алгоритм Ахо-Корасик) позволяют это.

Алгоритмы

Для сокращения обозначим:

• |Σ|=σ — размер алфавита.
• |haystack|=h — длина строки, в которой ведётся поиск.
• |needle|=n — длина шаблона поиска.

Вычислительная сложность определяется до первого совпадения. Жирным шрифтом выделены важнейшие с практической точки зрения алгоритмы.

Основанные на сравнении как «чёрном ящике»

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

К этой категории относится и примитивный алгоритм поиска.

Название	Предв. обработка	Сложность		Примечания
		типичная	макс.
Примитивный алгоритм	Нет	2h	O(hn)
Алгоритм Бойера-Мура-Хорспула	O(σ)	<h	O(hn)	Упрощённый до предела алгоритм Бойера-Мура

Основанные на сравнении с начала

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

Название	Предв. обработка	Сложность		Примечания
		типичная	макс.
Алгоритм Рабина-Карпа	O(n)	<h+n	O(hn)	Хэширование позволяет серьёзно снизить сложность в среднем
Алгоритм Кнута-Морриса-Пратта	O(n)		<2h+1	Один из первых линейных алгоритмов
Непримитивный алгоритм	O(1)	<h	O(hn)	Простой алгоритм, проводящий сначала сравнение первого символа, затем — сравнение остальных в режиме «чёрного ящика»
Автоматный алгоритм	O(nσ)	=h	=h	Строит конечный автомат, который распознаёт язык, состоящий из одной-единственной строки.
Алгоритм Апостолико-Крошмора	O(n)		≤1,5h

Основанные на сравнении с конца

В этом семействе алгоритмов needle движется по haystack слева направо, но сравнение этих строк друг с другом проводится справа налево. Сравнение справа налево позволяет в случае несовпадения сдвинуть needle не на одну позицию, а на несколько.

Название	Предв. обработка	Сложность		Примечания
		типичная	макс.
Алгоритм Бойера-Мура	O(n+σ)	<h	O(hn)	Стандартный алгоритм поиска подстроки в строке
Алгоритм Чжу-Такаоки	O(n+σ²)	<h	O(hn)	Алгоритм Бойера-Мура, оптимизированный под короткие алфавиты
Алгоритм Апостолико-Джанкарло	O(n+σ)	<h	≤1,5h	Одна из первых попыток получить <h в типичном случае и O(h) в худшем. Очень сложен в реализации.
Турбо-алгоритм Бойера-Мура	O(n+σ)	<h	≤2h	Один из наиболее эффективных алгоритмов, не дающих регрессии на «плохих» данных

Особые

• Алгоритм Ахо-Корасик — позволяет за один проход по haystack найти одну строку из нескольких.

Источники

• Большая подборка алгоритмов поиска подстроки (англ.)