34
правки
Изменения
Новая страница: «''Поиск подстроки в строке'' (''String searching algorithm'') — класс алгоритмов над строками, которые п...»
''Поиск подстроки в строке'' (''String searching algorithm'') — класс алгоритмов над строками, которые позволяют найти паттерн (''needle'') в тексте (''haystack'').
== Классификация алгоритмов поиска подстроки в строке ==
=== Сравнение — «чёрный ящик» ===
Во всех алгоритмах этого типа сравнение является черным ящиком для программиста.
* + Позволяет использовать стандартные функции сравнения участков памяти (man *cmp(3)), которые, зачастую, оптимизированы под конкретное железо.
* - Не выдается точка, в которой произошло несовпадение.
=== По порядку сравнения паттерна в тексте ===
==== Прямой ====
* + Отсутсвие регрессии на «плохих» данных.
* - Не самая хорошая средняя ассимптотическая сложность.
==== Обратный ====
Паттерн движется по тексту слева на право, но сравнение подстрок происходит с права на лево.
* + При несовпадении позволяет перемещать паттерн по строке сразу на несколько символов
==== Сравнение в необычном порядке ====
Специфические алгоритмы, основанные, как правило, на некоторых эмпирических наблюдениях над словарём.
=== По количеству поисковых шаблонов ===
#Один шаблон (''Single pattern algorithms'')
#Конечное количество шаблонов (''finite set of patterns'')
#Бесконечное количество шаблонов (Регулярные грамматики/regexp'ы)
=== По необходимости препроцессинга текста ===
Виды препроцессинга:
*[[Префикс-функция]]
*[[Z-функция]]
*[[Бор]]
*[[Суффиксный_массив]]
Алгоритмы, использующие препроцессинг — одни из самых быстрых в этом классе.
== Сравнение алгоритмов ==
*<tex>|\Sigma| = \sigma</tex> — размер алфавита
*<tex>|haystack| = h</tex> — длина текста
*<tex>|needle| = n</tex> — длина паттерна
*<tex>a</tex> — размер ответа(кол-во пар)
*<tex>m</tex> — суммарная длина всх паттернов
{|class="wikitable"
|+
!width="25%"|Название !! width="8%"| Среднее !! width="8%"| Худшее !! width="8%"|Необходимость препроцессинга !! width="8%"| Дополнительная память !! width="10%"| Кол-во поисковых шаблонов !! width="10%"| Порядок сравнения !! width="35%"| Описание
|- align = "center"
|[[Наивный алгоритм поиска подстроки в строке| Наивный алгоритм <br>(Brute Force algorithm)]]
|<tex>O(n \cdot (h - n))</tex>
|<tex>O(n^2)</tex>
|Нет
|<tex>O(1)</tex>
|Single
|Прямой
|Сравнение — «чёрный ящик». Если <tex>n</tex> достаточно мало по сравнению с <tex>h</tex>, то ассимптотика будет близкой к O(h), что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, ctrl+F в браузерах)
|- align = "center"
|[http://www-igm.univ-mlv.fr/~lecroq/string/node18.html#SECTION00180| Алгоритм Бойера-Мура-Хорспула <br>(Horspool algorithm)]
|<tex>O(nh)</tex>
|<tex>O(nh)</tex>
|Да <br> <tex>O(n + \sigma)</tex>
|<tex>O(\sigma)</tex>
|Single
|Прямой
|В самой простой реализации использует только эвристику стоп-символа и относится к алгоритмом с сравнением — «чёрным ящиком».
|- align = "center"
|[[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа| Алгоритм Рабина-Карпа <br>(Karp-Rabin algorithm)]]
|<tex>O(n + h)</tex>
|<tex>O(nh)</tex>
|Да <br> <tex>O(n)</tex>
|<tex>O(1)</tex>
|Single
|Прямой
|Данный алгоритм использует хэширование, что снижает скорость в среднем.
|- align = "center"
|[[Алгоритм Кнута-Морриса-Пратта| Алгоритм Кнута-Морриса-Пратта <br>(Knuth-Morris-Pratt algorith)]]
|<tex>O(n + h)</tex>
|<tex>O(n + h)</tex>
|Да <br> <tex>O(n)</tex>
|<tex>O(n)</tex>
|Single
|Прямой
|Использует [[Префикс-функция| префикс-функцию]]
|- align = "center"
|[[Алгоритм Ахо-Корасик| Алгоритм Ахо-Корасик <br>(Aho–Corasick string matching algorithm)]]
|<tex>O(m + h + a)</tex>
|<tex>O(h)</tex>
|Да <br> <tex>O(m)</tex>
|<tex>O(m\sigma)</tex>
|finite
|Прямой
|Строит конечный автомат
|}
== Классификация алгоритмов поиска подстроки в строке ==
=== Сравнение — «чёрный ящик» ===
Во всех алгоритмах этого типа сравнение является черным ящиком для программиста.
* + Позволяет использовать стандартные функции сравнения участков памяти (man *cmp(3)), которые, зачастую, оптимизированы под конкретное железо.
* - Не выдается точка, в которой произошло несовпадение.
=== По порядку сравнения паттерна в тексте ===
==== Прямой ====
* + Отсутсвие регрессии на «плохих» данных.
* - Не самая хорошая средняя ассимптотическая сложность.
==== Обратный ====
Паттерн движется по тексту слева на право, но сравнение подстрок происходит с права на лево.
* + При несовпадении позволяет перемещать паттерн по строке сразу на несколько символов
==== Сравнение в необычном порядке ====
Специфические алгоритмы, основанные, как правило, на некоторых эмпирических наблюдениях над словарём.
=== По количеству поисковых шаблонов ===
#Один шаблон (''Single pattern algorithms'')
#Конечное количество шаблонов (''finite set of patterns'')
#Бесконечное количество шаблонов (Регулярные грамматики/regexp'ы)
=== По необходимости препроцессинга текста ===
Виды препроцессинга:
*[[Префикс-функция]]
*[[Z-функция]]
*[[Бор]]
*[[Суффиксный_массив]]
Алгоритмы, использующие препроцессинг — одни из самых быстрых в этом классе.
== Сравнение алгоритмов ==
*<tex>|\Sigma| = \sigma</tex> — размер алфавита
*<tex>|haystack| = h</tex> — длина текста
*<tex>|needle| = n</tex> — длина паттерна
*<tex>a</tex> — размер ответа(кол-во пар)
*<tex>m</tex> — суммарная длина всх паттернов
{|class="wikitable"
|+
!width="25%"|Название !! width="8%"| Среднее !! width="8%"| Худшее !! width="8%"|Необходимость препроцессинга !! width="8%"| Дополнительная память !! width="10%"| Кол-во поисковых шаблонов !! width="10%"| Порядок сравнения !! width="35%"| Описание
|- align = "center"
|[[Наивный алгоритм поиска подстроки в строке| Наивный алгоритм <br>(Brute Force algorithm)]]
|<tex>O(n \cdot (h - n))</tex>
|<tex>O(n^2)</tex>
|Нет
|<tex>O(1)</tex>
|Single
|Прямой
|Сравнение — «чёрный ящик». Если <tex>n</tex> достаточно мало по сравнению с <tex>h</tex>, то ассимптотика будет близкой к O(h), что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, ctrl+F в браузерах)
|- align = "center"
|[http://www-igm.univ-mlv.fr/~lecroq/string/node18.html#SECTION00180| Алгоритм Бойера-Мура-Хорспула <br>(Horspool algorithm)]
|<tex>O(nh)</tex>
|<tex>O(nh)</tex>
|Да <br> <tex>O(n + \sigma)</tex>
|<tex>O(\sigma)</tex>
|Single
|Прямой
|В самой простой реализации использует только эвристику стоп-символа и относится к алгоритмом с сравнением — «чёрным ящиком».
|- align = "center"
|[[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа| Алгоритм Рабина-Карпа <br>(Karp-Rabin algorithm)]]
|<tex>O(n + h)</tex>
|<tex>O(nh)</tex>
|Да <br> <tex>O(n)</tex>
|<tex>O(1)</tex>
|Single
|Прямой
|Данный алгоритм использует хэширование, что снижает скорость в среднем.
|- align = "center"
|[[Алгоритм Кнута-Морриса-Пратта| Алгоритм Кнута-Морриса-Пратта <br>(Knuth-Morris-Pratt algorith)]]
|<tex>O(n + h)</tex>
|<tex>O(n + h)</tex>
|Да <br> <tex>O(n)</tex>
|<tex>O(n)</tex>
|Single
|Прямой
|Использует [[Префикс-функция| префикс-функцию]]
|- align = "center"
|[[Алгоритм Ахо-Корасик| Алгоритм Ахо-Корасик <br>(Aho–Corasick string matching algorithm)]]
|<tex>O(m + h + a)</tex>
|<tex>O(h)</tex>
|Да <br> <tex>O(m)</tex>
|<tex>O(m\sigma)</tex>
|finite
|Прямой
|Строит конечный автомат
|}
