- Алгоритм Бойера — Мура — Хорспула
-
Алгоритм Бойера — Мура — Хорспула
Алгоритм Бойера — Мура — Хорспула поиска строки — упрощённый вариант алгоритма Бойера — Мура. АБМХ работает лучше алгоритма Бойера — Мура на случайных текстах. К тому же, требующая многих предварительных вычислений эвристика совпавшего суффикса опускается.
Впрочем, оценка (в худшем случае на непериодических шаблонах) у АБМХ составляет |needle|·|haystack| (вместо 3|haystack| у Бойера-Мура).
Содержание
Описание алгоритма
Сначала строится таблица смещений для искомого шаблона. Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона.
Если последний символ шаблона и соответствующий ему при наложении символ строки не совпадают, то образец сдвигается относительно строки на величину, полученную из таблицы смещений. Причём символ берется из строки (а не из шаблона), соответствующий сдвиг находится в таблице. Производится сдвиг и снова начинается проверка с последнего символа.
Если же символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен. Если же какой-то (не последний) символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на один символ вправо, и снова проверка снова начинается с последнего символа.
Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки.
Построение таблицы
В таблице хранится величина сдвига для каждого символа в шаблоне. Величина сдвига определяется из тех соображений, что он должен быть максимально возможным, но таким, чтобы не пропустить вхождение искомого шаблона.
Таблица содержит список всех символов в шаблоне. В соответствие каждому символу ставится его порядковый номер, считая с конца строки. Если символ встречается несколько раз, то используется самое правое вхождение.
Пример
Для шаблона «abbad» таблица имеет следующий вид.
a b d 1 2 5 Примечания
Позиция последнего символа шаблона в алгоритме не рассматривается, то есть значение смещения для символа 'd' будет равно длине шаблона — 5.
В таблице соответствия символ — смещение, для всех символов, не вошедших в шаблон, величина смещения устанавливается равной длине шаблона — 5.
Пример работы алгоритма
Искомый шаблон — «abbad» (таблица для этого шаблона построена выше).
abeccacbadbabbad abbad
Накладываем образец на строку. Последний символ исходной строки «с» не содержится в образце. Сдвигаем образец вправо на 5 позиций в соответствии со значением смещения для «с»:
abeccacbadbabbad abbad
Три символа образца совпали, а четвертый — нет. Сдвигаем образец вправо на 1:
abeccacbadbabbad abbad
Последний символ строки b не совпадает с символом шаблона.Сдвигаем образец вправо на 2:
abeccacbadbabbad abbad
И снова последний символ строки b не совпадает с символом шаблона.Сдвигаем на 2 позиции:
abeccacbadbabbad abbad
Последний символ исходной строки «a» снова не совпадает с символом шаблона. В соответствии с таблицей смещений сдвигаем образец на 1 позицию и получаем искомое вхождение образца:abeccacbadbabbad abbad
Пример
Паскаль
Процедура получает ссылки на три переменные: haystack и needle строкового типа и result целого типа, причём первые две для процедуры являются константами и не могут быть изменены. В haystack должна содержаться строка, в которой будет осуществлён поиск, а needle должна содержать подстроку, которую надо найти. В результате выполнения процедуры переменная result будет содержать номер позиции, начиная с которого подстрока needle входит в строку haystack, или 0, если вхождения нет.
procedure boyer_moore(const haystack: string; const needle: string; var result: byte); var i, j, k : byte; needle_len : byte; haystack_len : byte; needle_table : array[char] of byte; begin needle_len := length(needle); haystack_len := length(haystack); if needle_len < haystack_len then begin for i := 0 to 255 do needle_table[chr(i)] := needle_len; for i := 1 to needle_len-1 do needle_table[needle[i]] := needle_len-i; i := needle_len; j := i; while (j > 0) and (i <= haystack_len) do begin j := needle_len; k := i; while (j > 0) and (haystack[k] = needle[j]) do begin dec(k); dec(j); end; i := i + needle_table[haystack[i]]; end; if k > haystack_len - needle_len then result := 0 else result := k + 1; end else result := 0; end;
Литература
- Никлаус Вирт Алгоритмы и структуры данных. — М.: Невский Диалект, 2006. С. 352. ISBN 5-7940-0065-1
Wikimedia Foundation. 2010.