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

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

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

Определения

Выравнивание шаблона PAN по тексту ANPANMAN от
k =3 до k=8 . Соответствие происходит при k=5 .

T обозначает входной текст для поиска. Его длина равна n .
P обозначает строку, которую нужно найти, называемую шаблоном . Ее длина равна m .
S [ i ] обозначает символ с индексом i строки S , считая от 1.
S [ i .. j ] обозначает подстроку строки S, начинающуюся с индекса i и заканчивающуюся на j включительно.
Префикс S — это подстрока S [1.. i ] для некоторого i из диапазона [1, l ], где l — длина S .
Суффиксом строки S является подстрока S [ i .. l ] для некоторого i из диапазона [1, l ], где l — длина строки S .
Выравнивание P по T — это индекс k в T, такой что последний символ P выровнен с индексом k в T.
Совпадение или вхождение P происходит при выравнивании k, если P эквивалентно T [ ( k - m +1).. k ] .

Описание

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

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

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

Более формально, алгоритм начинается с выравнивания ⁠ ⁠ $к=м$ , поэтому начало $P$ выравнивается с началом $T$ . Затем символы в $P$ и $T$ сравниваются, начиная с индекса $m$ в $P$ и $k$ в $T$ , двигаясь назад. Строки сопоставляются от конца $P$ до начала $P$ . Сравнения продолжаются до тех пор, пока не будет достигнуто начало $P$ (что означает, что есть совпадение), или пока не произойдет несовпадение, при котором выравнивание смещается вперед (вправо) в соответствии с максимальным значением, разрешенным рядом правил. Сравнения выполняются снова при новом выравнивании, и процесс повторяется до тех пор, пока выравнивание не сместится за конец $T$ , что означает, что больше совпадений найдено не будет.

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

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

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

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

Описание

Демонстрация правила плохого символа с шаблоном P = NNAAMAN . В столбце, отмеченном знаком X , есть несоответствие между N (во входном тексте) и A (в шаблоне) . Шаблон смещается вправо (в данном случае на 2), так что находится следующее вхождение символа N (в шаблоне P ) слева от текущего символа (который является средним A ).

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

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

Методы различаются в зависимости от точной формы, которую должна принять таблица для правила плохого символа, но простое решение поиска с постоянным временем выглядит следующим образом: создайте двумерную таблицу, которая индексируется сначала индексом символа $c$ в алфавите, а затем индексом $i$ в шаблоне. Этот поиск вернет вхождение $c$ в $P$ со следующим по величине индексом ⁠ ⁠ $j<i$ или -1, если такого вхождения нет. Тогда предлагаемый сдвиг будет ⁠ ⁠ $ij$ , с ⁠ ⁠ $O(1)$ временем поиска и ⁠ ⁠ $O(км)$ пространством, предполагая, что алфавит имеет конечную длину $k$ .

Реализации C и Java ниже имеют ⁠ ⁠ $O(к)$ сложность пространства (make_delta1, makeCharTable). Это то же самое, что и исходная delta1 и таблица плохих символов BMH . Эта таблица сопоставляет символ в позиции ⁠ ⁠ $я$ со сдвигом на ⁠ ⁠ $\operatorname {len} (p)-1-i$ , причем последний экземпляр — наименьшая величина сдвига — имеет приоритет. Все неиспользуемые символы устанавливаются как ⁠ ⁠ $\operatorname {len} (p)$ как контрольное значение.

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

Описание

Демонстрация правила хорошего суффикса с шаблоном P = ANAMPNAM . Здесь t — это T [6..8], а t ′ — это P [2..4].

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

Предположим, что для заданного выравнивания P и T подстрока t из T соответствует суффиксу P , и предположим, что t является наибольшей такой подстрокой для заданного выравнивания.
Затем найдите, если она существует, самую правую копию t ′ строки t в P такую, что t ′ не является суффиксом P и символ слева от t ′ в P отличается от символа слева от t в P. Сдвиньте P вправо так, чтобы подстрока t ′ в P выровнялась с подстрокой t в T.
Если t ′ не существует, то сдвиньте левый конец P вправо на наименьшую величину (за левый конец t в T ) так, чтобы префикс сдвинутого шаблона совпадал с суффиксом t в T . Это включает в себя случаи, когда t является точным совпадением P .
Если такой сдвиг невозможен, то сдвигаем P на m (длина P) позиций вправо.

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

