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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ссылки)
(Сравнение алгоритмов)
(не показано 26 промежуточных версий 6 участников)
Строка 1: Строка 1:
\''Поиск подстроки в строке'' (англ. ''String searching algorithm'') — класс алгоритмов над строками, которые позволяют найти паттерн (''needle'') в тексте (''haystack'').  
+
'''Поиск подстроки в строке''' (англ. ''String searching algorithm'') — класс алгоритмов над строками, которые позволяют найти паттерн (''pattern'') в тексте (''text'').  
 
== Классификация алгоритмов поиска подстроки в строке ==
 
== Классификация алгоритмов поиска подстроки в строке ==
  
 
=== Сравнение — «чёрный ящик» ===
 
=== Сравнение — «чёрный ящик» ===
  
Во всех алгоритмах этого типа сравнение является «чёрным ящиком» для программиста.  
+
Во всех алгоритмах этого типа сравнение является «чёрным ящиком» для программиста.
* + Позволяет использовать стандартные функции сравнения участков памяти (man *cmp(3)), которые, зачастую, оптимизированы под конкретное железо.  
+
 
* - Не выдается точка, в которой произошло несовпадение.  
+
Преимущества:
 +
* позволяет использовать стандартные функции сравнения участков памяти (man *cmp(3)), которые, зачастую, оптимизированы под конкретное железо.  
 +
 
 +
Недостатки:
 +
* не выдается точка, в которой произошло несовпадение.
  
 
=== По порядку сравнения паттерна в тексте ===
 
=== По порядку сравнения паттерна в тексте ===
 +
==== Прямой ====
  
==== Прямой ====
+
Преимущества:
* + Отсутсвие регрессии на «плохих» данных.
+
* отсутствие регрессии на «плохих» данных.
* - Не самая хорошая средняя асимптотическая сложность.
+
 
 +
Недостатки:
 +
* не самая хорошая средняя асимптотическая сложность.
  
 
==== Обратный ====
 
==== Обратный ====
Паттерн движется по тексту слева на право, но сравнение подстрок происходит справа на лево.
+
Паттерн движется по тексту слева направо, но сравнение подстрок происходит справа налево.
* + При несовпадении позволяет перемещать паттерн по строке сразу на несколько символов
+
 
 +
Преимущества:
 +
* при несовпадении позволяет перемещать паттерн по строке сразу на несколько символов.
 +
 
 +
Недостатки:
 +
* производительность сильно зависит от данных.
  
 
==== Сравнение в необычном порядке ====
 
==== Сравнение в необычном порядке ====
Специфические алгоритмы, основанные, как правило, на некоторых эмпирических наблюдениях над словарём.  
+
Специфические алгоритмы, основанные, как правило, на некоторых эмпирических наблюдениях над словарём.<ref>Например, [[Wikipedia:en:Raita Algorithm| Алгоритм Райты (англ.)]]</ref>
  
 
=== По количеству поисковых шаблонов ===
 
=== По количеству поисковых шаблонов ===
  
#Один шаблон (''Single pattern algorithms'')
+
Сколько поисковых шаблонов может обработать алгоритм за один раз.
#Конечное количество шаблонов (''finite set of patterns'')
+
 
#Бесконечное количество шаблонов (''infinite number of patterns'') (см. [[Теория формальных языков]], [http://en.wikipedia.org/wiki/Regular_expression regexp])
+
* один шаблон (англ. ''single pattern algorithms'')
 +
* конечное количество шаблонов (англ. ''finite set of patterns'')
 +
* бесконечное количество шаблонов (англ. ''infinite number of patterns'') (см. [[Теория формальных языков]])
  
 
=== По необходимости препроцессинга текста ===
 
=== По необходимости препроцессинга текста ===
Строка 32: Строка 46:
 
*[[Z-функция]]
 
*[[Z-функция]]
 
*[[Бор]]
 
*[[Бор]]
*[[Суффиксный_массив]]
+
*[[Суффиксный массив]]
Алгоритмы использующие препроцессинг — одни из самых быстрых в этом классе.
+
Алгоритмы, использующие препроцессинг — одни из самых быстрых в этом классе.
  
 
== Сравнение алгоритмов ==
 
== Сравнение алгоритмов ==
 
*<tex>|\Sigma| = \sigma</tex>­ — размер алфавита
 
