Центральный Дом Знаний - Алгоритм Бойера — Мура

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Как Вы планируете отдохнуть летом?
Всего ответов: 922

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

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

Алгоритм Бойера — Мура поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером (англ. Robert S. Boyer) и Джеем Муром  в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускаются как заведомо не дающие результата.

Общая оценка вычислительной сложности алгоритма — O(|haystack|+|needle|+|Σ|) на непериодических шаблонах и O(|haystack|·|needle|+|Σ|) на периодических, где haystack — строка, в которой выполняется поиск, needle — шаблон поиска, Σ — алфавит, на котором проводится сравнение. В 1991 году Коул показал, что на непериодических шаблонах за полный проход по строке алгоритм совершит не более 3·|haystack| сравнений.

Алгоритм основан на трёх идеях.

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

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

Эти «несколько», упомянутые в предыдущем абзаце, вычисляются по двум эвристикам.

2. Эвристика стоп-символа. Предположим, что мы производим поиск слова «колокол». Первая же буква не совпала — «к» (назовём эту букву стоп-символом). Тогда можно сдвинуть шаблон вправо до последней буквы «к».

!

Строка: * * * * * * к * * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л

Если стоп-символа в шаблоне вообще нет, шаблон смещается за этот стоп-символ.

!

Строка: * * * * * а л * * * * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л

В данном случае стоп-символ — «а», и шаблон сдвигается так, чтобы он оказался прямо за этой буквой. В алгоритме Бойера-Мура эвристика стоп-символа вообще не смотрит на совпавший суффикс (см. ниже), так что первая буква шаблона («к») окажется под «л», и будет проведена одна заведомо холостая проверка.

Если стоп-символ «к» оказался за другой буквой «к», эвристика стоп-символа не работает.

!

Строка: * * * * к к о л * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л ?????

В таких ситуациях выручает третья идея АБМ — эвристика совпавшего суффикса.

3. Эвристика совпавшего суффикса. Если при сравнении строки и шаблона совпало один или больше символов, шаблон сдвигается в зависимости от того, какой суффикс совпал.

Строка: * * т о к о л * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л

В данном случае совпал суффикс «окол», и шаблон сдвигается вправо до ближайшего «окол». Если подстроки «окол» в шаблоне больше нет, но он начинается на «кол», сдвигается до «кол», и т. д.

Обе эвристики требуют предварительных вычислений — в зависимости от шаблона поиска заполняются две таблицы. Таблица стоп-символов по размеру соответствует алфавиту (например, если алфавит состоит из 256 символов, то её длина 256); таблица суффиксов — искомому шаблону. Именно из-за этого алгоритм Бойера-Мура не учитывает совпавший суффикс и несовпавший символ одновременно — это потребовало бы слишком много предварительных вычислений.

Опишем подробнее обе таблицы. 

Считается, что символы строк нумеруются с 1 (как в Паскале).

В таблице стоп-символов указывается последняя позиция в needle (исключая последнюю букву) каждого из символов алфавита. Для всех символов, не вошедших в needle, пишем 0 (для нумерации с 0 — соответственно, −1). Например, если needle=«abcdadcd», таблица стоп-символов будет выглядеть так.

Символ a b c d [все остальные]

Последняя позиция 5 2 7 6 0

Обратите внимание, для стоп-символа «d» последняя позиция будет 6, а не 8 — последняя буква не учитывается. Это известная ошибка, приводящая к неоптимальности. Для АБМ она не фатальна («вытягивает» эвристика суффикса), но фатальна для упрощённой версии АБМ — алгоритма Хорспула.

Если несовпадение произошло на позиции i, а стоп-символ c, то сдвиг будет i-StopTable[c].

[править]Таблица суффиксов

Для каждого возможного суффикса S шаблона needle указываем наименьшую величину, на которую нужно сдвинуть вправо шаблон, чтобы он снова совпал с S. Если такой сдвиг невозможен, ставится |needle| (в обеих системах нумерации). Например, для того же needle=«abcdadcd» будет:

Суффикс [пустой] d cd dcd ... abcdadcd

Сдвиг 1 2 4 8 ... 8

Иллюстрация

было ? ?d ?cd ?dcd ... abcdadcd

