1632
правки
Изменения
м
==== Прямой ====Преимущества:: <tex>+</tex> Отсутсвие * отсутствие регрессии на «плохих» данных. Недостатки: <tex>-</tex> Не * не самая хорошая средняя асимптотическая сложность.
#Один Сколько поисковых шаблонов может обработать алгоритм за один раз. * один шаблон (англ. ''Single single pattern algorithms'')#Конечное * конечное количество шаблонов (англ. ''finite set of patterns'')#Бесконечное * бесконечное количество шаблонов (англ. ''infinite number of patterns'') (см. [[Теория формальных языков]])
rollbackEdits.php mass rollback
'''Поиск подстроки в строке''' (англ. ''String searching algorithm'') — класс алгоритмов над строками, которые позволяют найти паттерн (''needlepattern'') в тексте (''haystacktext'').
== Классификация алгоритмов поиска подстроки в строке ==
=== Сравнение — «чёрный ящик» ===
Во всех алгоритмах этого типа сравнение является «чёрным ящиком» для программиста. Преимущества: <tex>+</tex> Позволяет * позволяет использовать стандартные функции сравнения участков памяти (man *cmp(3)), которые, зачастую, оптимизированы под конкретное железо. Недостатки: <tex>-</tex> Не * не выдается точка, в которой произошло несовпадение.
=== По порядку сравнения паттерна в тексте ===
==== Прямой ====
==== Обратный ====
Паттерн движется по тексту слева на правонаправо, но сравнение подстрок происходит справа на левоналево. Преимущества: <tex>+</tex> При * при несовпадении позволяет перемещать паттерн по строке сразу на несколько символов. Недостатки:* производительность сильно зависит от данных.
==== Сравнение в необычном порядке ====
=== По количеству поисковых шаблонов ===
=== По необходимости препроцессинга текста ===
*[[Бор]]
*[[Суффиксный массив]]
Алгоритмы , использующие препроцессинг — одни из самых быстрых в этом классе.
== Сравнение алгоритмов ==
*<tex>|\Sigma| = \sigma</tex> — размер алфавита
*<tex>|haystacktext| = ht</tex> — длина текста*<tex>|needlepattern| = np</tex> — длина паттерна
*<tex>a</tex> — размер ответа(кол-во пар)
*<tex>m</tex> — суммарная длина всех паттернов
|- align = "center"
|[[Наивный алгоритм поиска подстроки в строке| Наивный алгоритм <br>(Brute Force algorithm)]]
|<tex>O(n p \cdot (h t - np))</tex>|<tex>O(nt^2)</tex>
|
|<tex>O(1)</tex>
|Single
|Прямой
|Сравнение — «чёрный ящик». Если <tex>np</tex> достаточно мало по сравнению с <tex>ht</tex>, то ассимптотика асимптотика будет близкой к <tex>O(ht)</tex>, что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, ctrlCtrl+F в браузерах)
|-align = "center"
|[[Z-функция| Поиск подстроки в строке с помощью Z-функции]]
|<tex>O(ht)</tex>|<tex>O(ht)</tex>|<tex>O(h p + nt)</tex>|<tex>O(h + np)</tex>
|Single
|Прямой
|Можно модифицировать для поиска подстроки.
|- align = "center"
|[[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа| Алгоритм Рабина-Карпа <br>(Karp-Rabin algorithm)]]
|<tex>O(n p + ht)</tex>|<tex>O(nhpt)</tex>|<tex>O(np)</tex>
|<tex>O(1)</tex>
|Single / Finite
|- align = "center"
|[[Алгоритм Кнута-Морриса-Пратта| Алгоритм Кнута-Морриса-Пратта <br>(Knuth-Morris-Pratt algorith)]]
|<tex>O(n p + ht)</tex>|<tex>O(n p + ht)</tex>|<tex>O(np)</tex>|<tex>O(np)</tex>
|Single
|Прямой
|-align = "center"
|[[Алгоритм Колусси| Алгоритм Колусси <br>(Colussi algorithm)]]
|<tex>O(ht)</tex>|<tex>O(ht)</tex>|<tex>O(np)</tex>|<tex>O(np)</tex>
|Single
|Прямой / Обратный
|- align = "center"
|[[Алгоритм Ахо-Корасик| Алгоритм Ахо-Корасик <br>(Aho–Corasick string matching algorithm)]]
|<tex>O(m + h t + a)</tex>|<tex>O(ht)</tex>
|<br> <tex>O(m)</tex>
|<tex>O(m\sigma)</tex>
|-align = "center"
|[[Алгоритм Shift-Or]]
|<tex>O(ht)</tex>|<tex>O(h t \cdot ceil(\dfrac{n / }{w)})</tex> <br> <tex>w</tex> — размер машинного слова|<tex>O(n p + \sigma)</tex>|<tex>O(n p + \sigma)</tex>
|Single
|Прямой
|Использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если <tex>n p \leqslant w</tex>. Иначе деградирует и по памяти, и по сложности
|-align = "center"
|[[Алгоритм Бойера-Мура| Алгоритм Бойера-Мура <br>(Boyer-Moore algorithm)]]
|<tex>O(ht)</tex>|<tex>O(hnpt)</tex>|<tex>O(n p + \sigma)</tex>|<tex>O(n p + \sigma)</tex>
|Single
|Обратный
|-align = "center"
|[[Алгоритм поиска подстроки в строке с помощью суффиксного массива| Поиск подстроки в строке с помощью суффиксного массива <br>(Suffix array)]]
|<tex>O(np\log ht)</tex>|<tex>O(np\log ht)</tex>|<tex>O(ht)</tex>|<tex>O(ht)</tex>
|Single
|Прямой
|Использует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix (lcp)]], то можно уменьшить асимптотику до <tex>O(n p + \log ht)</tex>. Суффиксный массив можно строить[[Построение суффиксного массива с помощью стандартных методов сортировки| стандартными способами]] или [[Алгоритм КаркайненаКарккайнена-Сандерса| алгоритмом КаркайненаКарккайнена-Сандерса]]. Асимптотика приведена для построения Каркайненаномсуффиксного массива с помощью алгоритма Карккайнена-СандерсомСандерса
|-align = "center"
|[[Сжатое суффиксное дерево| Поиск подстроки в строке с помощью суффиксного дерева <br>(Suffix tree)]]
|<tex>O(np)</tex>|<tex>O(np)</tex>|<tex>O(h^2t)</tex>|<tex>O(ht)</tex>|Single|Прямой|Позволяет выполнять поиск подстроки в строке за линейное время |- align = "center"|[[Алгоритм Апостолико-Крочемора| Алгоритм Апостолико-Крочемора <br>( 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]]
