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

2018-01-10T20:46:01Z

Oneone: Худшее время наивного

'''Поиск подстроки в строке''' (англ. ''String searching algorithm'') — класс алгоритмов над строками, которые позволяют найти паттерн (''pattern'') в тексте (''text'').
== Классификация алгоритмов поиска подстроки в строке ==

=== Сравнение — «чёрный ящик» ===

Во всех алгоритмах этого типа сравнение является «чёрным ящиком» для программиста.

Преимущества:
* позволяет использовать стандартные функции сравнения участков памяти (man *cmp(3)), которые, зачастую, оптимизированы под конкретное железо.

Недостатки:
* не выдается точка, в которой произошло несовпадение.

=== По порядку сравнения паттерна в тексте ===
==== Прямой ====

Преимущества:
* отсутствие регрессии на «плохих» данных.

Недостатки:
* не самая хорошая средняя асимптотическая сложность.

==== Обратный ====
Паттерн движется по тексту слева направо, но сравнение подстрок происходит справа налево.

Преимущества:
* при несовпадении позволяет перемещать паттерн по строке сразу на несколько символов.

Недостатки:
* производительность сильно зависит от данных.

==== Сравнение в необычном порядке ====
Специфические алгоритмы, основанные, как правило, на некоторых эмпирических наблюдениях над словарём.<ref>Например, [[Wikipedia:en:Raita Algorithm| Алгоритм Райты (англ.)]]</ref>

=== По количеству поисковых шаблонов ===

Сколько поисковых шаблонов может обработать алгоритм за один раз.

* один шаблон (англ. ''single pattern algorithms'')
* конечное количество шаблонов (англ. ''finite set of patterns'')
* бесконечное количество шаблонов (англ. ''infinite number of patterns'') (см. [[Теория формальных языков]])

=== По необходимости препроцессинга текста ===
Виды препроцессинга:
*[[Префикс-функция]]
*[[Z-функция]]
*[[Бор]]
*[[Суффиксный массив]]
Алгоритмы, использующие препроцессинг — одни из самых быстрых в этом классе.

== Сравнение алгоритмов ==
*<tex>|\Sigma| = \sigma</tex> — размер алфавита
*<tex>|text| = t</tex> — длина текста
*<tex>|pattern| = p</tex> — длина паттерна
*<tex>a</tex> — размер ответа(кол-во пар)
*<tex>m</tex> — суммарная длина всех паттернов

{|class="wikitable"
|+
!width="25%"|Название !! width="5%"| Среднее !! width="5%"| Худшее !! width="5%"|Препроцессинг !! width="5%"| Дополнительная память !! width="10%"| Кол-во поисковых шаблонов !! width="10%"| Порядок сравнения !! width="35%"| Описание

|- align = "center"
|[[Наивный алгоритм поиска подстроки в строке| Наивный алгоритм (Brute Force algorithm)]]
|<tex>O(p \cdot (t - p))</tex>
|<tex>O(t^2)</tex>
|
|<tex>O(1)</tex>
|Single
|Прямой
|Сравнение — «чёрный ящик». Если <tex>p</tex> достаточно мало по сравнению с <tex>t</tex>, то асимптотика будет близкой к <tex>O(t)</tex>, что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, Ctrl+F в браузерах)

|-align = "center"
|[[Z-функция| Поиск подстроки в строке с помощью Z-функции]]
|<tex>O(t)</tex>
|<tex>O(t)</tex>
|<tex>O(p + t)</tex>
|<tex>O(p)</tex>
|Single
|Прямой
|

|- align = "center"
|[[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа| Алгоритм Рабина-Карпа (Karp-Rabin algorithm)]]
|<tex>O(p + t)</tex>
|<tex>O(pt)</tex>
|<tex>O(p)</tex>
|<tex>O(1)</tex>
|Single / Finite
|Прямой
|Данный алгоритм использует хэширование, что снижает скорость в среднем. Можно модифицировать для поиска нескольких паттернов

|- align = "center"
|[[Алгоритм Кнута-Морриса-Пратта| Алгоритм Кнута-Морриса-Пратта (Knuth-Morris-Pratt algorith)]]
|<tex>O(p + t)</tex>
|<tex>O(p + t)</tex>
|<tex>O(p)</tex>
|<tex>O(p)</tex>
|Single
|Прямой
|Использует [[Префикс-функция| префикс-функцию]]

