WikiDer > Алгоритм поиска строки Бойера – Мура

Boyer–Moore string-search algorithm
Строковый поиск Бойера – Мура
КлассСтроковый поиск
Структура данныхСтрока
Худший случай спектакльΘ (m) предварительная обработка + O (mn) сопоставление[примечание 1]
Лучший случай спектакльΘ (m) предварительная обработка + Ω (n / m) согласование
Худший случай космическая сложностьΘ (к)[заметка 2]

В Информатика, то Алгоритм поиска строки Бойера – Мура эффективный алгоритм поиска строки это стандартный ориентир для практической литературы по поиску строк.[1] Он был разработан Роберт С. Бойер и Дж. Стротер Мур в 1977 г.[2] Исходный документ содержал статические таблицы для вычисления сдвигов паттернов без объяснения того, как их производить. Алгоритм создания таблиц был опубликован в следующей статье; эта статья содержала ошибки, которые позже были исправлены Войцех Риттер в 1980 г.[3][4] В алгоритм препроцессы то строка ищется (шаблон), но не строка, в которой ищется (текст). Таким образом, он хорошо подходит для приложений, в которых шаблон намного короче текста или где он сохраняется при нескольких поисках. Алгоритм Бойера – Мура использует информацию, собранную на этапе предварительной обработки, для пропуска частей текста, что приводит к более низкому постоянному коэффициенту, чем многие другие алгоритмы поиска по строкам. В общем, алгоритм работает быстрее по мере увеличения длины шаблона. Ключевые особенности алгоритма состоят в том, чтобы соответствовать хвосту шаблона, а не его заголовку, и пропускать текст скачками из нескольких символов, а не искать каждый отдельный символ в тексте.

Определения

АNпАNMАN-
пАN------
-пАN-----
--пАN----
---пАN---
----пАN--
-----пАN-
Выравнивания узора СКОВОРОДА печатать АНПАНМАН, от k = 3 к к = 8. Матч происходит в к = 5.
  • S[я] обозначает символ в индексе я строки S, считая от 1.
  • S[я..j] обозначает подстрока строки S начиная с индекса я и заканчивая j, включительно.
  • А приставка из S это подстрока S[1..я] для некоторых я в диапазоне [1, п], где п это длина S.
  • А суффикс из S это подстрока S[я..п] для некоторых я в диапазоне [1, п], где п это длина S.
  • Строка, которую нужно искать, называется шаблон и обозначается п. Его длина п.
  • Строка, в которой выполняется поиск, называется текст и обозначается Т. Его длина м.
  • An выравнивание из п к Т это индекс k в Т так что последний символ п выровнен с индексом k из Т.
  • А матч или вхождение из п происходит при выравнивании, если п эквивалентно Т[(k-п+1)..k].

Описание

Алгоритм Бойера – Мура ищет вхождения п в Т путем выполнения явного сравнения символов при разных выравниваниях. Вместо перебор всех выравниваний (из них ), Бойер-Мур использует информацию, полученную при предварительной обработке п чтобы пропустить как можно больше выравниваний.

До появления этого алгоритма обычным способом поиска в тексте было изучение каждого символа текста на предмет первого символа шаблона. Как только это будет найдено, последующие символы текста будут сравниваться с символами шаблона. Если совпадений не было, то текст снова будет проверяться посимвольно, чтобы найти совпадение. Таким образом, необходимо проверить почти каждый символ в тексте.

Ключевым моментом в этом алгоритме является то, что если конец шаблона сравнивается с текстом, то можно делать переходы по тексту, а не проверять каждый символ текста. Причина, по которой это работает, заключается в том, что при выравнивании шаблона по тексту последний символ шаблона сравнивается с символом в тексте. Если символы не совпадают, нет необходимости продолжать поиск в обратном направлении по тексту. Если символ в тексте не соответствует ни одному из символов в шаблоне, то будет найден следующий символ в тексте для проверки. п символы дальше по тексту, где п длина выкройки. Если символ в тексте является в шаблоне выполняется частичный сдвиг шаблона по тексту, чтобы выровняться по совпадающему символу, и процесс повторяется. Переход по тексту для сравнения вместо проверки каждого символа в тексте уменьшает количество сравнений, которые необходимо выполнить, что является ключом к эффективности алгоритма.

