Изменения

В 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>.  

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

Создадим для каждого символа алфавита {{Определение|definition =Назовём вектором <tex>xBit\texttt{-}Shift(M[j])</tex> двоичный такой вектор , который получен сдвигом столбца <tex>U(x)M[j]</tex> длины вниз на одну позицию и записью <tex>n1</tex>в первой позиции. Старое значение в позиции <tex>U(x)n</tex> равно теряется.}} То есть <tex>1Bit\texttt{-}Shift(M[j])</tex> в тех позициях состоит из <tex>p1</tex>, где стоит символ к которой приписаны первые <tex>xn - 1</tex>. Например, битов столбца <tex>p = abacdeabM[j]</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) \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{-Or}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>, определяемый следующим образом: <tex> R[i][j] =\left\{ \begin{array}{ll} 0, & \mbox {if p[1 $\ldots$ i] = t[j - i + 1 $\ldots$ j]} \\ 1, & \mbox {otherwise} \end{array}\right.</tex> Следующий столбец <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-функция]] * [[Алгоритм Кнута-Морриса-Пратта]] ==Источники информации==*''Дэн Гасфилд'' — '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология''' — СПб.: Невский Диалект; БХВ-Петербург, 2003. — стр 100.*[[wikipedia:Bitap algorithm | Wikipedia {{---}} Bitap algorithm]]*[http://algolist.manual.ru/search/esearch/shift_or.php Алгоритм Shift-Or]*[http://www-igm.univ-mlv.fr/~lecroq/string/node6.html Shift-Or algorithm] [[Категория: Алгоритмы и структуры данных]][[Категория: Поиск подстроки в строке]][[Категория: Точный поиск]]