Правило хорошего суффикса требует двух таблиц: одну для использования в общем случае (где найдена копия t ′ $), а другую для использования, когда общий случай не возвращает осмысленного результата. Эти таблицы будут обозначены L$ и $H$ соответственно. Их определения следующие: ^[5]

Для каждого $i$ , ⁠ ⁠ $L[я]$ — это наибольшая позиция, меньшая $m$ , такая, что строка ⁠ ⁠ $P[i..m]$ соответствует суффиксу ⁠ ⁠ $P[1..L[i]]$ и такая, что символ, предшествующий этому суффиксу, не равен ⁠ ⁠ $P[i-1]$ . ⁠ ⁠ $L[я]$ определяется как нуль, если нет позиции, удовлетворяющей условию.

Пусть ⁠ ⁠ $H[я]$ обозначает длину наибольшего суффикса ⁠ ⁠, $P[i..m]$ который также является префиксом $P$ , если таковой существует. Если такового не существует, пусть ⁠ ⁠ $H[я]$ будет равен нулю.

Обе эти таблицы можно построить за ⁠ ⁠ $O(м)$ время и использовать ⁠ ⁠ $O(м)$ пространство. Сдвиг выравнивания для индекса $i$ в $P$ задается как ⁠ ⁠ $мл[я]$ или ⁠ ⁠ $mH[i]$ . $H$ следует использовать только если ⁠ ⁠ $L[я]$ равно нулю или было найдено совпадение.

Пример сдвига с использованием шаблона ANPANMAN

Индекс | Несоответствие | Сдвиг  0 | Н| 1  1 | АН| 8  2 | МУЖЧИНА| 3  3 | НМАН| 6  4 | АНМАН| 6  5 | ПАНМАН| 6  6 | НПАНМАН| 6  7 | АМПАНМАН| 6

Объяснение:

Индекс 0, нет совпавших символов, прочитанный символ не был N. Длина хорошего суффикса равна нулю. Поскольку в шаблоне много букв, которые также не являются N, у нас здесь минимальная информация — сдвиг на 1 является наименее интересным результатом.

Индекс 1, мы сопоставили N, и ему предшествовало что-то, отличное от A. Теперь посмотрим на шаблон, начиная с конца, где у нас N, которому предшествует что-то, отличное от A? Есть еще два N, но обоим предшествует A. Это значит, что никакая часть хорошего суффикса не может быть нам полезна — сдвиг на полную длину шаблона 8.

Индекс 2: Мы сопоставили AN, и ему предшествовало не M. В середине шаблона есть AN, которому предшествует P, поэтому он становится кандидатом на сдвиг. Сдвиг этого AN вправо для выравнивания с нашим соответствием — это сдвиг на 3.

Индекс 3 и выше: сопоставленные суффиксы не соответствуют ничему другому в шаблоне, но конечный суффикс AN соответствует началу шаблона, поэтому все сдвиги здесь равны 6. ^[6]

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

Простая, но важная оптимизация Бойера-Мура была предложена Цви Галилом в 1979 году . ^[7] В отличие от сдвига, правило Галила имеет дело с ускорением фактических сравнений, выполняемых при каждом выравнивании, путем пропуска разделов, которые известны как совпадающие. Предположим, что при выравнивании $k 1$ , $P$ сравнивается с $T$ до символа $c$ из $T$ . Затем, если $P$ сдвигается на $k 2$ таким образом, что его левый конец оказывается между $c$ и $k 1$ , на следующей фазе сравнения префикс $P$ должен соответствовать подстроке $T [(k 2 - n).. k 1]$ . Таким образом, если сравнения дойдут до позиции $k 1$ из $T$ , вхождение $P$ может быть записано без явного сравнения после $k 1$ . Помимо повышения эффективности Бойера-Мура, правило Галила требуется для доказательства линейного времени выполнения в худшем случае.

Правило Галила в его первоначальной версии эффективно только для версий, которые выводят несколько совпадений. Оно обновляет диапазон подстрок только при $c = 0$ , т. е. полном совпадении. Обобщенная версия для работы с подсовпадениями была представлена в 1985 году как алгоритм Апостолико–Джанкарло . ^[8]

Производительность

