418
правок
Изменения
м
В 1991 году Р==Варианты=====Алгоритм Бойера — Мура — Хорспула===Этот алгоритм работает лучше Бойера-Мура на случайных текстах — для него оценка в среднем лучше.Коул доказал следующую теорему:{{ТеоремаАлгоритм использует только сдвиги плохих символов, при этом за такой символ берётся символ из исходного текста, который соответствует последнему символу шаблона, независимо от того, где случилось несовпадение.Поскольку реальные поисковые образцы редко имеют равномерное распределение, алгоритм Бойера-Мура-Хорспула может дать как выигрыш, так и проигрыш по сравнению с стандартной реализацией.|author=Richard Cole==Алгоритм Чжу — Такаоки===|statement=В худшем случае требуется На коротких алфавитах сдвиги плохих символов не помогают уже на коротких суффиксах. Простейший способ улучшить работу алгоритма в таких условиях — вместо одного плохого символа строить таблицу для пары символов: несовпавшего и идущего перед ним. Такой алгоритм получил собственное имя: алгоритм Чжу — Такаоки.На предварительную обработку расходуется <tex>O(3 m+\cdot nsigma^2)</tex> сравнений в случае шаблона с периодом равным длине самого шаблонавремени.|proof=Доказательство [http://www.cs.nyu.edu/cs/faculty/cole/papers/CHPZ95.ps]}}
Нет описания правки
Массивы <tex>bmBc</tex> и <tex>bmGs</tex> вычисляются за <tex>O(m+\sigma)</tex> времени до основной фазы поиска и требуют, очевидно, <tex>O(m+\sigma)</tex> памяти.
==Псевдо-кодПсевдокод==
Константой <tex>|\Sigma|=\sigma=ASIZE</tex> обозначим размер нашего алфавита.
Функция для вычисления таблицы сдвигов плохих символов. Она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона). Вычисляется прямо по определению за <tex>O(m+\sigma)</tex>
'''int'''[] '''preBmBc'''('''string''' x, '''int''' m):
'''int''' bmBc[ASIZE]
<font color=green>// Значение по умолчанию = m</font>
Также, очевидно, что значение функции для последнего элемента будет равно длине всей строки.
'''int'''[] '''suffixes'''(string x, int m):
'''int''' f = 0
'''int''' suff[m]
Функция для вычисления сдвигов хороших суффиксов
'''void''' '''preBmGs'''(string x, int m):
'''int''' i, j, suff[XSIZE]
'''int''' bmGs[]
Основная функция алгоритма Бойера-Мура
'''void''' '''BM'''(string x, int m, string y, int n):
'''int''' bmGs[m]
'''int''' bmBc[ASIZE]
где <tex>n</tex> {{---}} длина исходного текста, <tex>m</tex> {{---}} длина шаблона, <tex>\sigma</tex> {{---}} размер алфавита.
==Сравнение с другими алгоритмами==
* Алгоритмы семейства Бойера-Мура не расширяются до приблизительного поиска, поиска любой строки из нескольких.
* На больших алфавитах (например, Юникод) может занимать много памяти. В таких случаях либо обходятся хэш-таблицами, либо дробят алфавит, рассматривая, например, 4-байтовый символ как пару двухбайтовых.
* На искусственно подобранных неудачных текстах (например, шаблон "<tex>abcabcabcabcabc"</tex>) скорость алгоритма Бойера-Мура серьёзно снижается. ==Варианты=====Алгоритм Бойера — Мура — Хорспула===Этот алгоритм работает лучше Бойера-Мура на случайных текстах — для него оценка в среднем лучше.Алгоритм использует только сдвиги плохих символов, при этом за такой символ берётся символ из исходного текста, который соответствует последнему символу шаблона, независимо от того, где случилось несовпадение.Поскольку реальные поисковые образцы редко имеют равномерное распределение, алгоритм Бойера-Мура-Хорспула может дать как выигрыш, так и проигрыш по сравнению с стандартной реализацией.===Алгоритм Чжу — Такаоки===На коротких алфавитах сдвиги плохих символов не помогают уже на коротких суффиксах. Простейший способ улучшить работу алгоритма в таких условиях — вместо одного плохого символа строить таблицу для пары символов: несовпавшего и идущего перед ним. Такой алгоритм получил собственное имя: алгоритм Чжу — Такаоки.На предварительную обработку расходуется <tex>O(m+\sigma^2)</tex> времени.
==Ссылки==
