Изменения

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

Нам потребуется двоичный массив <tex>M</tex> размером <tex>n \cdot times (m + 1)</tex>, в котором индекс <tex>i</tex> пробегает значения от <tex>1</tex> до <tex>n</tex>, а индекс <tex>j</tex> {{---}} от <tex>0</tex> до <tex>m</tex>.

1, & \mbox {if p[1..$\ldots$ i] = t[j - i + 1..$\ldots$ j]} \\

Получаем, что элементы, равные <tex>1</tex>, в строчке <tex>i</tex> показывают все места в <tex>t</tex>, где заканчиватся копии <tex>p[1..\ldots i]</tex>, а столбец <tex>j</tex> показывает все префиксы <tex>p</tex>, которые заканчиваются в позиции <tex>j</tex> строки <tex>t</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> {{Определение|definition =Назовём вектором <tex>Bit\texttt{-}Shift(M[j])</tex> такой вектор, который получен сдвигом столбца <tex>M[j]</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется.}} То есть <tex>Bit\texttt{-}Shift(M[j])</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>M[j]</tex>. Например,

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

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

===Псевдокод===

'''string''' bitap_searchshiftAndSearch('''string''' text, '''string''' pattern):

M = new array [n] of bit <font color=green> // для поиска коротких слов достаточно одной переменной типа '''integer''' </font>

U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all <font color=green> // изначально все элементы равны <tex> 0</tex> </font> '''for''' i = 1..n <font color=green> // препроцессинг {{- --}} вычисление вектора <tex> U</tex> </font>

M = Bit-Shift(M) '''&''' U[ttext[j]]

Докажем, что метод <tex>Shift\texttt{-}And</tex> правильно вычисляет элементы массива <tex>M</tex>. Заметим, что для любого <tex>i > 1</tex> элемент <tex>M[i][j] = 1</tex> тогда и только тогда, когда <tex>p[1..\ldots i - 1]</tex> совпадает с <tex>t[j - i + 1..\ldots j-1]</tex>, а символ <tex>p[i]</tex> совпадает с <tex>t[j]</tex>. Первое условие выполнено, когда элемент массива <tex>M[i - 1][j - 1] = 1</tex>, а второе — когда <tex>i</tex>-ый бит вектора <tex>U</tex> для символа <tex>t[j]</tex> равен <tex>1</tex>. После сдвига столбца Таким образом, чтобы вычислить элемент <tex>M[i][j - 1] </tex>, нужно взять результат побитовой операции <tex> and </tex> алгоритм логически умножает элемент элементов <tex>M[i - 1][j - 1]</tex> столбца и <tex>U[t[j]][i]</tex>. Это эквивалентно применению побитовой операции <tex> and </tex> к вектору <tex> U[t[j]] </tex> и сдвинутому на <tex> 1 </tex> столбцу под номером <tex>j - 1</tex> на элемент массива <tex> M </tex>. Для <tex>i= 1 </tex> вектора нам достаточно проверить, что <tex>U([t[j])][1] = 1 </tex>. Следовательно, все элементы поэтому мы и записываем в <tex>M[1][j] </tex> вычисляются правильно единицу, что и делает операция <tex> Bit\texttt{-}Shift </tex>. Получаем, что наш алгоритм находит корректно вычисляет все вхождения образца в текстзначения массива <tex> M </tex>.

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

Аналогичен алгоритму <tex>Shift\texttt{-}And</tex>, но вместо массива <tex>M</tex> используется массив <tex>R</tex>, определяемый следующим образом:

0, & \mbox {if p[1..$\ldots$ i] = t[j - i + 1..$\ldots$ j]} \\

Следующий столбец <tex>R[j]</tex> получается операцией побитового логического сложения <tex>or</tex> вектора <tex>Bit\texttt{-}Shift'(R[j - 1])</tex> и вектора <tex>W([t[j])]</tex>. Здесь <tex>W([t[j]) ] = not \ U([t[j])]</tex>, а <tex>Bit\texttt{-}Shift'(R[j - 1])</tex> {{--- }} сдвиг вектора <tex>R[j - 1]</tex> на одну позицию вниз с записью <tex>0</tex> в первой позиции. <tex>R[j] = Bit\texttt{-}Shift'(R[j - 1]) \ or \ W[t[j]]</tex> Очевидно, что алгоритм <tex>Shift\texttt{-}Or</tex> корректен, так как данная формула получается применением логического отрицания к аналогичной формуле для алгоритма <tex>Shift\texttt{-}And</tex>, корректность которого была доказана выше. ==См. также==* [[Z-функция]] * [[Алгоритм Кнута-Морриса-Пратта]]

<tex>R[j] = Bit=Источники информации==*''Дэн Гасфилд'' — '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология''' — СПб.: Невский Диалект; БХВ-Shift(RПетербург, 2003. — стр 100.*[[j wikipedia:Bitap algorithm | Wikipedia {{--- 1}} Bitap algorithm]]) \ or \ W(t*[jhttp://algolist.manual.ru/search/esearch/shift_or.php Алгоритм Shift-Or])<*[http:/tex>/www-igm.univ-mlv.fr/~lecroq/string/node6.html Shift-Or algorithm]