Алгоритм Бойера–Мура, представленный в оригинальной статье, имеет худшее время выполнения ⁠ ⁠ $O(n+m)$ только если шаблон не появляется в тексте. Это было впервые доказано Кнутом , Моррисом и Праттом в 1977 году ^[3] , а затем Гибасом и Одлыжко в 1980 году ^[9] с верхней границей $5 n$ сравнений в худшем случае. Ричард Коул дал доказательство с верхней границей $3 n$ сравнений в худшем случае в 1991 году ^[10].

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

Реализации

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

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

Варианты

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

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

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

Примечания

^ m — длина строки шаблона, которую мы ищем в тексте, которая имеет длину n . Эта среда выполнения предназначена для поиска всех вхождений шаблона, без правила Галила.
^ k — размер алфавита. Это пространство предназначено для оригинальной таблицы плохих символов delta1 в реализациях C и Java и таблицы хороших суффиксов.

Ссылки

^ Хьюм, Эндрю; Сандей, Дэниел (ноябрь 1991 г.). «Быстрый поиск строк». Программное обеспечение: практика и опыт . 21 (11): 1221–1248. doi :10.1002/spe.4380211105. S2CID 5902579.
^ Boyer, Robert S. ; Moore, J Strother (октябрь 1977 г.). «Быстрый алгоритм поиска строк». Comm. ACM . 20 (10). Нью-Йорк: Ассоциация вычислительной техники: 762–772. doi : 10.1145/359842.359859 . ISSN 0001-0782. S2CID 15892987.
^ ab Knuth, Donald E. ; Morris, James H. Jr. ; Pratt, Vaughan R. (1977). «Быстрое сопоставление шаблонов в строках». SIAM Journal on Computing . 6 (2): 323–350. CiteSeerX 10.1.1.93.8147 . doi :10.1137/0206024. ISSN 0097-5397.
^ Риттер, Войцех (1980). «Правильный алгоритм предварительной обработки для поиска строк Бойера–Мура». Журнал SIAM по вычислениям . 9 (3): 509–512. doi :10.1137/0209037. ISSN 0097-5397.
^ ab Gusfield, Dan (1999) [1997], "Глава 2 - Точное совпадение: классические методы, основанные на сравнении", Алгоритмы для строк, деревьев и последовательностей (1-е изд.), Cambridge University Press, стр. 19–21, ISBN 0-521-58519-8
^ "Constructing a Good Suffix Table - Understanding an example". Stack Overflow . 11 декабря 2014 . Получено 30 июля 2024 . В данной статье использован текст из этого источника, доступный по лицензии CC BY-SA 3.0.
^ ab Galil, Z. (сентябрь 1979 г.). «Об улучшении худшего времени выполнения алгоритма сопоставления строк Бойера–Мура». Comm. ACM . 22 (9). Нью-Йорк: Ассоциация вычислительной техники: 505–508. doi : 10.1145/359146.359148 . ISSN 0001-0782. S2CID 1333465.
^ Апостолико, Альберто; Джанкарло, Раффаэле (февраль 1986 г.). «Повторный взгляд на стратегии поиска строк Бойера–Мура–Галиля». Журнал SIAM по вычислениям . 15 : 98–105. doi :10.1137/0215007.
^ Guibas, Leonidas ; Odlyzko, Andrew (1977). «Новое доказательство линейности алгоритма поиска строк Бойера–Мура». Труды 18-го ежегодного симпозиума по основам компьютерной науки . SFCS '77. Вашингтон, округ Колумбия: IEEE Computer Society: 189–195. doi :10.1109/SFCS.1977.3. S2CID 6470193.
^ ab Cole, Richard (сентябрь 1991 г.). "Жесткие границы сложности алгоритма сопоставления строк Бойера–Мура". Труды 2-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Soda '91. Филадельфия, Пенсильвания: Общество промышленной и прикладной математики: 224–233. ISBN 0-89791-376-0.
^ Haertel, Mike (21 августа 2010 г.). "почему GNU grep быстр". Архив рассылки FreeBSD-current .

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

На Викискладе есть медиафайлы по теме «Алгоритм поиска строк Бойера–Мура» .

Оригинальная статья по алгоритму Бойера-Мура
Пример алгоритма Бойера-Мура с домашней страницы Дж. Стротера Мура , соавтора алгоритма
Статья Ричарда Коула 1991 года, доказывающая линейность времени выполнения