стало abcdadcd abcdadcd abcdadcd abcdadcd ... abcdadcd

Если шаблон начинается и заканчивается одной и той же комбинацией букв, |needle| вообще не появится в таблице. Например, для needle=«колокол» для всех суффиксов (кроме, естественно, пустого) сдвиг будет равен 4.

Суффикс [пустой] л ол ... олокол колокол

Сдвиг 1 4 4 ... 4 4

Иллюстрация

было ? ?л ?ол ... ?олокол колокол

стало колокол колокол колокол ... колокол колокол

Существует быстрый алгоритм вычисления таблицы суффиксов. Этот алгоритм использует префикс-функцию строки.

m = length(needle)

pi[] = префикс-функция(needle)

pi1[] = префикс-функция(обращение(needle))

for j=0..m

suffshift[j] = m - pi[m]

for i=1..m

j = m - pi1[i]

suffshift[j] = min(suffshift[j], i - pi1[i])

Здесь suffshift[0] соответствует всей совпавшей строке; suffshift[m] — пустому суффиксу. Поскольку префикс-функция вычисляется за O(|needle|) операций, вычислительная сложность этого шага также равняется O(|needle|).

]Пример работы алгоритма:

Искомый шаблон — «abbad». Таблица стоп-символов будет выглядеть как

Символ a b [остальные]

Позиция 4 3 0

Таблица суффиксов для всех возможных суффиксов (кроме пустого) даёт максимальный сдвиг — 5.

abeccaabadbabbad

abbad

Накладываем образец на строку. Совпадения суффикса нет — таблица суффиксов даёт сдвиг на одну позицию. Для несовпавшего символа исходной строки «с» (5-я позиция) в таблице стоп-символов записан 0. Сдвигаем образец вправо на 5-0=5 позиций.

abeccaabadbabbad

abbad

Символы 3—5 совпали, а второй — нет. Эвристика стоп-символа для «а» не работает (2-4=-2). Но поскольку часть символов совпала, в дело включается эвристика совпавшего суффикса, сдвигающая шаблон сразу на пять позиций!

abeccaabadbabbad

abbad

И снова совпадения суффикса нет. В соответствии с таблицей стоп-символов сдвигаем образец на 1 позицию и получаем искомое вхождение образца:

abeccaabadbabbad

abbad

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

Итак, пусть совпал суффикс S, needle=PbS, стоп-символ — a (в дальнейшем малые буквы — символы, большие — строки).

Строка: * * * * * * * a [-- S --] * * * *

Шаблон: [--- P ---] b [-- S --]

Эвристика стоп-символа. Работает, когда в строке S символ а отсутствует. Если P=WaV и в строке V нет символа а, то эвристика стоп-символа предлагает сдвиг на |V|+1 позицию.

Строка: * * * * * * * * * * * * a [-- S --] * * * * * * * *

Шаблон: [- W -] a [--- V ---] b [-- S --]

Пропустить: [- W -] a [--- V ---] b [-- S --]

Новый шаг: [- W -] a [--- V ---] b [-- S --]

Действительно, если в строке V нет буквы a, нечего пробовать пропущенные |V| позиций.

Если же в needle вообще нет символа а, то эвристика стоп-символа предлагает сдвиг на |P|+1 позицию — и также нет смысла пробовать пропущенные |P|.

Строка: * * * * * * * * a [-- S --] * * * * * * * *

Шаблон: [--- P ---] b [-- S --]

Пропустить: [--- P ---] b [-- S --]

Новый шаг: [--- P ---] b [-- S --]

Эвристика совпавшего суффикса. Сама неформальная фраза — «наименьшая величина, на которую нужно сдвинуть вправо шаблон, чтобы он снова совпал с S» — говорит, что меньшие сдвиги бесполезны. Поэтому взамен покажем корректность ускоренного алгоритма вычисления таблицы суффиксов — то есть, продемонстрируем, что он вычисляет именно этот «минимальный сдвиг».

Сначала рассмотрим первый цикл. pi(m) — это длина максимального суффикса needle, который является префиксом. Поэтому m−pi(m) — максимальный сдвиг, который обусловливается тем, что S и needle могут перекрываться и частично; дальше сдвигать недопустимо.

