Алгоритм Shift-And

В 1990ые годы Рикардо Беза-Йетс (англ. Ricardo Baeza-Yates) и Гастон Гоннет (англ. Gaston Gonnet) изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом $Shift-And$. Также алгоритм известен как $bitap$ алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием $Shift\texttt{-}Or$, которая будет рассмотрена ниже.

Алгоритм

Пусть $p$ — шаблон длины $n$, $t$ — текст длины $m$.

Нам потребуется двоичный массив $M$ размером $n \cdot (m + 1)$, в котором индекс $i$ пробегает значения от $1$ до $n$, а индекс $j$ — от $0$ до $m$.

$M[i][j] = 1$, если первые $i$ символов $p$ точно совпадают с $i$ символами $t$, кончаясь на позиции $j$; иначе $M[i][j] = 0$.

$M[i][j] = \left\{ \begin{array}{ll} 1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\ 0, & \mbox {otherwise} \end{array} \right.$

Например, пусть $t = california$, $p = for$. Тогда $M[1][5] = M[2][6] = M[3][7] = 1$, остальные $M[i][j] = 0$.

Получаем, что элементы, равные $1$, в строчке $i$ показывают все места в $t$, где заканчиватся копии $p[1..i]$, а столбец $j$ показывает все префиксы $p$, которые заканчиваются в позиции $j$ строки $t$. $M[n][j] = 1$ тогда, когда вхождение $p$ заканчивается в позиции $j$ строки $t$. То есть вычисление последней строки $M$ решает задачу точного совпадения.

Построение массива $M$.

Создадим для каждого символа алфавита $x$ двоичный вектор $U(x)$ длины $n$. $U(x)$ равно $1$ в тех позициях $p$, где стоит символ $x$. Например, $p = abacdeab$, $U(a) = 10100010$

Определим $Bit-Shift(M[j])$ как вектор, полученный сдвигом вектора для столбца $M[j]$ вниз на одну позицию и записью $1$ в первой позиции. Старое значение в позиции $n$ теряется. То есть $Bit-Shift(M[j])$ состоит из $1$, к которой приписаны первые $n - 1$ битов столбца $M[j]$. $(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 0, 1, 0, 1, 1, 0)$

Из определения, нулевой столбец $M$ состоит из нулей. Элементы любого другого столбца $M[j], j \gt 0$ получаются из столбца $M[j - 1]$ и вектора $U$ для символа $t[j]$. А именно, вектор для столбца $j$ получается операцией побитового логического умножения $and$ вектора $Bit-Shift(M[j - 1])$ и вектора $U(t[j])$. $M[j] = Bit-Shift(M[j - 1]) \ and \ U(t[j])$

Псевдокод

   string bitap_search(string text, string pattern)
       n = pattern.length
       m = text.length
       if n == 0
           return text
       M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer
       fill(M, 0)
       U = new array [$|\Sigma|$][n] of bit, initially all 0
       for i = 1..n // препроцессинг - вычисление вектора U
           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-And$ правильно вычисляет элементы массива $M$. Заметим, что для любого $i \gt 1$ элемент $M[i][j] = 1$ тогда и только тогда, когда $p[1..i - 1]$ совпадает с $t[j - i + 1 \dots j-1]$, а символ $p[i]$ совпадает с $t[j]$. Первое условие выполнено, когда элемент массива $M[i - 1][j - 1] = 1$, а второе — когда $i$-ый бит вектора $U$ для символа $t[j]$ равен $1$. После сдвига столбца $j - 1$ алгоритм логически умножает элемент $M[i - 1][j - 1]$ столбца $j - 1$ на элемент $i$ вектора $U(t[j])$. Следовательно, все элементы $M$ вычисляются правильно и алгоритм находит все вхождения образца в текст.

Эффективность

Сложность алгоритма составляет $O(n \cdot m)$, на препроцессинг — построение массива $U$ требуется $O(|\Sigma| \cdot n)$ операций и памяти. Если же $n$ не превышает длину машинного слова, то сложность получается $O(m)$ и $O(n + |\Sigma|)$ соответсвенно.

Алгоритм Shift-Or

Аналогичен алгоритму $Shift-And$, но вместо массива $M$ используется массив $R$, определяемый следующим образом:

$R[i][j] = \left\{ \begin{array}{ll} 0, & \mbox {if p[1..i] = t[j - i + 1..j]} \\ 1, & \mbox {otherwise} \end{array} \right.$

Следующий столбец $R[j]$ получается операцией побитового логического сложения $or$ вектора $Bit-Shift'(R[j - 1])$ и вектора $W(t[j])$. Здесь $W(t[j]) = not \ U(t[j])$, а $Bit-Shift'(R[j - 1])$ - сдвиг вектора $R[j - 1]$ на одну позицию вниз с записью $0$ в первой позиции.

$R[j] = Bit-Shift(R[j - 1]) \ or \ W(t[j])$

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