Более формально алгоритм начинается с выравнивания , так что начало п совпадает с началом Т. Персонажи в п и Т затем сравниваются, начиная с индекса п в п и k в Т, двигаясь назад. Строки сопоставляются с конца п к началу п. Сравнение продолжается до начала п достигается (что означает совпадение) или возникает несоответствие, при котором выравнивание сдвигается вперед (вправо) в соответствии с максимальным значением, разрешенным рядом правил. Сравнение выполняется снова при новом выравнивании, и процесс повторяется до тех пор, пока выравнивание не смещается за конец Т, что означает, что больше совпадений найдено не будет.

Правила сдвига реализованы как поиск в таблице с постоянным временем с использованием таблиц, сгенерированных во время предварительной обработки п.

Правила смены

Сдвиг рассчитывается с применением двух правил: правила плохого символа и правила хорошего суффикса. Фактическое смещение смещения - это максимальное смещение, рассчитанное по этим правилам.

Правило плохого характера

Описание

----Икс--K---
АNпАNMАNАM-
-NNААMАN---
---NNААMАN-
Демонстрация правила плохого характера с шаблоном ННААМАН.

Правило плохого персонажа рассматривает персонажа в Т при котором процесс сравнения завершился неудачно (при условии, что такая ошибка произошла). Следующее вхождение этого символа слева в п найден, и сдвиг, который приводит это событие в соответствие с несовпадающим вхождением в Т предлагается. Если несоответствующий символ не встречается слева в п, предлагается сдвиг, который перемещает всю п мимо точки несоответствия.

Предварительная обработка

Методы различаются в зависимости от точной формы, которую должна принимать таблица для правила плохого символа, но простое решение для поиска с постоянным временем выглядит следующим образом: создать 2D-таблицу, которая сначала индексируется по индексу символа. c по алфавиту и секунд по индексу я в выкройке. Этот поиск вернет вхождение c в п со следующим по величине индексом или -1, если такого случая нет. Предлагаемая смена тогда будет , с участием время поиска и пространство, предполагая конечный алфавит длины k.

Реализации C и Java ниже имеют сложность пространства (make_delta1, makeCharTable). Это то же самое, что и исходная delta1, а Таблица неверных символов BMH. Эта таблица отображает символ в позиции сдвинуть , причем последний экземпляр - наименьшее количество сдвига - имеет приоритет. Все неиспользуемые символы устанавливаются как как контрольное значение.

Правило хорошего суффикса

Описание

----Икс--K-----
MАNпАNАMАNАп-
АNАMпNАM-----
----АNАMпNАM-
Демонстрация хорошего суффиксного правила с шаблоном АНАМПНАМА.

Правило хорошего суффикса значительно сложнее как по концепции, так и по реализации, чем правило плохого символа. Как и правило плохого символа, оно также использует свойство алгоритма сравнения, начинающегося в конце шаблона и продолжающегося к началу шаблона. Его можно описать так:[5]

Предположим, для данного выравнивания п и Т, подстрока т из Т совпадает с суффиксом п, но при следующем сравнении слева возникает несоответствие. Затем найдите, если он существует, самую правую копию т ' из т в п такой, что т ' не является суффиксом п и символ слева от т ' в п отличается от символа слева от т в п. сдвиг п вправо, чтобы подстрока т ' в п выравнивается с подстрокой т в Т. Если т ' не существует, сдвиньте левый конец п за левым концом т в Т на наименьшую величину, чтобы префикс сдвинутого шаблона совпадал с суффиксом т в Т. Если такой сдвиг невозможен, то сдвигайте п от п места справа. Если возникновение п найден, то сдвиг п на наименьшую величину, чтобы правильный префикс сдвинутого п совпадает с суффиксом появления п в Т. Если такой сдвиг невозможен, то сдвигайте п от п места, то есть сдвиг п прошлое т.

