Алгоритм Shift-And — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм Shift-Or)
м (Исправление ошибок с отображением \ldots, замена \cdot на \times при указании размера массива)
(не показано 13 промежуточных версий 4 участников)
Строка 1: Строка 1:
В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием <tex>Shift-Or</tex>, которая будет рассмотрена ниже.
+
В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift\texttt{-}And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием <tex>Shift\texttt{-}Or</tex>, которая будет рассмотрена ниже.
  
 
==Алгоритм==
 
==Алгоритм==
Строка 5: Строка 5:
 
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.
 
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.
  
Нам потребуется двоичный массив <tex>M</tex> размером <tex>n \cdot (m + 1)</tex>, в котором индекс <tex>i</tex> пробегает значения от <tex>1</tex> до <tex>n</tex>, а индекс <tex>j</tex> {{---}} от <tex>0</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] = 1</tex>, если первые <tex>i</tex> символов <tex>p</tex> точно совпадают с <tex>i</tex> символами <tex>t</tex>, кончаясь на позиции <tex>j</tex>; иначе <tex>M[i][j] = 0</tex>.
Строка 12: Строка 12:
 
\left\{
 
\left\{
 
\begin{array}{ll}
 
\begin{array}{ll}
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\
+
1, & \mbox {if p[1 $\ldots$ i] = t[j - i + 1 $\ldots$ j]} \\
 
0, & \mbox {otherwise}
 
0, & \mbox {otherwise}
 
\end{array}
 
\end{array}
Строка 20: Строка 20:
 
Например, пусть <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>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>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[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>.  
 
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.
 
То есть вычисление последней строки <tex>M</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>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>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>(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>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 (1, 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-Shift(M[j - 1])</tex> и вектора <tex>U(t[j])</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-Shift(M[j - 1]) \ and \ U(t[j])</tex>
+
<tex>M[j] = Bit\texttt{-}Shift(M[j - 1]) \ and \ U[t[j]]</tex>
  
==Псевдокод==
+
===Псевдокод===
  
     '''string''' bitap_search('''string''' text, '''string''' pattern)
+
     '''string''' shiftAndSearch('''string''' text, '''string''' pattern):
 
         n = pattern.length
 
         n = pattern.length
 
         m = text.length
 
         m = text.length
 
         '''if''' n == 0
 
         '''if''' n == 0
 
             '''return''' text
 
             '''return''' text
         M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer
+
         M = array[n] of bit <font color=green>          // для поиска коротких слов достаточно одной переменной типа '''integer''' </font>
 
         fill(M, 0)
 
         fill(M, 0)
         U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0
+
         U = new array [<tex>|\Sigma|</tex>][n] of bit <font color=green> // изначально все элементы равны <tex> 0 </tex> </font>
         '''for''' i = 1..n // препроцессинг - вычисление вектора U
+
         '''for''' i = 1..n <font color=green>                // препроцессинг {{---}} вычисление вектора <tex> U </tex> </font>
 
             U[pattern[i]][i] = 1
 
             U[pattern[i]][i] = 1
 
         '''for''' j = 1..m
 
         '''for''' j = 1..m
             M = Bit-Shift(M) '''&''' U[t[j]]
+
             M = Bit-Shift(M) '''&''' U[text[j]]
 
             '''if''' M[n]
 
             '''if''' M[n]
 
                 '''return''' text[j - n + 1..j]
 
                 '''return''' text[j - n + 1..j]
Строка 55: Строка 61:
  
 
==Корректность==
 
==Корректность==
Докажем, что метод <tex>Shift-And</tex> правильно вычисляет элементы массива <tex>M</tex>. Заметим, что для любого <tex>i > 1</tex> элемент <tex>M[i][j] = 1</tex> тогда и только тогда, когда <tex>p[1..i - 1]</tex> совпадает с <tex>t[j - i + 1..j]</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>j - 1</tex> алгоритм логически умножает элемент <tex>M[i - 1][j - 1]</tex> столбца <tex>j - 1</tex> на элемент <tex>i</tex> вектора <tex>U(t[j])</tex>. Следовательно, все элементы <tex>M</tex> вычисляются правильно и алгоритм находит все вхождения образца в текст.
+
Докажем, что метод <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> соответсвенно.
+
Сложность алгоритма составляет <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==
 
==Алгоритм Shift-Or==
Аналогичен алгоритму <tex>Shift-And</tex>, но вместо массива <tex>M</tex> используется массив <tex>R</tex>, определяемый следующим образом:
+
Аналогичен алгоритму <tex>Shift\texttt{-}And</tex>, но вместо массива <tex>M</tex> используется массив <tex>R</tex>, определяемый следующим образом:
  
 
<tex> R[i][j] =
 
<tex> R[i][j] =
 
\left\{
 
\left\{
 
\begin{array}{ll}
 
\begin{array}{ll}
0, & \mbox {if p[1..i] = t[j - i + 1..j]} \\
+
0, & \mbox {if p[1 $\ldots$ i] = t[j - i + 1 $\ldots$ j]} \\
 
1, & \mbox {otherwise}
 
1, & \mbox {otherwise}
 
\end{array}
 
\end{array}
Строка 72: Строка 78:
 
</tex>
 
</tex>
  
Следующий столбец <tex>R[j]</tex> получается операцией побитового логического сложения <tex>or</tex> вектора <tex>Bit-Shift'(R[j - 1])</tex> и вектора <tex>W(t[j])</tex>. Здесь <tex>W(t[j]) = not \ U(t[j])</tex>, а <tex>Bit-Shift'(R[j - 1])</tex> - сдвиг вектора <tex>R[j - 1]</tex> на одну позицию вниз с записью <tex>0</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-функция]]
 +
* [[Алгоритм Кнута-Морриса-Пратта]]
  
<tex>R[j] = Bit-Shift(R[j - 1]) \ or \ W(t[j])</tex>
+
==Источники информации==
 +
*''Дэн Гасфилд'' — '''Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология''' — СПб.: Невский Диалект; БХВ-Петербург, 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]
  
Очевидно, что алгоритм <tex>Shift-Or</tex> корректен, так как данная формула получается применением логического отрицания к аналогичной формуле для алгоритма <tex>Shift-And</tex>, корректность которого была доказана выше.
+
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Поиск подстроки в строке]]
 +
[[Категория: Точный поиск]]

Версия 17:17, 6 июня 2019

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

Алгоритм

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

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

[math] 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. [/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 \ldots 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] решает задачу точного совпадения.

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

Создадим для каждого символа алфавита [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\texttt{-}Shift(M[j])[/math] такой вектор, который получен сдвигом столбца [math]M[j][/math] вниз на одну позицию и записью [math]1[/math] в первой позиции. Старое значение в позиции [math]n[/math] теряется.


То есть [math]Bit\texttt{-}Shift(M[j])[/math] состоит из [math]1[/math], к которой приписаны первые [math]n - 1[/math] битов столбца [math]M[j][/math]. Например,

[math](0, 0, 0, 1, 0, 1, 1, 0, 1) \overset{Bit\texttt{-}Shift}{\longmapsto} (1, 0, 0, 0, 1, 0, 1, 1, 0)[/math]

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

Псевдокод

   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 [[math]|\Sigma|[/math]][n] of bit  // изначально все элементы равны [math] 0 [/math] 
       for i = 1..n                  // препроцессинг — вычисление вектора [math] U [/math] 
           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

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

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

Эффективность

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

Алгоритм Shift-Or

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

[math] 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. [/math]

Следующий столбец [math]R[j][/math] получается операцией побитового логического сложения [math]or[/math] вектора [math]Bit\texttt{-}Shift'(R[j - 1])[/math] и вектора [math]W[t[j]][/math]. Здесь [math]W[t[j]] = not \ U[t[j]][/math], а [math]Bit\texttt{-}Shift'(R[j - 1])[/math] — сдвиг вектора [math]R[j - 1][/math] на одну позицию вниз с записью [math]0[/math] в первой позиции.

[math]R[j] = Bit\texttt{-}Shift'(R[j - 1]) \ or \ W[t[j]][/math]

Очевидно, что алгоритм [math]Shift\texttt{-}Or[/math] корректен, так как данная формула получается применением логического отрицания к аналогичной формуле для алгоритма [math]Shift\texttt{-}And[/math], корректность которого была доказана выше.

См. также

Источники информации