|-align = "center"
|[[Алгоритм Колусси| Алгоритм Колусси (Colussi algorithm)]]
|<tex>O(t)</tex>
|<tex>O(t)</tex>
|<tex>O(p)</tex>
|<tex>O(p)</tex>
|Single
|Прямой / Обратный
|Оптимизация [[Алгоритм Кнута-Морриса-Пратта| Алгоритма Кнута-Морриса-Пратта]] использует как прямой, так и обратный обход

|- align = "center"
|[[Алгоритм Ахо-Корасик| Алгоритм Ахо-Корасик (Aho–Corasick string matching algorithm)]]
|<tex>O(m + t + a)</tex>
|<tex>O(t)</tex>
| <tex>O(m)</tex>
|<tex>O(m\sigma)</tex>
|Finite
|Прямой
|Строит конечный автомат. Можно хранить таблицу переходов как индексный массив (array), а можно как [[Красно-черное дерево]]. В последнем случае уменьшится расход памяти, но ухудшится асимптотика

|-align = "center"
|[[Алгоритм Shift-Or]]
|<tex>O(t)</tex>
|<tex>O(t \cdot \dfrac{n}{w})</tex> <tex>w</tex> — размер машинного слова
|<tex>O(p + \sigma)</tex>
|<tex>O(p + \sigma)</tex>
|Single
|Прямой
|Использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если <tex>p \leqslant w</tex>. Иначе деградирует и по памяти, и по сложности

|-align = "center"
|[[Алгоритм Бойера-Мура| Алгоритм Бойера-Мура (Boyer-Moore algorithm)]]
|<tex>O(t)</tex>
|<tex>O(pt)</tex>
|<tex>O(p + \sigma)</tex>
|<tex>O(p + \sigma)</tex>
|Single
|Обратный
|Считается наиболее быстрым из алгоритмов общего назначения. Использует эвристики. Существует большое количество оптимизаций<ref>Например, [http://www-igm.univ-mlv.fr/~lecroq/string/node15.html#SECTION00150 Турбо-алгоритм Бойера-Мура (Turbo-BM algorithm)]</ref>

|-align = "center"
|[[Алгоритм поиска подстроки в строке с помощью суффиксного массива| Поиск подстроки в строке с помощью суффиксного массива (Suffix array)]]
|<tex>O(p\log t)</tex>
|<tex>O(p\log t)</tex>
|<tex>O(t)</tex>
|<tex>O(t)</tex>
|Single
|Прямой
|Использует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix (lcp)]], то можно уменьшить асимптотику до <tex>O(p + \log t)</tex>. Суффиксный массив можно строить[[Построение суффиксного массива с помощью стандартных методов сортировки| стандартными способами]] или [[Алгоритм Каркайнена-Сандерса| алгоритмом Каркайнена-Сандерса]]. Асимптотика приведена для построения суффиксного массива с помощью алгоритма Каркайнена-Сандерса

|-align = "center"
|[[Сжатое суффиксное дерево| Поиск подстроки в строке с помощью суффиксного дерева (Suffix tree)]]
|<tex>O(p)</tex>
|<tex>O(p)</tex>
|<tex>O(t)</tex>
|<tex>O(t)</tex>
|Single
|Прямой
|Позволяет выполнять поиск подстроки в строке за линейное время

|- align = "center"
|[[Алгоритм Апостолико-Крочемора| Алгоритм Апостолико-Крочемора ( Apostolico-Crochemore algorithm)]]
|<tex>O(t)</tex>
|<tex>O(t)</tex>
|<tex>O(p)</tex>
|<tex>O(p)</tex>
|Single
|Прямой
|В худшем случае выполнит <tex>\dfrac{3}{2} n</tex> сравнений.
|}

== Примечания ==

<references />

== Источники информации ==
* [[wikipedia:ru:Поиск_подстроки | Википедия {{---}} Поиск подстроки]]
* [[Wikipedia:en:String_searching_algorithm | Википедия {{---}} String searching algorithm]]
* [http://www-igm.univ-mlv.fr/~lecroq/string/index.html ESMAJ] — (англ.) Большое количество разных алгоритмов поиска подстроки в строке. Многие из них в данной статье не описаны.

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Поиск подстроки в строке]]

Викиконспекты - Вклад участника [ru]

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