Например: даже если весь шаблон «колокол» совпал, дальше 4 символов сдвиг невозможен — например, в строке «колоколокол» шаблон «колокол» встречается дважды, на 1-й и на 5-й позиции.

haystack: колоколокол

Проба 1: колокол

Проба 2: колокол

Теперь рассмотрим второй цикл — он соответствует полному перекрытию S и needle. Покажем такой факт: если needle=P′SX=P′YS и других вхождений S в SX=YS нет, то в позиции, которая соответствует суффиксу S (то есть, m−|S|), будет записано ровно |X|=|Y| (при условии, что предыдущая оценка, связанная с частичным перекрытием, больше).

Рассмотрим итерацию i=|SX|=|YS|. Очевидно, что pi1(i) — это длина максимального префикса-суффикса строки SX=YS. Покажем, что эта величина равна именно |S|. Действительно, если эта величина больше |S|, то строку SX=YS можно разложить как TV=WT, причём |T|>|S|. Поскольку YS=WT, то T=QS, и SX=QSV при непустых строках Q и V. Получаем третье вхождение строки S в SX, противоречие. Отсюда pi1(i)=|S|, значит, в позицию m−pi1(i)=m−|S| записывается число i−pi1(i)=|SX|−|S|=|X|.

Выясним, может ли на какой-то итерации в эту ячейку записаться меньшее число. При i1<i: из условия отсутствия третьего вхождения S не может быть pi1(i1)=pi1(i). При i2>i: pi1(i2)=pi1(i)возможно, но в таком случае в ячейку будет записано |X|+i2−i, что больше |X|. 

Си:

Здесь occ — таблица стоп-символов, skip — таблица суффиксов. Для ясности листинга применён простейший, требующий O(|needle|²) операций, алгоритм расчёта таблицы суффиксов.

#include <string.h>
#include <limits.h>
 
/* Вход: needle+nlen - что искать
 * offset - позиция конца суффикса; suffixlen - его длина
 * Выход: 1, если есть совпадение суффикса (и нет совпадения более длинного суффикса)
 */
static int suffix_match(const unsigned char *needle, size_t nlen, size_t offset, size_t suffixlen)
{
 if (offset > suffixlen)
 return needle[offset - suffixlen - 1] != needle[nlen - suffixlen - 1] &&
 memcmp(needle + nlen - suffixlen, needle + offset - suffixlen, suffixlen) == 0;
 else
 return memcmp(needle + nlen - offset, needle, offset) == 0;
}
 
static size_t max(size_t a, size_t b)
{
 return a > b ? a : b; 
}
 
/* Вход: haystack - где искать, needle - что искать.
 * hlen - длина haystack, nlen - длина needle
 * Выход: указатель на первое вхождение needle в haystack, либо NULL
 */
const unsigned char* memmem_boyermoore
 (const unsigned char* haystack, size_t hlen,
 const unsigned char* needle, size_t nlen)
{
 size_t skip[nlen]; /* Таблица суффиксов */
 size_t occ[UCHAR_MAX + 1]; /* Таблица стоп-символов */
 
 if(nlen > hlen || nlen <= 0 || !haystack || !needle) 
 return NULL;
 
 /* ПОСТРОЕНИЕ ТАБЛИЦЫ СТОП-СИМВОЛОВ */
 
 /* Заполняем -1 (в Си нумерация символов с 0!!) */
 for(size_t a=0; a<UCHAR_MAX+1; ++a)
 occ[a] = -1;
 
 /* В таблицу occ записывается последнее вхождение в needle */
 /* (исключая последний символ) */
 for(size_t a = 0; a < nlen - 1; ++a) 
 occ[needle[a]] = a;
 
 /* ПОСТРОЕНИЕ ТАБЛИЦЫ СУФФИКСОВ */ 
 /* Упрощённый вариант. Можно реализовать быстрее. */
 for(size_t a = 0; a < nlen; ++a)
 {
 size_t offs = nlen;
 while(offs && !suffix_match(needle, nlen, offs, a))
 --offs;
 skip[nlen - a - 1] = nlen - offs;
 }
 
 /* ПОИСК */
 for(size_t hpos = 0; hpos <= hlen - nlen; )
 {
 size_t npos = nlen - 1;
 /* Сверка needle и haystack с конца */
 while(needle[npos] == haystack[npos + hpos])
 {
 if(npos == 0) 
 return haystack + hpos;
 
 --npos;
 }
 /* Не совпало! */
 hpos += max(skip[npos], npos - occ[haystack[npos + hpos]]);
 /* ^^^ ^^^^ */
 /* суффикс стоп-символ */
 }
 return NULL;
}

