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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

В задачах поиска традиционно принято обозначать шаблон поиска как 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].

Для чего нужно так много алгоритмов?[править | править исходный текст]

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

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

Как правило, в текстовом редакторе достаточно взять самый простой эвристический алгоритм наподобие Бойера-Мура-Хорспула — даже очень медленный ПК справится с поиском за доли секунды. Если же объём текста измеряется гигабайтами, либо поиск запущен на сервере, который обрабатывает множество запросов — приходится выбирать наиболее удачный алгоритм из доступных. Например, программы определения плагиата осуществляют онлайн проверку, используя алгоритмы поиска подстроки среди большого количества документов, хранящихся в собственной базе.

Алгоритмы[править | править исходный текст]

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

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

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

Основанные на сравнении как «чёрном ящике»[править | править исходный текст]

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

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

Название Предв. обработка Сложность Примечания
типичная макс.
Примитивный алгоритм Нет 2H O(Hn)
Алгоритм Бойера-Мура-Хорспула O(n+σ) ~ 2H / σ[2] O(Hn) Упрощённый до предела алгоритм Бойера-Мура; использует только видоизменённую эвристику стоп-символа — за стоп-символ всегда берётся символ haystack, расположенный напротив последнего символа needle.
Алгоритм быстрого поиска
=Алгоритм Санди
O(n+σ) <H O(Hn) Также использует исключительно эвристику стоп-символа — но за стоп-символ берётся символ haystack, идущий за последним символом needle.

Основанные на сравнении с начала[править | править исходный текст]

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

Название Предв. обработка Сложность Примечания
типичная макс.
Алгоритм Рабина-Карпа O(n) <H+n O(Hn) Хэширование позволяет серьёзно снизить сложность в среднем
Автоматный алгоритм
=Алгоритм Ахо-Корасик
O(nσ) = H Строит конечный автомат, который распознаёт язык, состоящий из одной-единственной строки. После небольшой модификации позволяет за один проход по haystack найти одну строку из нескольких.
Алгоритм Кнута-Морриса-Пратта O(n) ≤ 2H Один из первых алгоритмов с линейной оценкой в худшем случае. Модификация алгоритма Ахо-Корасик, строящая автомат неявно на основе префикс-функции.
Алгоритм Апостолико-Крошмора O(n) < H ≤1,5H
Алгоритм Shift-Or
=Bitap-алгоритм
=Двоичный алгоритм
O(n+σ) =H·ceil(n/w) Эффективен, если размер needle (в символах) не больше размера машинного слова (в битах, обозначен как w). Легко переделывается на приблизительный поиск, поиск нескольких строк.

Основанные на сравнении с конца[править | править исходный текст]

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

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

Проводящие сравнение в необычном порядке[править | править исходный текст]

Название Предв. обработка Сложность Примечания
типичная макс.
Непримитивный алгоритм const <H O(Hn) Простой алгоритм, сравнивающий второй символ, затем начиная с третьего в режиме «чёрного ящика», и, наконец, первый. При n[1]≠n[2][4] и несовпадении на второй-третьей стадии — сдвиг на 2 вправо.
Алгоритм Райты
=Алгоритм Бойера-Мура-Хорспула-Райты
O(n+σ) <H O(Hn) Эмпирический алгоритм, оптимизированный под английские тексты. Сравнивает последний символ, потом первый, потом средний, потом все остальные; при несовпадении — сдвиг по Хорспулу.


Примечания[править | править исходный текст]

  1. Brute force algorithm (англ.)
  2. Horspool algorithm
  3. Boyer-Moore algorithm
  4. Напомним, символы нумеруются с 1, как в Паскале.

Источники[править | править исходный текст]