Алгоритм Бойера-Мура

Материал из Кафедра АСОИУ.

Перейти к: навигация, поиск

Содержание

Пожалуй у каждого заядлого компьютерщика при перелистывании страниц книги в поисках нужного фрагмента, промелькивала мысль "Ох авторы книги... не могли встроить поиск?" :-) Действительно, программы приучили нас к такой удобной возможности, как поиск фрагментов, и если вы разрабатываете подобную программу, пользователь вправе ожидать, что вы предоставите в его распоряжение соответствующие команды, причем он вправе ожидать, что при использовании вашей функции, затратился минимум времени на поиск и этот процесс потратит минимум Ватт электроэнергии. Эту проблему нельзя эффективно решить при помощи стандартных функций С/С++, поскольку большинство средств разработки включает только малоэффективные реализации. Во-первых, в стандартных функциях не всегда используются самые эффективные алгоритмы, а во-вторых, вполне возможно, что вам понадобится изменить стандартное поведение этих функций.

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

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

Одномерный вариант алгоритма Бойера-Мура

Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Прежде чем рассмотреть работу этого алгоритма, уточним некоторые термины. Под строкой мы будем понимать всю последовательность символов текста. Собственно говоря, речь не обязательно должна идти именно о тексте. В общем случае строка – это любая последовательность байтов. Поиск подстроки в строке осуществляется по заданному образцу, т. е. некоторой последовательности байтов, длина которой не превышает длину строки. Наша задача заключается в том, чтобы определить, содержит ли строка заданный образец.

Одномерный вариант алгоритма Бойера-Мура состоит из следующих шагов:

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

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

Величина сдвига в случае несовпадения последнего символа вычисляется исходя из следующих соображений:

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

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

Поясним все вышесказанное на простом примере. Пусть у нас есть набор символов из пяти символов: a, b, c, d, e и мы хотим найти вхождение образца "abbad" в строке "abeccacbadbabbad". Следующие схемы иллюстрируют все этапы выполнения алгоритма:

  • Строим таблицу смещений для образца "abbad":
abcde
12505
  • Начало поиска:
abeccacbadbabbad
abbad

Последний символ образца не совпадает с наложенным символом строки.

  • Сдвигаем образец вправо на 5 позиций:
abeccacbadbabbad
abbad

Три символа образца совпали, а четвертый – нет.

  • Сдвигаем образец вправо на одну позицию:
abeccacbadbabbad
abbad

Последний символ снова не совпадает с символом строки.

  • В соответствии с таблицей смещений сдвигаем образец на 2 позиции:
abeccacbadbabbad
abbad
  • Еще раз сдвигаем образец на 2 позиции:
abeccacbadbabbad
abbad
  • Теперь, в соответствии с таблицей, сдвигаем образец на одну позицию, и получаем искомое вхождение образца:
abeccacbadbabbad
abbad

Как видно по примеру применение алгоритма Бойера-Мура очень существенно сокращает количество операций сравнения (всего ~18) в отличии от метода грубой силы (~78 операций сравнения) и разрыв только увеличивается при увеличении длины образца. Приведем результаты небольшого теста по сравнению реализации этого алгоритма и стандартных функций поиска подстроки в строке:

  • Строка содержит образец
string::find  found,     251 ticks
strstr()      found,     230 ticks
CString::Find found,     221 ticks
Бойер-Мур     found,      81 ticks
  • Строка не содержит образец
string::find  not found, 581 ticks
CString::Find not found, 551 ticks
strstr()      not found, 540 ticks
Бойер-Мур     not found, 270 ticks

Тест проводился на строке размером 128 Кбайт, и образца - 13 байт, машина Celeron 1000, 512 Mб, компилятор MSVC6 SP5, приведенные цифры - число тиков таймера при выполнении цикла (1000 итераций), усредненные по результатам 5 прогонов.

Двумерный вариант алгоритма Бойера-Мура

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

abdab
a03301
b30350
c33355
d33052
e33355

Заполнение таблицы начинается с последнего столбца. Самый правый столбец таблицы фактически соответствует массиву, который используется в одномерном варианте алгоритма. Следующие столбцы содержат значения сдвига для образца при условии, что предыдущие (при движении справа налево) символы совпали, т.е. "грубый" метод построения таблицы выглядит следующим образом:

  • Фиксируем текущий столбец (начинаем построение с крайнего правого столбца).
  • Формируем подстроку - берем первым символом подстроки очередной символ строки таблицы (начиная с первой строки) и дополняем его справа символами столбцов справа от текущего.
  • Конец подстроки совмещаем с концом образца.
  • Ищем, сдвигая влево подстроку, первое ее вхождение в образец.
  • Потребовавшееся число сдвигов записываем в пересечение текущего столбца и строки таблицы.

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

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

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

Модифицированные варианты алгоритма

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

Измененная последовательность проверки

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

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

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

  • Первый шаг остался неизмененным - совмещаем начало строки и образца, и проверяем последний символ образца.
  • Далее проверяем первый символ образца.
  • Проверяем середину образца.
  • И наконец проверяем все символы от середины до краев образца (вначале проверяем правый от центра символ, затем левый, затем правый от правого, левый от левого...).