Алгоритм Бойера — Мура — Хорспула:

Этот алгоритм работает лучше Бойера-Мура на случайных текстах — для него оценка в среднем лучше.

АБМХ использует только эвристику стоп-символа, при этом за стоп-символ берётся символ haystack, который соответствует последнему символу needle, независимо от того, где случилось несовпадение.

Поскольку реальные поисковые образцы редко имеют равномерное распределение, алгоритм Бойера-Мура-Хорспула может дать как выигрыш, так и проигрыш по сравнению с АБМ.

Алгоритм Чжу — Такаоки:

На коротких алфавитах (например, при сравнении участков ДНК алфавит состоит всего из 4 символов: A, Т, Г, Ц) эвристика стоп-символа отказывает уже на коротких суффиксах. Простейший способ улучшить работу АБМ в таких условиях — вместо одного стоп-символа строить таблицу для пары символов: несовпавшего и идущего перед ним[3]. Такой алгоритм получил собственное имя: алгоритм Чжу — Такаоки.

На предварительную обработку расходуется O(|needle|+|Σ|²) времени.

Алгоритм «турбо-Бойера — Мура»:

Турбо-алгоритм, разработанный группой учёных во главе с М. Крошмором, предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.

Помимо эвристики стоп-символа и эвристики совпавшего суффикса, применяется третья эвристика — эвристика турбосдвига.

Пусть первый раз совпал суффикс UV (и сработала эвристика суффиксов, обеспечив полное перекрытие этого суффикса), второй раз — более короткий V (возможно, V=∅).

! !

haystack: * * * * * * * * * * # [-U-] [V] * * * * * * * * # [V] * * * * * *

1. Совпало UV: * [-U-] [V] * * * * [-U-] [V]

2. Затем совпало V: * [-U-] [V] * * * * * * [-U-] [V]

Сдвиг по эвристике суффиксов: * [-U-] [V] * * * * * * [-U-] [V]

Турбосдвиг: * [-U-] [V] * * * * * * [-U-] [V]

По рисунку видно, что минимальный возможный сдвиг — |U|. В противном случае два символа, обозначенные восклицательными знаками, в haystack разные, а в needle одинаковые. В этом и заключается эвристика турбосдвига.

Алгоритм выполняет свою работу за 2·|haystack| сравнений до первого совпадения в худшем случае.

Алгоритм Бойера-Мура на «хороших» данных очень быстр, а вероятность появления «плохих» данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск (haystack). Разве что на коротких текстах выигрыш не оправдает предварительных вычислений.

На x86 существует красивая ассемблерная реализация АБМ, основанная на командах std; rep cmpsb. После неудачного сравнения в регистре ecx остаётся индекс несовпавшего символа; указатели esi и edi указывают на соответствующие символы строк needle и haystack.

Сравнение не является «чёрным ящиком», поэтому при реализации наиболее быстрого поиска приходится либо рассчитывать на удачную работу оптимизатора, либо вручную оптимизировать поиск на ассемблерном уровне.

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

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

На искусственно подобранных «неудачных» текстах (например, needle=«колоколоколоколоколокол») скорость алгоритма Бойера-Мура серьёзно снижается. Существуют попытки совместить присущую алгоритму Кнута-Морриса-Пратта эффективность в «плохих» случаях и скорость Бойера-Мура в «хороших» — например, турбо-алгоритм, обратный алгоритм Колусси и другие.

Лит.: Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. — М.: МЦНМО, 2000. ISBN 5-900916-37-5. — с. 801. = T. Cormen, E. Leiserson, R. Rivest. Introduction to Algorithms. The MIT Press, 1990.

Loading

Календарь

«  Март 2024  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
25262728293031

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24