*<tex>|\Sigma| = \sigma</tex>­ — размер алфавита
*<tex>|haystack| = h</tex> — длина текста
+
*<tex>|text| = t</tex> — длина текста
*<tex>|needle| = n</tex> — длина паттерна
+
*<tex>|pattern| = p</tex> — длина паттерна
 
*<tex>a</tex> — размер ответа(кол-во пар)
 
*<tex>a</tex> — размер ответа(кол-во пар)
*<tex>m</tex> — суммарная длина всх паттернов  
+
*<tex>m</tex> — суммарная длина всех паттернов  
  
 
{|class="wikitable"
 
{|class="wikitable"
 
|+
 
|+
!width="25%"|Название !! width="5%"| Среднее !! width="5%"| Худшее !! width="5%"|Необходимость препроцессинга !! width="5%"| Дополнительная память !! width="10%"| Кол-во поисковых шаблонов !! width="10%"| Порядок сравнения !! width="35%"| Описание
+
!width="25%"|Название !! width="5%"| Среднее !! width="5%"| Худшее !! width="5%"|Препроцессинг !! width="5%"| Дополнительная память !! width="10%"| Кол-во поисковых шаблонов !! width="10%"| Порядок сравнения !! width="35%"| Описание
  
 
|- align = "center"
 
|- align = "center"
 
|[[Наивный алгоритм поиска подстроки в строке| Наивный алгоритм <br>(Brute Force algorithm)]]
 
|[[Наивный алгоритм поиска подстроки в строке| Наивный алгоритм <br>(Brute Force algorithm)]]
|<tex>O(n \cdot (h - n))</tex>
+
|<tex>O(p \cdot (t - p))</tex>
|<tex>O(n^2)</tex>
+
|<tex>O(t^2)</tex>
|Нет
+
|
 
|<tex>O(1)</tex>
 
|<tex>O(1)</tex>
 
|Single
 
|Single
 
|Прямой
 
|Прямой
|Сравнение — «чёрный ящик». Если <tex>n</tex> достаточно мало по сравнению с <tex>h</tex>, то ассимптотика будет близкой к O(h), что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, ctrl+F в браузерах)
+
|Сравнение — «чёрный ящик». Если <tex>p</tex> достаточно мало по сравнению с <tex>t</tex>, то асимптотика будет близкой к <tex>O(t)</tex>, что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, Ctrl+F в браузерах)
  
