Алгоритм Shift-And
В 1990ые годы Рикардо Беза-Йетс (англ. Ricardo Baeza-Yates) и Гастон Гоннет (англ. Gaston Gonnet) изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом . Также алгоритм известен как алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием , которая будет рассмотрена ниже.
Алгоритм
Пусть — шаблон длины , — текст длины .
Нам потребуется двоичный массив размером , в котором индекс пробегает значения от до , а индекс — от до .
, если первые символов точно совпадают с символами , кончаясь на позиции ; иначе .
Например, пусть , . Тогда , остальные .
Получаем, что элементы, равные , в строчке показывают все места в , где заканчиватся копии , а столбец показывает все префиксы , которые заканчиваются в позиции строки .
тогда, когда вхождение заканчивается в позиции строки . То есть вычисление последней строки решает задачу точного совпадения.
Построение массива M
Создадим для каждого символа алфавита двоичный вектор длины . равно в тех позициях , где стоит символ . Например, ,
| Определение: |
| Назовём вектором такой вектор, который получен сдвигом столбца вниз на одну позицию и записью в первой позиции. Старое значение в позиции теряется. |
То есть состоит из , к которой приписаны первые битов столбца . Например,
Из определения, нулевой столбец состоит из нулей. Элементы любого другого столбца получаются из столбца и вектора для символа . А именно, вектор для столбца получается операцией побитового логического умножения вектора и вектора .
Псевдокод
string shiftAndSearch(string text, string pattern):
n = pattern.length
m = text.length
if n == 0
return text
M = array[n] of bit // для поиска коротких слов достаточно одной переменной типа integer
fill(M, 0)
U = new array [][n] of bit // изначально все элементы равны
for i = 1..n // препроцессинг — вычисление вектора
U[pattern[i]][i] = 1
for j = 1..m
M = Bit-Shift(M) & U[text[j]]
if M[n]
return text[j - n + 1..j]
return null
Корректность
Докажем, что метод правильно вычисляет элементы массива . Заметим, что для любого элемент тогда и только тогда, когда совпадает с , а символ совпадает с . Первое условие выполнено, когда элемент массива , а второе — когда -ый бит вектора для символа равен . Таким образом, чтобы вычислить элемент , нужно взять результат побитовой операции элементов и . Это эквивалентно применению побитовой операции к вектору и сдвинутому на столбцу под номером массива . Для нам достаточно проверить, что , поэтому мы и записываем в единицу, что и делает операция . Получаем, что наш алгоритм корректно вычисляет все значения массива .
Эффективность
Сложность алгоритма составляет , на препроцессинг — построение массива — требуется операций и памяти. Если же не превышает длину машинного слова, то сложность получается и соответсвенно.
Алгоритм Shift-Or
Аналогичен алгоритму , но вместо массива используется массив , определяемый следующим образом:
Следующий столбец получается операцией побитового логического сложения вектора и вектора . Здесь , а — сдвиг вектора на одну позицию вниз с записью в первой позиции.
Очевидно, что алгоритм корректен, так как данная формула получается применением логического отрицания к аналогичной формуле для алгоритма , корректность которого была доказана выше.
См. также
Источники информации
- Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — стр 100.
- Wikipedia — Bitap algorithm
- Алгоритм Shift-Or
- Shift-Or algorithm