Предварительная обработка

Правило хорошего суффикса требует двух таблиц: одну для использования в общем случае, а другую для использования, когда либо общий случай не возвращает значимого результата, либо происходит совпадение. Эти таблицы будут обозначены L и ЧАС соответственно. Их определения следующие:[5]

Для каждого я, самая большая позиция меньше чем п такая строка совпадает с суффиксом и такой, что символ, предшествующий этому суффиксу, не равен . считается равным нулю, если нет позиции, удовлетворяющей условию.

Позволять обозначают длину наибольшего суффикса это также префикс п, если таковой существует. Если его нет, пусть быть нулевым.

Обе эти таблицы могут быть построены в время и использование Космос. Сдвиг выравнивания для индекса я в п дан кем-то или . ЧАС следует использовать только если равен нулю или найдено совпадение.

Правило Галиля

Простая, но важная оптимизация Бойера – Мура была предложена Галил в 1979 г.[6]В отличие от сдвига, правило Галиля имеет дело с ускорением фактических сравнений, выполняемых при каждом выравнивании, путем пропуска разделов, которые, как известно, совпадают. Предположим, что при выравнивании k1, п сравнивается с Т вплоть до характера c из Т. Тогда если п переносится на k2 так что его левый конец находится между c и k1, на следующем этапе сравнения префикс п должна соответствовать подстроке Т[(k2 - п)..k1]. Таким образом, если сравнения сводятся к позиции k1 из Т, появление п можно записать без явного сравнения прошлых k1. Помимо повышения эффективности Бойера – Мура, правило Галиля требуется для доказательства линейного выполнения в наихудшем случае.

Правило Galil в его исходной версии действует только для версий, которые выводят несколько совпадений. Он обновляет диапазон подстроки только на c = 0, т.е. полное совпадение. Обобщенная версия для работы с подматчами была представлена ​​в 1985 году как Алгоритм Апостолико – Джанкарло.[7]

Спектакль

Алгоритм Бойера-Мура, представленный в исходной статье, имеет время работы в худшем случае только если шаблон не появляются в тексте. Впервые это было доказано Knuth, Моррис, и Пратт в 1977 г.[8]с последующим Гибас и Одлызко в 1980 г.[9] с верхней границей 5п сравнения в худшем случае. Ричард Коул дал доказательство с оценкой сверху 3п сравнения в худшем случае в 1991 году.[10]

Когда узор делает встречаются в тексте, время работы исходного алгоритма равно в худшем случае. Это легко увидеть, если и шаблон, и текст состоят исключительно из одного и того же повторяющегося символа. Однако включение Правило Галила приводит к линейному времени выполнения во всех случаях.[6][10]

Реализации

Существуют разные реализации на разных языках программирования. В C ++ это часть стандартной библиотеки, начиная с C ++ 17, а также Увеличение предоставляет общий поиск Бойера – Мура реализация в рамках Алгоритм библиотека. В Go (язык программирования) есть реализация в search.go. D (язык программирования) использует BoyerMooreFinder для сопоставления на основе предикатов в пределах диапазонов как часть библиотеки времени выполнения Phobos.

Алгоритм Бойера – Мура также используется в GNUс grep.[11]

Ниже приведены несколько простых реализаций.

Варианты

В Алгоритм Бойера – Мура – ​​Хорспула представляет собой упрощение алгоритма Бойера – Мура, использующее только правило плохих символов.