|- align = "center"
+
|-align = "center"
|[http://www-igm.univ-mlv.fr/~lecroq/string/node18.html#SECTION00180 Алгоритм Бойера-Мура-Хорспула <br>(Horspool algorithm)]
+
|[[Z-функция| Поиск подстроки в строке с помощью Z-функции]]
|<tex>O(nh)</tex>
+
|<tex>O(t)</tex>
|<tex>O(nh)</tex>
+
|<tex>O(t)</tex>
|Да <br> <tex>O(n + \sigma)</tex>
+
|<tex>O(p + t)</tex>
|<tex>O(\sigma)</tex>
+
|<tex>O(p)</tex>
 
|Single
 
|Single
 
|Прямой
 
|Прямой
|В самой простой реализации использует только эвристику стоп-символа и относится к алгоритмом с сравнением — «чёрным ящиком».
+
|
 +
 
 
|- align = "center"
 
|- align = "center"
 
|[[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа| Алгоритм Рабина-Карпа <br>(Karp-Rabin algorithm)]]
 
|[[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа| Алгоритм Рабина-Карпа <br>(Karp-Rabin algorithm)]]
|<tex>O(n + h)</tex>
+
|<tex>O(p + t)</tex>
|<tex>O(nh)</tex>
+
|<tex>O(pt)</tex>
|Да <br> <tex>O(n)</tex>
+
|<tex>O(p)</tex>
 
|<tex>O(1)</tex>
 
|<tex>O(1)</tex>
 
|Single / Finite
 
|Single / Finite
 
|Прямой
 
|Прямой
|Данный алгоритм использует хэширование, что снижает скорость в среднем. Можно модифицировать для поиска нескольких паттернов.
+
|Данный алгоритм использует хэширование, что снижает скорость в среднем. Можно модифицировать для поиска нескольких паттернов
  
 
|- align = "center"
 
|- align = "center"
 
|[[Алгоритм Кнута-Морриса-Пратта| Алгоритм Кнута-Морриса-Пратта <br>(Knuth-Morris-Pratt algorith)]]
 
|[[Алгоритм Кнута-Морриса-Пратта| Алгоритм Кнута-Морриса-Пратта <br>(Knuth-Morris-Pratt algorith)]]
|<tex>O(n + h)</tex>
+
|<tex>O(p + t)</tex>
|<tex>O(n + h)</tex>
+
|<tex>O(p + t)</tex>
|Да <br> <tex>O(n)</tex>
+
|<tex>O(p)</tex>
|<tex>O(n)</tex>
+
|<tex>O(p)</tex>
 
|Single
 
|Single
 
|Прямой
 
|Прямой
 
|Использует [[Префикс-функция| префикс-функцию]]
 
|Использует [[Префикс-функция| префикс-функцию]]
 +
 +
|-align = "center"
 +
|[[Алгоритм Колусси| Алгоритм Колусси <br>(Colussi algorithm)]]
 +
|<tex>O(t)</tex>
 +
|<tex>O(t)</tex>
 +
|<tex>O(p)</tex>
 +
|<tex>O(p)</tex>
 +
|Single
 +
|Прямой / Обратный
 +
|Оптимизация [[Алгоритм Кнута-Морриса-Пратта| Алгоритма Кнута-Морриса-Пратта]] использует как прямой, так и обратный обход
  
 
|- align = "center"
 
|- align = "center"
 
|[[Алгоритм Ахо-Корасик| Алгоритм Ахо-Корасик <br>(Aho–Corasick string matching algorithm)]]
 
|[[Алгоритм Ахо-Корасик| Алгоритм Ахо-Корасик <br>(Aho–Corasick string matching algorithm)]]
|<tex>O(m + h + a)</tex>
+
|<tex>O(m + t + a)</tex>
|<tex>O(h)</tex>
+
|<tex>O(t)</tex>
|Да <br> <tex>O(m)</tex>
+
|<br> <tex>O(m)</tex>
 
|<tex>O(m\sigma)</tex>
 
|<tex>O(m\sigma)</tex>
 
|Finite
 
|Finite
Строка 96: Строка 121:
  
 
|-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(t)</tex>
|<tex>O(h \cdot ceil(n / w))</tex> <br> w — размер машинного слова
+
|<tex>O(t \cdot \dfrac{n}{w})</tex> <br> <tex>w</tex> — размер машинного слова
|Да <br> <tex>O(n + \sigma)</tex>
+
|<tex>O(p + \sigma)</tex>
|<tex>O(n + \sigma)</tex>
+
|<tex>O(p + \sigma)</tex>
 
|Single
 
|Single
 
|Прямой
 
|Прямой
|Использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если n <= w. Иначе деградирует и по памяти, и по сложности.
+
|Использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если <tex>p \leqslant w</tex>. Иначе деградирует и по памяти, и по сложности
  
 
|-align = "center"
 
|-align = "center"
 
|[[Алгоритм Бойера-Мура| Алгоритм Бойера-Мура <br>(Boyer-Moore algorithm)]]
 
|[[Алгоритм Бойера-Мура| Алгоритм Бойера-Мура <br>(Boyer-Moore algorithm)]]
|<tex>O(h)</tex>
+
|<tex>O(t)</tex>
|<tex>O(hn)</tex>
+
|<tex>O(pt)</tex>
|Да <br> <tex>O(n + \sigma)</tex>
+
|<tex>O(p + \sigma)</tex>
|<tex>O(n + \sigma)</tex>
+
|<tex>O(p + \sigma)</tex>
 
|Single
 
|Single
 
|Обратный
 
|Обратный
|Считается наиболее быстрым из алгоритмов общего назначения. Использует эвристики.
+
|Считается наиболее быстрым из алгоритмов общего назначения. Использует эвристики. Существует большое количество оптимизаций<ref>Например, [http://www-igm.univ-mlv.fr/~lecroq/string/node15.html#SECTION00150 Турбо-алгоритм Бойера-Мура <br>(Turbo-BM algorithm)]</ref>
  
 
|-align = "center"
 
|-align = "center"
|[http://www-igm.univ-mlv.fr/~lecroq/string/node20.html#SECTION00200 Алгоритм Чжу-Такаоки <br>(Zhu-Takaoka algorithm)]
+
|[[Алгоритм поиска подстроки в строке с помощью суффиксного массива| Поиск подстроки в строке с помощью суффиксного массива <br>(Suffix array)]]
|<tex>O(h)</tex>
+
|<tex>O(p\log t)</tex>
|<tex>O(hn)</tex>
+
|<tex>O(p\log t)</tex>
|Да <br> <tex>O(n + \sigma^2)</tex>
+
|<tex>O(t)</tex>
|<tex>O(n + \sigma^2)</tex>
+
|<tex>O(t)</tex>
 
|Single
 
|Single
|Обратный
+
|Прямой
|Оптимизация Бойера-Мура под короткие алфавиты
+
|Использует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix (lcp)]], то можно уменьшить асимптотику до <tex>O(p + \log t)</tex>. Суффиксный массив можно строить[[Построение суффиксного массива с помощью стандартных методов сортировки| стандартными способами]] или [[Алгоритм Карккайнена-Сандерса| алгоритмом Карккайнена-Сандерса]]. Асимптотика приведена для построения суффиксного массива с помощью алгоритма Карккайнена-Сандерса
  
 
|-align = "center"
 
|-align = "center"
|[http://www-igm.univ-mlv.fr/~lecroq/string/node15.html#SECTION00150 Турбо-алгоритм Бойера-Мура <br>(Turbo-BM algorithm)]
+
|[[Сжатое суффиксное дерево| Поиск подстроки в строке с помощью суффиксного дерева <br>(Suffix tree)]]
|<tex>O(h)</tex>
+
|<tex>O(p)</tex>
|<tex>O(h)</tex>
+
|<tex>O(p)</tex>
|Да <br> <tex>O(n + \sigma)</tex>
+
|<tex>O(t)</tex>
|<tex>O(n + \sigma)</tex>
+
|<tex>O(t)</tex>
 
|Single
 
|Single
|Обратный
+
|Прямой
|Не дает регрессии на «плохих» данных. <tex>2h</tex> сравнений в худшем случае. Количество эвристик увеличивается до трёх.
+
|Позволяет выполнять поиск подстроки в строке за линейное время
  
|-align = "center"
+
|- align = "center"
|[[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
+
|[[Алгоритм Апостолико-Крочемора| Алгоритм Апостолико-Крочемора <br>( Apostolico-Crochemore algorithm)]]
|<tex>O(nlog(h))</tex>
+
|<tex>O(t)</tex>
|<tex>O(nlog(h))</tex>
+
|<tex>O(t)</tex>
|Да <br> <tex>O(n)</tex>
+
|<tex>O(p)</tex>
|<tex>O(nlog^2(n))</tex>
+
|<tex>O(p)</tex>
 
|Single
 
|Single
|
+
|Прямой
|Использует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix(lcp)]], то можно увеличить асимптотику до <tex>O(n + log(h))</tex>
+
|В худшем случае выполнит <tex>\dfrac{3}{2} n</tex> сравнений.
 
|}
 
|}
  
