Файл:Axo.jpg

2019-06-06T17:42:02Z

Maxina29: Maxina29 загрузил новую версию Файл:Axo.jpg

Файл:Axo.jpg

2019-06-06T16:45:09Z

Maxina29: Maxina29 загрузил новую версию Файл:Axo.jpg

Файл:Бор.jpg

2019-06-06T16:28:09Z

Maxina29: Maxina29 загрузил новую версию Файл:Бор.jpg

Файл:Бор.jpg

2019-06-06T16:25:43Z

Maxina29: Maxina29 загрузил новую версию Файл:Бор.jpg

Алгоритм Shift-And

2019-06-06T14:17:07Z

Maxina29: Исправление ошибок с отображением \ldots, замена \cdot на \times при указании размера массива

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

==Алгоритм==

Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.

Нам потребуется двоичный массив <tex>M</tex> размером <tex>n \times (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] = 1</tex>, если первые <tex>i</tex> символов <tex>p</tex> точно совпадают с <tex>i</tex> символами <tex>t</tex>, кончаясь на позиции <tex>j</tex>; иначе <tex>M[i][j] = 0</tex>.

<tex> M[i][j] =
\left\{
\begin{array}{ll}
1, & \mbox {if p[1 $\ldots$ i] = t[j - i + 1 $\ldots$ j]} \\
0, & \mbox {otherwise}
\end{array}
\right.
</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 \ldots 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> решает задачу точного совпадения.

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

Создадим для каждого символа алфавита <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>(0, 0, 0, 1, 0, 1, 1, 0, 1) \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''' shiftAndSearch('''string''' text, '''string''' pattern):
n = pattern.length
m = text.length
'''if''' n == 0
'''return''' text
M = array[n] of bit // для поиска коротких слов достаточно одной переменной типа '''integer''' 
fill(M, 0)
U = new array [<tex>|\Sigma|</tex>][n] of bit // изначально все элементы равны <tex> 0 </tex> 
'''for''' i = 1..n // препроцессинг {{---}} вычисление вектора <tex> U </tex> 
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

==Корректность==
Докажем, что метод <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] </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> соответсвенно.

==Алгоритм Shift-Or==
Аналогичен алгоритму <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]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Поиск подстроки в строке]]
[[Категория: Точный поиск]]

Викиконспекты - Вклад участника [ru]

Файл:Axo.jpg

Файл:Axo.jpg

Файл:Бор.jpg

Файл:Бор.jpg

Алгоритм Shift-And