Алгоритм Shift-Or

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

Алгоритм

Пусть [math]p[/math] – шаблон длины [math]n[/math], [math]t[/math] – текст длины [math]m[/math].

Нам потребуется двоичный массив [math]M[/math] размером [math]n * (m + 1)[/math], в котором индекс [math]i[/math] пробегает значения от [math]1[/math] до [math]n[/math], а индекс [math]j[/math] – от [math]0[/math] до [math]m[/math]. [math]M[i][j] =[/math] { [math]1[/math], если первые [math]i[/math] символов [math]p[/math] точно совпадают с [math]i[/math] символами [math]t[/math], кончаясь на позиции [math]j[/math]; [math]0[/math] — иначе }

То есть [math]M[i][j] = 1[/math] тогда и только тогда, когда [math]p[1..i] = t[j – i + 1..j][/math]. Например, пусть [math]t = california[/math], [math]p = for[/math]. Тогда [math]M[1][5] = M[2][6] = M[3][7] = 1[/math], остальные [math]M[i][j] = 0[/math]. Получаем, что элементы, равные [math]1[/math], в строчке [math]i[/math] показывают все места в [math]t[/math], где заканчиватся копии [math]p[1..i][/math], а столбец [math]j[/math] показывает все префиксы [math]p[/math], которые заканчиваются в позиции [math]j[/math] строки [math]t[/math]. [math]M[n][j] = 1[/math] тогда, когда вхождение [math]p[/math] заканчивается в позиции [math]j[/math] строки [math]t[/math]. То есть вычисление последней строки [math]M[/math] решает задачу точного совпадения.

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

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

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

Псевдокод

   algorithm bitap_search(text : string, pattern : string) returns string
       m := length(pattern)
       if m == 0
           return text
       /* Initialize the bit array R. */
       R := new array[m+1] of bit, initially all 0
       R[0] = 1
       for i = 0; i < length(text); i += 1:
           /* Update the bit array. */
           for k = m; k >= 1; k -= 1:
               R[k] = R[k-1] & (text[i] == pattern[k-1])
           if R[m]:
               return (text+i - m) + 1
       return nil

Корректность

Докажем, что метод Shift-Or правильно вычисляет элементы массива M. Заметим, что для любого I > 1элемент M(i, j) = 1 т и тт, когда p[1..i – 1] совпадает с t[j – i + 1..j], а символ 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(nm), на препроцессинг — построение массива U требуется O(сигма*n) операций и памяти. Если же n не превышает длину машинного слова, то сложность получается O(m) и O(n + сигма) соответсвенно.