34
правки
Изменения
delete excess algo, add Raita example, add ref to turbo-algorithm
==== Сравнение в необычном порядке ====
Специфические алгоритмы, основанные, как правило, на некоторых эмпирических наблюдениях над словарём. Как пример можно привести [[Wikipedia:en:Raita Algorithm| Алгоритм Райты (англ.)]]
=== По количеству поисковых шаблонов ===
|Сравнение — «чёрный ящик». Если <tex>n</tex> достаточно мало по сравнению с <tex>h</tex>, то ассимптотика будет близкой к O(h), что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, ctrl+F в браузерах)
|- align = "center"
|[[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа| Алгоритм Рабина-Карпа <br>(Karp-Rabin algorithm)]]
|Single
|Обратный
|Считается наиболее быстрым из алгоритмов общего назначения. Использует эвристики. |-align = "center"|[http://www-igm.univ-mlv.fr/~lecroq/string/node20.html#SECTION00200 Алгоритм Чжу-Такаоки <br>(Zhu-Takaoka algorithm)]|<tex>O(h)</tex>|<tex>O(hn)</tex>|Существует большое количество оптимизаций<texref>O(n + \sigma^2)</tex>|<tex>O(n + \sigma^2)</tex>|Single|Обратный|Оптимизация Бойера-Мура под короткие алфавиты |-align = "center"|Например, [http://www-igm.univ-mlv.fr/~lecroq/string/node15.html#SECTION00150 Турбо-алгоритм Бойера-Мура <br>(Turbo-BM algorithm)]|<tex>O(h)</tex>|<texref>O(h)</tex>|<tex>O(n + \sigma)</tex>|<tex>O(n + \sigma)</tex>|Single|Обратный|Не дает регрессии на «плохих» данных. <tex>2h</tex> сравнений в худшем случае. Количество эвристик увеличивается до трёх
|-align = "center"
|Single
|Прямой
|Использует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix(lcp)]], то можно увеличить асимптотику до <tex>O(n + log(h))</tex>
|-align = "center"
|Оптимизация [[Алгоритм Кнута-Морриса-Пратта| Алгоритма Кнута-Морриса-Пратта]] использует как прямой, так и обратный обход
|}
== Примечания ==
<references />
== Ссылки ==
