В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-Or</tex>, хотя, исходя из самого алгоритма, естественней назвать его <tex>Shift-And</tex>. Также алгоритм известен как bitap алгоритм и алгоритм Беза-Йетса-Гоннета. ==Алгоритм== Пусть <tex>p</tex> – шаблон длины <tex>n</tex>, <tex>t</tex> – текст длины <tex>m</tex>. Нам потребуется двоичный массив <tex>M</tex> размером <tex>n * (m + 1)</tex>, в котором индекс <tex>i</tex> пробегает значения от <tex>1</tex> до <tex>n</tex>, а индекс <tex>j</tex> – от <tex>0</tex> до <tex>m</tex>.<tex>M#перенаправление [i][j] =</tex> { <tex>1</tex>, если первые <tex>i</tex> символов <tex>p</tex> точно совпадают с <tex>i</tex> символами <tex>t</tex>, кончаясь на позиции <tex>j</tex>; <tex>0</tex> — иначе } То есть <tex>M[i][j] = 1</tex> тогда и только тогда, когда <tex>p[1..i] = t[j – i + 1..j]</tex>.Например, пусть <tex>t = california</tex>, <tex>p = for</tex>. Тогда <tex>M[1][5] = M[2][6] = M[3][7] = 1</tex>, остальные <tex>M[i][j] = 0</tex>. Получаем, что элементы, равные <tex>1</tex>, в строчке <tex>i</tex> показывают все места в <tex>t</tex>, где заканчиватся копии <tex>p[1..i]</tex>, а столбец <tex>j</tex> показывает все префиксы <tex>p</tex>, которые заканчиваются в позиции <tex>j</tex> строки <tex>t</tex>. <tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения. Построение массива <tex>M</tex>.Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex> Определим <tex>Bit-Алгоритм Shift(j)</tex> как вектор, полученный сдвигом вектора для столбца <tex>j</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. То есть <tex>Bit-Shift(j)</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n – 1</tex> битов столбца <tex>j</tex>.<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) → (1, 0, 0, 1, 0, 1, 1, 0)</tex> Из определения, нулевой столбец <tex>M</tex> состоит из нулей. Элементы любого другого столбца <tex>j > 0</tex> получаются из столбца <tex>j – 1</tex> и вектора <tex>U</tex> для символа <tex>t[j]</tex>. А именно, вектор для столбца <tex>j</tex> получается операцией побитового логического умножения <tex>and</tex> вектора <tex>Bit-Shift(j – 1)</tex> и вектора <tex>U(t[j])</tex>. <tex>M[j] = Bit-Shift(j – 1) and U(t[j])</tex>Например, … ==Псевдокод== 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[iAnd] совпадает с 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 + сигма) соответсвенно.