В Алгоритм Апостолико – Джанкарло ускоряет процесс проверки совпадения при заданном выравнивании, пропуская явные сравнения символов. При этом используется информация, полученная во время предварительной обработки шаблона, в сочетании с длинами совпадений суффиксов, записанными при каждой попытке сопоставления. Для хранения длин совпадений суффиксов требуется дополнительная таблица, размер которой равен размеру искомого текста.

В Алгоритм Раита улучшает производительность алгоритма Бойера-Мура-Хорспула. Шаблон поиска конкретной подстроки в данной строке отличается от алгоритма Бойера-Мура-Хорспула.

Заметки

  1. ^ м это длина строки шаблона, которую мы ищем в тексте, которая имеет длину п. Эта среда выполнения предназначена для поиска всех вхождений шаблона без правила Galil.
  2. ^ k это размер алфавита

использованная литература

  1. ^ Юм; Воскресенье (ноябрь 1991 г.). «Быстрый поиск строки». Программное обеспечение - практика и опыт. 21 (11): 1221–1248. Дои:10.1002 / spe.4380211105. S2CID 5902579.
  2. ^ Бойер, Роберт С.; Мур, Дж. Стротер (Октябрь 1977 г.). «Алгоритм быстрого поиска строки». Comm. ACM. Нью-Йорк: Ассоциация вычислительной техники. 20 (10): 762–772. Дои:10.1145/359842.359859. ISSN 0001-0782. S2CID 15892987.
  3. ^ Knuth, Donald E .; Моррис младший, Джеймс Х .; Пратт, Воан Р. (1977). «Быстрое сопоставление с образцом в строках». SIAM Журнал по вычислениям. 6 (2): 323–350. Дои:10.1137/0206024. ISSN 0097-5397.
  4. ^ Риттер, Войцех (1980). "Правильный алгоритм предварительной обработки для поиска строки Бойера – Мура". SIAM Журнал по вычислениям. 9 (3): 509–512. Дои:10.1137/0209037. ISSN 0097-5397.
  5. ^ а б Гасфилд, Дэн (1999) [1997], «Глава 2 - Точное соответствие: классические методы, основанные на сравнении», Алгоритмы на строках, деревьях и последовательностях (1-е изд.), Cambridge University Press, стр. 19–21, ISBN 0521585198
  6. ^ а б Галиль, З. (Сентябрь 1979 г.). «Об улучшении наихудшего времени работы алгоритма сопоставления строк Бойера – Мура». Comm. ACM. Нью-Йорк: Ассоциация вычислительной техники. 22 (9): 505–508. Дои:10.1145/359146.359148. ISSN 0001-0782. S2CID 1333465.
  7. ^ Апостолико, Альберто; Джанкарло, Рафаэле (февраль 1986 г.). "Новый взгляд на стратегии поиска струн Бойера – Мура – ​​Галила". SIAM Журнал по вычислениям. 15: 98–105. Дои:10.1137/0215007.
  8. ^ Кнут, Дональд; Моррис, Джеймс Х.; Пратт, Воган (1977). «Быстрое сопоставление с образцом в строках». SIAM Журнал по вычислениям. 6 (2): 323–350. CiteSeerX 10.1.1.93.8147. Дои:10.1137/0206024.
  9. ^ Гибас, Леонидас; Одлызко Андрей (1977). «Новое доказательство линейности алгоритма поиска строки Бойера – Мура». Материалы 18-го ежегодного симпозиума по основам компьютерных наук. Вашингтон, округ Колумбия: Компьютерное общество IEEE: 189–195. Дои:10.1109 / SFCS.1977.3. S2CID 6470193.
  10. ^ а б Коул, Ричард (сентябрь 1991 г.). «Тесные границы сложности алгоритма сопоставления строк Бойера – Мура». Материалы 2-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Филадельфия, Пенсильвания: Общество промышленной и прикладной математики: 224–233. ISBN 0-89791-376-0.
  11. ^ https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html

внешние ссылки