Более полное использование таблицы

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

Рассмотрим в нашем примере второй этап поиска, когда совпало 3 символа "bad". При проверке следующего символа обнаружилось несоответствие и мы сдвинули образец на один символ вправо. Хотя постойте, мы при проверке обнаружили, что второй символ образца "b" не соответствует 7-му символу строки, а это символ "c" и он не встречается в образце, тогда разумнее передвинуть образец на два символа, а не на один как раньше.

Теперь подумаем над тем, как из таблицы получить это число, для тех, кто забыл, что находится в таблице повторяю - в ней находятся "расстояние" от конца образца до первого (считая с конца) вхождения конкретного символа из алфавита в образец. Очевидно, что если сразу брать значение из таблицы соответствующее "c", то ничего хорошего не получится, т.к. значения в таблице просчитаны с конца образца, а мы уже давно находимся в другом месте. Логично предположить, что взяв из таблицы значение соответствующее "c" и вычесть номер (нумерация с 0, начиная с конца образца) проверяемого символа мы получим "расстояние" от текущего положения в образце до первого следующего вхождения символа "c", т.е. 5 - 3 = 2 и мы получили искомое число. Не обращайте внимания, на то, что говорится про следующее вхождение символа "c", хотя этот символ не входит в образец.

Хорошо? Неочень! Представим случай, когда номер текущей позиции равен 6, а значение, полученное из таблицы - 2, тогда результат получится отрицательным, что в свою очередь означает, что мы уже прошли позицию первого (с права) вхождения символа и мы уже не знаем "расстояние" до следующего вхождения символа или есть ли он дальше вообще. Так, что все, что мы можем сделать, это только передвинуть образец вправо на один символ.

Использование хэш-функции

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

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

Mix модификаций

Попробуем модифицировать первую модификацию второй модификацией :-). Цель - совместить быстрое определение несоответствия символов из первой модификации с возможностью сдвига на несколько позиций.

Для этого разделим образец на 2 зоны:

  • Левая будет проверятся первой модификацией.
  • Соответственно правая - второй.

Основная проблема - выбрать эту границу зон. При выборе размера правой зоны лучше следовать следующим правилам:

  • Она не должна доходить до последнего первого (считая с конца) вхождения конкретного символа из алфавита в образец т.е. в таблице этому символу должно соответствовать пред максимальное значение.
  • Должна быть как можно меньше
  • Должна обеспечивать максимальный сдвиг при обнаружении несоответствия.

Итак новая стратегия выглядит следующим образом (будем считать, что все этапы завершились успешно):

  • Первый шаг остался неизмененным - совмещаем начало строки и образца, и проверяем последний символ образца.
  • Проверяем символы подряд с права на лево до определенной позиции (границы зон), при обнаружении несоответствия действуют правила второй модификации.
  • Далее опять же действуем по первой модификации, но в пределах первой зоны: проверяем первый символ образца.
  • Проверяем середину первой зоны.
  • И наконец проверяем все символы от середины до краев первой зоны.

Все было бы хорошо, но мы буквально уничтожили пользу от применения первой модификации, а именно:

Если взять обычный текст и искать образец, заканчивающийся на "нный"...

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

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

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

Поиск разряженного образца

Теперь поговорим о том, как же заставить алгоритм Бойера-Мура работать с разряженным образцом. Начнем, пожалуй, с одномерного варианта алгоритма.

Одномерный вариант алгоритма

Для начала попробуем на этапе поиска при встрече подстановочного символа "?" в образце просто пропустить его и идти дальше. А теперь вопрос: будет ли это работать? Ответ: неочень. Очевидно, что нужно еще и изменить таблицу, мы ведь не символ "?" ищем, а любой символ. Причем, т.к. таблица содержит значения до первых вхождений символов, а "?" - любой символ, то длина образца автоматически уменьшается до позиции первого с права вхождения символа "?". Например таблица для образца "?abbad" эквивалентна таблице "abbad".

Заменим в нашем примере "abbad" на "ca?ba" и попробуем что-нибудь найти:

  • Строим таблицу смещений для образца "ca?ba":
abcde
01222
  • Начало поиска:
abeccacbadbabbad
ca?ba

Последний символ образца не совпадает с наложенным символом строки.

  • Сдвигаем образец вправо на 2 позиции:
abeccacbadbabbad
ca?ba

Последний символ снова не совпадает с символом строки.

  • В соответствии с таблицей смещений сдвигаем образец на 2 позиции, и получаем искомое вхождение образца:
abeccacbadbabbad
ca?ba

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

Двумерный вариант алгоритма

Таблица (точнее только ее крайний правый столбец) для двумерного варианта строится с теми же соображениями, что и для одномерного. Например для предыдущего образца "ca?ba" таблица смещений будит выглядеть следующим образом:

ca?ba
a50020
b55001
c05032
d55052
e55052

Отличительная черта таблицы в том, что в столбце подстановочного символа все значения - нули, что впрочем очевидно ("?" - любой символ).

См. также

  • KDS - программа

Ссылки

Статьи

Форумы

Личные инструменты