Главная » Java, Структуры данных и алгоритмы » Алгоритмы шаблонного сопоставления Алгоритм Бойера-Мура

0

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

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

Зеркало: при поиске возможного размещения Р в Т сравнения начинаются с конца Р и перемещаются к началу Р.

Пропуск символов: в процессе поиска возможного размещения Р в Т несовпадение текстового символа T[i\ — с с соответствующим шаблонным символом P[j] решается следующим образом. Если с отсутствует в Р,

то Р полностью сдвигается (пропускает) за T[i] (так как не сравнился ни один из символов в Р). В противном случае Р сдвигается до тех пор, пока с из Р не совпадет с T[i],

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

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

• если с находится в Р, то last(c) является индексом последнего (самого правого) появления с в Р. В противном случае last(c) = -1.

Если символы используются в массиве в качестве индексов, то функция last может быть реализована в виде поисковой таблицы. Метод создания такой таблицы за 0(m+ |Z|) времени оставлен для упражнения М-11.6. Функция last предоставляет необходимые сведения для осуществления эвристики пропуска символов.

Во фрагменте кода 11.2 показан алгоритм Бойера-Мура.

Алгоритм BMMatch(71,/>):

Input: строка Т (текст) из п символов и шаблон Р из m символов.

Output: индекс начала первой подстроки Т, совпадающей с Р, или сообщение о том, что Т не содержит подстроку Р.

вычислить функцию last / m – 1 j m – 1

repeat

if P[i] = T[i] then if j = 0 then

return / { возможно совпадение! } else

/<-/- 1 У f- J ~ 1

else

/<-/’ + m – min(/,1 + last(7"[/])) { переход } у <— m — 1 until / > n – 1

return "There is no substring of T matching P"

Фрагмент кода 11.2. Шаблонный алгоритм Бойера-Мура

Стадия пропуска символов показана на рис. 11.2. Рис. 11.3 иллюстрирует выполнение шаблонного алгоритма Бойера-Мура применительно к исходной строке примера 11.3.

Рис. 11.2. Стадия пропуска символов в БМ-алгоритме (см. фрагмент кода 11.2), в которой используется метка / = last (Гр]). Здесь различаются два случая: (а) 1 + / < у, где шаблон перемещается на у – / клеток; (Ь) у < 1 + /, где шаблон перемещается на одну клетку

Верное выполнение шаблонного алгоритма Бойера-Мура проистекает из-за невозможности пропуска любого возможного совпадения, когда метод выполняет перемещение. И это связано с тем, что last(c) является последним встреченным с в шаблоне Р.

В наихудшем случае время выполнения БМ-алгоритма составляет 0(пт + |Е|). При этом вычисление функции last занимает 0(т + |z|), а непосредственный поиск шаблона — 0{пт) времени в худшем случае, то есть аналогично силовому алгоритму. В качестве примера такой пары «текст-шаблон» в худшем случае можно указать

Рис. 11.4. Схема выполнения БМ-алгоритма в тексте на английском языке, обеспечивающая значительную скорость. Обратите внимание, что не все символы текста проверяются на соответствие

//** Упрощенная версия БМ-алгоритма, использующего только эвристики * зеркала и пропуска символов.

*                     @ return индекс начала самой левой подстроки текста,

*            совпадающей с шаблоном, или -1, если совпадений не обнаружено, public static int BMmatch (String text, String pattern) {

int[ ] last = buildLastFunction(pattern);

int n = text.length();

int m = pattern.lengthQ;

int i = m -1;

if (i > n – 1)

return -1; // не совпадает, если шаблон длиннее текста int j – m – 1; do {

if (pattern.charAt(j) == text.charAt(i)) if (j == 0)

return i; // совпадает else {           // зеркальная эвристика: следовать справа налево

i – -; j – -;

}

else {                                       // эвристика пропуска символов

i = i + m – Math.min(j, 1 + last[text.charAt(i)]); j = m – 1;

}

} while (i <= n – 1); return -1; // не совпадает

}

/** Создание вспомогательной функции, используемой в БМ-алгоритме. *@ return массив размером 128, хранящий индекс последнего совпадения

*            каждого из символов ASCII шаблона. */ public static int[] buildLastFunction (String pattern) {

int[ ] last = new int[128]; //при условии использования символов ASCII for (int i = 0; i < 128; r++) {

Iast[i] = -1; // инициализирует массив

for (int j = 0; i < pattern.Iength(); i++) {

last[pattern.charAt(i)] = i; // приводит в соответствие с числами

// таблицы ASCII

} "

return jast;

}

Фрагмент кода 11.3. Реализация шаблонного БМ-алгоритма на Java. Алгоритм выражен двумя статическими методами: ВММаК^’выполняет сравнение и вызывает метод buildLastFunction для создания функции last с использованием массива индексов символов ASCII. Метод BMMatch отмечает отсутствие совпадений, возвращая значение —1,

Здесь приведен упрощенный вариант алгоритма Бойера-Мура. Оригинальный же вариант алгоритма обеспечивает время выполнения 0(п + + т + |Е|) с помощью альтернативной эвристики перемещения по частично совпадающим текстовым строкам, которая перемещает шаблон на большие отрезки, чем эвристика пропуска символов. В основу такой эвристики перемещения заложен принцип шаблонного алгоритма Кнута-Морриса-Пратта, который и рассмотрим.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии