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

Материал из Викиконспекты
Версия от 20:26, 5 июня 2014; Firespace (обсуждение | вклад) (Новая страница: «''Поиск подстроки в строке'' (''String searching algorithm'') — класс алгоритмов над строками, которые п...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Поиск подстроки в строке (String searching algorithm) — класс алгоритмов над строками, которые позволяют найти паттерн (needle) в тексте (haystack).

Классификация алгоритмов поиска подстроки в строке

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

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

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

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

Прямой

  • + Отсутсвие регрессии на «плохих» данных.
  • - Не самая хорошая средняя ассимптотическая сложность.

Обратный

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

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

Сравнение в необычном порядке

Специфические алгоритмы, основанные, как правило, на некоторых эмпирических наблюдениях над словарём.

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

  1. Один шаблон (Single pattern algorithms)
  2. Конечное количество шаблонов (finite set of patterns)
  3. Бесконечное количество шаблонов (Регулярные грамматики/regexp'ы)

По необходимости препроцессинга текста

Виды препроцессинга:

Алгоритмы, использующие препроцессинг — одни из самых быстрых в этом классе.

Сравнение алгоритмов

  • [math]|\Sigma| = \sigma[/math]­ — размер алфавита
  • [math]|haystack| = h[/math] — длина текста
  • [math]|needle| = n[/math] — длина паттерна
  • [math]a[/math] — размер ответа(кол-во пар)
  • [math]m[/math] — суммарная длина всх паттернов
Название Среднее Худшее Необходимость препроцессинга Дополнительная память Кол-во поисковых шаблонов Порядок сравнения Описание
Наивный алгоритм
(Brute Force algorithm)
[math]O(n \cdot (h - n))[/math] [math]O(n^2)[/math] Нет [math]O(1)[/math] Single Прямой Сравнение — «чёрный ящик». Если [math]n[/math] достаточно мало по сравнению с [math]h[/math], то ассимптотика будет близкой к O(h), что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, ctrl+F в браузерах)
Алгоритм Бойера-Мура-Хорспула
(Horspool algorithm)]
[math]O(nh)[/math] [math]O(nh)[/math] Да
[math]O(n + \sigma)[/math]
[math]O(\sigma)[/math] Single Прямой В самой простой реализации использует только эвристику стоп-символа и относится к алгоритмом с сравнением — «чёрным ящиком».
Алгоритм Рабина-Карпа
(Karp-Rabin algorithm)
[math]O(n + h)[/math] [math]O(nh)[/math] Да
[math]O(n)[/math]
[math]O(1)[/math] Single Прямой Данный алгоритм использует хэширование, что снижает скорость в среднем.
Алгоритм Кнута-Морриса-Пратта
(Knuth-Morris-Pratt algorith)
[math]O(n + h)[/math] [math]O(n + h)[/math] Да
[math]O(n)[/math]
[math]O(n)[/math] Single Прямой Использует префикс-функцию
Алгоритм Ахо-Корасик
(Aho–Corasick string matching algorithm)
[math]O(m + h + a)[/math] [math]O(h)[/math] Да
[math]O(m)[/math]
[math]O(m\sigma)[/math] finite Прямой Строит конечный автомат