== Ссылки ==
+
== Примечания ==
*[[wikipedia:ru:Поиск_подстроки | Википедия {{---}} Поиск подстроки]]
+
 
* http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8
+
<references />
* http://en.wikipedia.org/wiki/String_searching_algorithm
+
 
* http://www-igm.univ-mlv.fr/~lecroq/string/index.html — (англ.) Очень много разных алгоритмов поиска подстроки в строке. Многие из них в данной статье не описаны.
+
== Источники информации ==
 +
* [[wikipedia:ru:Поиск_подстроки | Википедия {{---}} Поиск подстроки]]
 +
* [[Wikipedia:en:String_searching_algorithm | Википедия {{---}} String searching algorithm]]
 +
* [http://www-igm.univ-mlv.fr/~lecroq/string/index.html ESMAJ] — (англ.) Большое количество разных алгоритмов поиска подстроки в строке. Многие из них в данной статье не описаны.
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Поиск подстроки в строке]]
 
[[Категория: Поиск подстроки в строке]]

Версия 05:10, 27 мая 2018

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

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

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

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

Преимущества:

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

Недостатки:

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

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

Прямой

Преимущества:

  • отсутствие регрессии на «плохих» данных.

Недостатки:

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

Обратный

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

Преимущества:

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

Недостатки:

  • производительность сильно зависит от данных.

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

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

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

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

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

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

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

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

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

  • [math]|\Sigma| = \sigma[/math]­ — размер алфавита
  • [math]|text| = t[/math] — длина текста
  • [math]|pattern| = p[/math] — длина паттерна
  • [math]a[/math] — размер ответа(кол-во пар)
  • [math]m[/math] — суммарная длина всех паттернов
