Поиск подстроки в строке — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(small decor changes)
(add Colussi algorithm and some fixes)
Строка 73: Строка 73:
 
|Single / Finite
 
|Single / Finite
 
|Прямой
 
|Прямой
|Данный алгоритм использует хэширование, что снижает скорость в среднем. Можно модифицировать для поиска нескольких паттернов.
+
|Данный алгоритм использует хэширование, что снижает скорость в среднем. Можно модифицировать для поиска нескольких паттернов
  
 
|- align = "center"
 
|- align = "center"
Строка 96: Строка 96:
  
 
|-align = "center"
 
|-align = "center"
|[http://www-igm.univ-mlv.fr/~lecroq/string/node6.html#SECTION0060 Shift-Or algorithm]
+
|[[Алгоритм Shift-Or]]
 
|<tex>O(h)</tex> <br> w — размер машинного слова
 
|<tex>O(h)</tex> <br> w — размер машинного слова
 
|<tex>O(h \cdot ceil(n / w))</tex> <br> w — размер машинного слова
 
|<tex>O(h \cdot ceil(n / w))</tex> <br> w — размер машинного слова
Строка 103: Строка 103:
 
|Single
 
|Single
 
|Прямой
 
|Прямой
|Использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если n <= w. Иначе деградирует и по памяти, и по сложности.
+
|Использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если n <= w. Иначе деградирует и по памяти, и по сложности
  
 
|-align = "center"
 
|-align = "center"
Строка 133: Строка 133:
 
|Single
 
|Single
 
|Обратный
 
|Обратный
|Не дает регрессии на «плохих» данных. <tex>2h</tex> сравнений в худшем случае. Количество эвристик увеличивается до трёх.
+
|Не дает регрессии на «плохих» данных. <tex>2h</tex> сравнений в худшем случае. Количество эвристик увеличивается до трёх
  
 
|-align = "center"
 
|-align = "center"
Строка 142: Строка 142:
 
|<tex>O(n\log^2 n)</tex>
 
|<tex>O(n\log^2 n)</tex>
 
|Single
 
|Single
|
+
|Прямой
 
|Использует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix(lcp)]], то можно увеличить асимптотику до <tex>O(n + log(h))</tex>
 
|Использует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix(lcp)]], то можно увеличить асимптотику до <tex>O(n + log(h))</tex>
 +
 +
|-align = "center"
 +
|[[Алгоритм Колусси| Алгоритм Колусси <br>(Colussi algorithm)]]
 +
|<tex>O(h)</tex>
 +
|<tex>O(h)</tex>
 +
|<tex>O(n)</tex>
 +
|<tex>O(n)</tex>
 +
|Single
 +
|Прямой / Обратный
 +
|Оптимизация [[Алгоритм Кнута-Морриса-Пратта| Алгоритма Кнута-Морриса-Пратта]] использует как прямой, так и обратный обход
 
|}
 
|}
  
Строка 149: Строка 159:
 
* [[wikipedia:ru:Поиск_подстроки | Википедия {{---}} Поиск подстроки]]
 
* [[wikipedia:ru:Поиск_подстроки | Википедия {{---}} Поиск подстроки]]
 
* [[Wikipedia:en:String_searching_algorithm | Википедия {{---}} String searching algorithm]]
 
* [[Wikipedia:en:String_searching_algorithm | Википедия {{---}} String searching algorithm]]
* [http://www-igm.univ-mlv.fr/~lecroq/string/index.html ESMAJ] — (англ.) Очень много разных алгоритмов поиска подстроки в строке. Многие из них в данной статье не описаны.
+
* [http://www-igm.univ-mlv.fr/~lecroq/string/index.html ESMAJ] — (англ.) Большое количество разных алгоритмов поиска подстроки в строке. Многие из них в данной статье не описаны.
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Поиск подстроки в строке]]
 
[[Категория: Поиск подстроки в строке]]

Версия 01:45, 6 июня 2014

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

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

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

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

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

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

Прямой

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

Обратный

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

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

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

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

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

  1. Один шаблон (Single pattern algorithms)
  2. Конечное количество шаблонов (finite set of patterns)
  3. Бесконечное количество шаблонов (infinite number of patterns) (см. Теория формальных языков)

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

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

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

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

  • [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 / Finite Прямой Данный алгоритм использует хэширование, что снижает скорость в среднем. Можно модифицировать для поиска нескольких паттернов
Алгоритм Кнута-Морриса-Пратта
(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 Прямой Строит конечный автомат. Можно хранить таблицу переходов как индексный массив (array), а можно как Красно-черное дерево. В последнем случае уменьшится расход памяти, но ухудшится асимптотика
Алгоритм Shift-Or [math]O(h)[/math]
w — размер машинного слова
[math]O(h \cdot ceil(n / w))[/math]
w — размер машинного слова
[math]O(n + \sigma)[/math] [math]O(n + \sigma)[/math] Single Прямой Использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если n <= w. Иначе деградирует и по памяти, и по сложности
Алгоритм Бойера-Мура
(Boyer-Moore algorithm)
[math]O(h)[/math] [math]O(hn)[/math] [math]O(n + \sigma)[/math] [math]O(n + \sigma)[/math] Single Обратный Считается наиболее быстрым из алгоритмов общего назначения. Использует эвристики.
Алгоритм Чжу-Такаоки
(Zhu-Takaoka algorithm)
[math]O(h)[/math] [math]O(hn)[/math] [math]O(n + \sigma^2)[/math] [math]O(n + \sigma^2)[/math] Single Обратный Оптимизация Бойера-Мура под короткие алфавиты
Турбо-алгоритм Бойера-Мура
(Turbo-BM algorithm)
[math]O(h)[/math] [math]O(h)[/math] [math]O(n + \sigma)[/math] [math]O(n + \sigma)[/math] Single Обратный Не дает регрессии на «плохих» данных. [math]2h[/math] сравнений в худшем случае. Количество эвристик увеличивается до трёх
Алгоритм поиска подстроки в строке с помощью суффиксного массива [math]O(n\log h)[/math] [math]O(n\log h)[/math] [math]O(n)[/math] [math]O(n\log^2 n)[/math] Single Прямой Использует Суффиксный массив. Если использовать Largest common prefix(lcp), то можно увеличить асимптотику до [math]O(n + log(h))[/math]
Алгоритм Колусси
(Colussi algorithm)
[math]O(h)[/math] [math]O(h)[/math] [math]O(n)[/math] [math]O(n)[/math] Single Прямой / Обратный Оптимизация Алгоритма Кнута-Морриса-Пратта использует как прямой, так и обратный обход

Ссылки