Название Среднее Худшее Препроцессинг Дополнительная память Кол-во поисковых шаблонов Порядок сравнения Описание
Наивный алгоритм
(Brute Force algorithm)
[math]O(p \cdot (t - p))[/math] [math]O(t^2)[/math] [math]O(1)[/math] Single Прямой Сравнение — «чёрный ящик». Если [math]p[/math] достаточно мало по сравнению с [math]t[/math], то асимптотика будет близкой к [math]O(t)[/math], что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, Ctrl+F в браузерах)
Поиск подстроки в строке с помощью Z-функции [math]O(t)[/math] [math]O(t)[/math] [math]O(p + t)[/math] [math]O(p)[/math] Single Прямой
Алгоритм Рабина-Карпа
(Karp-Rabin algorithm)
[math]O(p + t)[/math] [math]O(pt)[/math] [math]O(p)[/math] [math]O(1)[/math] Single / Finite Прямой Данный алгоритм использует хэширование, что снижает скорость в среднем. Можно модифицировать для поиска нескольких паттернов
Алгоритм Кнута-Морриса-Пратта
(Knuth-Morris-Pratt algorith)
[math]O(p + t)[/math] [math]O(p + t)[/math] [math]O(p)[/math] [math]O(p)[/math] Single Прямой Использует префикс-функцию
Алгоритм Колусси
(Colussi algorithm)
[math]O(t)[/math] [math]O(t)[/math] [math]O(p)[/math] [math]O(p)[/math] Single Прямой / Обратный Оптимизация Алгоритма Кнута-Морриса-Пратта использует как прямой, так и обратный обход
Алгоритм Ахо-Корасик
(Aho–Corasick string matching algorithm)
[math]O(m + t + a)[/math] [math]O(t)[/math]
[math]O(m)[/math]
[math]O(m\sigma)[/math] Finite Прямой Строит конечный автомат. Можно хранить таблицу переходов как индексный массив (array), а можно как Красно-черное дерево. В последнем случае уменьшится расход памяти, но ухудшится асимптотика
Алгоритм Shift-Or [math]O(t)[/math] [math]O(t \cdot \dfrac{n}{w})[/math]
[math]w[/math] — размер машинного слова
[math]O(p + \sigma)[/math] [math]O(p + \sigma)[/math] Single Прямой Использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если [math]p \leqslant w[/math]. Иначе деградирует и по памяти, и по сложности
Алгоритм Бойера-Мура
(Boyer-Moore algorithm)
[math]O(t)[/math] [math]O(pt)[/math] [math]O(p + \sigma)[/math] [math]O(p + \sigma)[/math] Single Обратный Считается наиболее быстрым из алгоритмов общего назначения. Использует эвристики. Существует большое количество оптимизаций[2]
Поиск подстроки в строке с помощью суффиксного массива
(Suffix array)
[math]O(p\log t)[/math] [math]O(p\log t)[/math] [math]O(t)[/math] [math]O(t)[/math] Single Прямой Использует Суффиксный массив. Если использовать Largest common prefix (lcp), то можно уменьшить асимптотику до [math]O(p + \log t)[/math]. Суффиксный массив можно строить стандартными способами или алгоритмом Карккайнена-Сандерса. Асимптотика приведена для построения суффиксного массива с помощью алгоритма Карккайнена-Сандерса
Поиск подстроки в строке с помощью суффиксного дерева
(Suffix tree)
[math]O(p)[/math] [math]O(p)[/math] [math]O(t)[/math] [math]O(t)[/math] Single Прямой Позволяет выполнять поиск подстроки в строке за линейное время
Алгоритм Апостолико-Крочемора
( Apostolico-Crochemore algorithm)
[math]O(t)[/math] [math]O(t)[/math] [math]O(p)[/math] [math]O(p)[/math] Single Прямой В худшем случае выполнит [math]\dfrac{3}{2} n[/math] сравнений.

Примечания

Источники информации