http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=178.71.141.146&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T15:59:37ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-And&diff=38073Алгоритм Shift-And2014-06-08T17:48:15Z<p>178.71.141.146: /* Псевдокод */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием <tex>Shift-Or</tex>, которая будет рассмотрена ниже.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(M[j])</tex> как вектор, полученный сдвигом вектора для столбца <tex>M[j]</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(M[j])</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>M[j]</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) \ and \ U(t[j])</tex><br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = pattern.length<br />
m = text.length<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer<br />
fill(M, 0)<br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n // препроцессинг - вычисление вектора U<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M = Bit-Shift(M) '''&''' U[text[j]]<br />
'''if''' M[n]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <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> вычисляются правильно и алгоритм находит все вхождения образца в текст.<br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.<br />
<br />
==Алгоритм Shift-Or==<br />
Аналогичен алгоритму <tex>Shift-And</tex>, но вместо массива <tex>M</tex> используется массив <tex>R</tex>, определяемый следующим образом:<br />
<br />
<tex> R[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
0, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
1, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Следующий столбец <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> в первой позиции.<br />
<br />
<tex>R[j] = Bit-Shift(R[j - 1]) \ or \ W(t[j])</tex><br />
<br />
Очевидно, что алгоритм <tex>Shift-Or</tex> корректен, так как данная формула получается применением логического отрицания к аналогичной формуле для алгоритма <tex>Shift-And</tex>, корректность которого была доказана выше.</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-And&diff=38072Алгоритм Shift-And2014-06-08T17:47:53Z<p>178.71.141.146: /* Алгоритм */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием <tex>Shift-Or</tex>, которая будет рассмотрена ниже.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(M[j])</tex> как вектор, полученный сдвигом вектора для столбца <tex>M[j]</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(M[j])</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>M[j]</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) \ and \ U(t[j])</tex><br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = pattern.length<br />
m = text.length<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer<br />
fill(M, 0)<br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n // препроцессинг - вычисление вектора U<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M = Bit-Shift(M) '''&''' U[t[j]]<br />
'''if''' M[n]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <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> вычисляются правильно и алгоритм находит все вхождения образца в текст.<br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.<br />
<br />
==Алгоритм Shift-Or==<br />
Аналогичен алгоритму <tex>Shift-And</tex>, но вместо массива <tex>M</tex> используется массив <tex>R</tex>, определяемый следующим образом:<br />
<br />
<tex> R[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
0, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
1, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Следующий столбец <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> в первой позиции.<br />
<br />
<tex>R[j] = Bit-Shift(R[j - 1]) \ or \ W(t[j])</tex><br />
<br />
Очевидно, что алгоритм <tex>Shift-Or</tex> корректен, так как данная формула получается применением логического отрицания к аналогичной формуле для алгоритма <tex>Shift-And</tex>, корректность которого была доказана выше.</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-And&diff=38071Алгоритм Shift-And2014-06-08T17:39:44Z<p>178.71.141.146: /* Алгоритм Shift-Or */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием <tex>Shift-Or</tex>, которая будет рассмотрена ниже.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(M[j])</tex> как вектор, полученный сдвигом вектора для столбца <tex>M[j]</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(M[j])</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>M[j]</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) \ and \ U(t[j])</tex><br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = pattern.length<br />
m = text.length<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer<br />
fill(M, 0)<br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n // препроцессинг - вычисление вектора U<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M = Bit-Shift(M) '''&''' U[t[j]]<br />
'''if''' M[n]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <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> вычисляются правильно и алгоритм находит все вхождения образца в текст.<br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.<br />
<br />
==Алгоритм Shift-Or==<br />
Аналогичен алгоритму <tex>Shift-And</tex>, но вместо массива <tex>M</tex> используется массив <tex>R</tex>, определяемый следующим образом:<br />
<br />
<tex> R[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
0, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
1, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Следующий столбец <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> в первой позиции.<br />
<br />
<tex>R[j] = Bit-Shift(R[j - 1]) \ or \ W(t[j])</tex><br />
<br />
Очевидно, что алгоритм <tex>Shift-Or</tex> корректен, так как данная формула получается применением логического отрицания к аналогичной формуле для алгоритма <tex>Shift-And</tex>, корректность которого была доказана выше.</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-And&diff=38070Алгоритм Shift-And2014-06-08T17:30:00Z<p>178.71.141.146: /* Алгоритм Shift-Or */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием <tex>Shift-Or</tex>, которая будет рассмотрена ниже.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(M[j])</tex> как вектор, полученный сдвигом вектора для столбца <tex>M[j]</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(M[j])</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>M[j]</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) \ and \ U(t[j])</tex><br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = pattern.length<br />
m = text.length<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer<br />
fill(M, 0)<br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n // препроцессинг - вычисление вектора U<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M = Bit-Shift(M) '''&''' U[t[j]]<br />
'''if''' M[n]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <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> вычисляются правильно и алгоритм находит все вхождения образца в текст.<br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.<br />
<br />
==Алгоритм Shift-Or==<br />
Аналогичен алгоритму <tex>Shift-And</tex>, но вместо массива <tex>M</tex> используется массив <tex>R</tex>, определяемый следующим образом:<br />
<br />
<tex> R[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
0, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
1, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Следующий столбец <tex>R[j]</tex> получается операцией побитового логического сложения <tex>or</tex> вектора <tex>Bit-Shift(R[j - 1])</tex> и вектора <tex>U(t[j])</tex>. <br />
<tex>R[j] = Bit-Shift(R[j - 1]) \ or \ U(t[j])</tex></div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-And&diff=38069Алгоритм Shift-And2014-06-08T17:23:11Z<p>178.71.141.146: /* Алгоритм Shift-Or */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием <tex>Shift-Or</tex>, которая будет рассмотрена ниже.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(M[j])</tex> как вектор, полученный сдвигом вектора для столбца <tex>M[j]</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(M[j])</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>M[j]</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) \ and \ U(t[j])</tex><br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = pattern.length<br />
m = text.length<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer<br />
fill(M, 0)<br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n // препроцессинг - вычисление вектора U<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M = Bit-Shift(M) '''&''' U[t[j]]<br />
'''if''' M[n]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <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> вычисляются правильно и алгоритм находит все вхождения образца в текст.<br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.<br />
<br />
==Алгоритм Shift-Or==<br />
Аналогичен алгоритму <tex>Shift-And</tex>, но вместо массива <tex>M</tex> используется массив <tex>R</tex>, определяемый следующим образом:<br />
<br />
<tex> R[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
0, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
1, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Следующий столбец <tex>R[j]</tex> получается операцией побитового логического сложения <tex>or</tex> вектора <tex>Bit-Shift(R[j - 1])</tex> и вектора <tex>U(t[j])</tex>. <br />
<tex>R[j] = Bit-Shift(R[j - 1]) \ and \ U(t[j])</tex></div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-And&diff=38068Алгоритм Shift-And2014-06-08T17:21:05Z<p>178.71.141.146: /* Алгоритм */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием <tex>Shift-Or</tex>, которая будет рассмотрена ниже.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(M[j])</tex> как вектор, полученный сдвигом вектора для столбца <tex>M[j]</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(M[j])</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>M[j]</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) \ and \ U(t[j])</tex><br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = pattern.length<br />
m = text.length<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer<br />
fill(M, 0)<br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n // препроцессинг - вычисление вектора U<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M = Bit-Shift(M) '''&''' U[t[j]]<br />
'''if''' M[n]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <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> вычисляются правильно и алгоритм находит все вхождения образца в текст.<br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.<br />
<br />
==Алгоритм Shift-Or==<br />
...</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-And&diff=38067Алгоритм Shift-And2014-06-08T17:14:52Z<p>178.71.141.146: /* Алгоритм */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием <tex>Shift-Or</tex>, которая будет рассмотрена ниже.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(M[j])</tex> как вектор, полученный сдвигом вектора для столбца <tex>M[j]</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(M[j])</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>M[j]</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) \ and \ U(t[j])</tex><br />
Например, …<br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = pattern.length<br />
m = text.length<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer<br />
fill(M, 0)<br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n // препроцессинг - вычисление вектора U<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M = Bit-Shift(M) '''&''' U[t[j]]<br />
'''if''' M[n]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <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> вычисляются правильно и алгоритм находит все вхождения образца в текст.<br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.<br />
<br />
==Алгоритм Shift-Or==<br />
...</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-And&diff=38066Алгоритм Shift-And2014-06-08T17:09:32Z<p>178.71.141.146: /* Корректность */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием <tex>Shift-Or</tex>, которая будет рассмотрена ниже.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(j)</tex> как вектор, полученный сдвигом вектора для столбца <tex>j</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(j)</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>j</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) and U(t[j])</tex><br />
Например, …<br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = pattern.length<br />
m = text.length<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer<br />
fill(M, 0)<br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n // препроцессинг - вычисление вектора U<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M = Bit-Shift(M) '''&''' U[t[j]]<br />
'''if''' M[n]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <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> вычисляются правильно и алгоритм находит все вхождения образца в текст.<br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.<br />
<br />
==Алгоритм Shift-Or==<br />
...</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-And&diff=38065Алгоритм Shift-And2014-06-08T17:06:53Z<p>178.71.141.146: /* Корректность */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием <tex>Shift-Or</tex>, которая будет рассмотрена ниже.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(j)</tex> как вектор, полученный сдвигом вектора для столбца <tex>j</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(j)</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>j</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) and U(t[j])</tex><br />
Например, …<br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = pattern.length<br />
m = text.length<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer<br />
fill(M, 0)<br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n // препроцессинг - вычисление вектора U<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M = Bit-Shift(M) '''&''' U[t[j]]<br />
'''if''' M[n]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <tex>Shift-Or</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> вычисляются правильно и алгоритм находит все вхождения образца в текст.<br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.<br />
<br />
==Алгоритм Shift-Or==<br />
...</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-And&diff=38064Алгоритм Shift-And2014-06-08T17:06:30Z<p>178.71.141.146: /* Корректность */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием <tex>Shift-Or</tex>, которая будет рассмотрена ниже.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(j)</tex> как вектор, полученный сдвигом вектора для столбца <tex>j</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(j)</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>j</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) and U(t[j])</tex><br />
Например, …<br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = pattern.length<br />
m = text.length<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer<br />
fill(M, 0)<br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n // препроцессинг - вычисление вектора U<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M = Bit-Shift(M) '''&''' U[t[j]]<br />
'''if''' M[n]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <tex>Shift-Or</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> вычисляются правильно и алгоритм находит все вхождения образца в текст.<br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.<br />
<br />
==Алгоритм Shift-Or==<br />
...</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-Or&diff=38063Алгоритм Shift-Or2014-06-08T17:02:47Z<p>178.71.141.146: Перенаправление на Алгоритм Shift-And</p>
<hr />
<div>#перенаправление [[Алгоритм Shift-And]]</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-And&diff=38062Алгоритм Shift-And2014-06-08T17:00:25Z<p>178.71.141.146: Новая страница: «В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобре...»</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием <tex>Shift-Or</tex>, которая будет рассмотрена ниже.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(j)</tex> как вектор, полученный сдвигом вектора для столбца <tex>j</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(j)</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>j</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) and U(t[j])</tex><br />
Например, …<br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = pattern.length<br />
m = text.length<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer<br />
fill(M, 0)<br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n // препроцессинг - вычисление вектора U<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M = Bit-Shift(M) '''&''' U[t[j]]<br />
'''if''' M[n]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <tex>Shift-Or</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> вычисляются правильно и алгоритм находит все вхождения образца в текст. <br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.<br />
<br />
==Алгоритм Shift-Or==<br />
...</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-Or&diff=37985Алгоритм Shift-Or2014-06-07T19:25:59Z<p>178.71.141.146: /* Псевдокод */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-Or</tex>, хотя, исходя из самого алгоритма, естественней назвать его <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(j)</tex> как вектор, полученный сдвигом вектора для столбца <tex>j</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(j)</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>j</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) and U(t[j])</tex><br />
Например, …<br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = pattern.length<br />
m = text.length<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer<br />
fill(M, 0)<br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n // препроцессинг - вычисление вектора U<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M = Bit-Shift(M) '''&''' U[t[j]]<br />
'''if''' M[n]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <tex>Shift-Or</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> вычисляются правильно и алгоритм находит все вхождения образца в текст. <br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-Or&diff=37984Алгоритм Shift-Or2014-06-07T19:21:23Z<p>178.71.141.146: /* Псевдокод */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-Or</tex>, хотя, исходя из самого алгоритма, естественней назвать его <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(j)</tex> как вектор, полученный сдвигом вектора для столбца <tex>j</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(j)</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>j</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) and U(t[j])</tex><br />
Например, …<br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = pattern.length<br />
m = text.length<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer<br />
M = 0<br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n // препроцессинг - вычисление вектора U<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M = Bit-Shift(M) '''&''' U[t[j]]<br />
'''for''' j = 1..m<br />
'''if''' M[j]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <tex>Shift-Or</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> вычисляются правильно и алгоритм находит все вхождения образца в текст. <br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-Or&diff=37983Алгоритм Shift-Or2014-06-07T19:17:57Z<p>178.71.141.146: /* Псевдокод */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-Or</tex>, хотя, исходя из самого алгоритма, естественней назвать его <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(j)</tex> как вектор, полученный сдвигом вектора для столбца <tex>j</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(j)</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>j</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) and U(t[j])</tex><br />
Например, …<br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = pattern.length<br />
m = text.length<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer<br />
M = 0<br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M = Bit-Shift(M) '''&''' U[t[j]]<br />
'''for''' j = 1..m<br />
'''if''' M[j]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <tex>Shift-Or</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> вычисляются правильно и алгоритм находит все вхождения образца в текст. <br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-Or&diff=37982Алгоритм Shift-Or2014-06-07T19:17:13Z<p>178.71.141.146: /* Псевдокод */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-Or</tex>, хотя, исходя из самого алгоритма, естественней назвать его <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(j)</tex> как вектор, полученный сдвигом вектора для столбца <tex>j</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(j)</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>j</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) and U(t[j])</tex><br />
Например, …<br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = pattern.length<br />
m = text.length<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer<br />
M = 0<br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M = Bit-Shift(M) '''and''' U[t[j]]<br />
'''for''' j = 1..m<br />
'''if''' M[j]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <tex>Shift-Or</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> вычисляются правильно и алгоритм находит все вхождения образца в текст. <br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-Or&diff=37978Алгоритм Shift-Or2014-06-07T19:04:11Z<p>178.71.141.146: /* Псевдокод */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-Or</tex>, хотя, исходя из самого алгоритма, естественней назвать его <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(j)</tex> как вектор, полученный сдвигом вектора для столбца <tex>j</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(j)</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>j</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) and U(t[j])</tex><br />
Например, …<br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = |pattern|<br />
m = |text|<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n][m + 1] of bit, initially all 0 <br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M[j] = Bit-Shift(M[j - 1]) '''and''' U[t[j]]<br />
'''for''' j = 1..m<br />
'''if''' M[n][j]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <tex>Shift-Or</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> вычисляются правильно и алгоритм находит все вхождения образца в текст. <br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-Or&diff=37975Алгоритм Shift-Or2014-06-07T19:02:31Z<p>178.71.141.146: /* Псевдокод */</p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-Or</tex>, хотя, исходя из самого алгоритма, естественней назвать его <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(j)</tex> как вектор, полученный сдвигом вектора для столбца <tex>j</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(j)</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>j</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) and U(t[j])</tex><br />
Например, …<br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = |pattern|<br />
m = |length|<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n][m + 1] of bit, initially all 0 <br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n<br />
U[pattern[i]][i] = 1<br />
'''for''' j = 1..m<br />
M[j] = Bit-Shift(M[j - 1]) '''and''' U[t[j]]<br />
'''for''' j = 1..m<br />
'''if''' M[n][j]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <tex>Shift-Or</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> вычисляются правильно и алгоритм находит все вхождения образца в текст. <br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.</div>178.71.141.146http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_Shift-Or&diff=37973Алгоритм Shift-Or2014-06-07T19:02:05Z<p>178.71.141.146: </p>
<hr />
<div>В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-Or</tex>, хотя, исходя из самого алгоритма, естественней назвать его <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета.<br />
<br />
==Алгоритм==<br />
<br />
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.<br />
<br />
Нам потребуется двоичный массив <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>.<br />
<br />
<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>.<br />
<br />
<tex> M[i][j] =<br />
\left\{<br />
\begin{array}{ll}<br />
1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\<br />
0, & \mbox {otherwise}<br />
\end{array}<br />
\right.<br />
</tex><br />
<br />
Например, пусть <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>. <br />
<br />
Получаем, что элементы, равные <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>. <br />
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>. <br />
То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.<br />
<br />
Построение массива <tex>M</tex>.<br />
<br />
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>. <br />
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex><br />
<br />
Определим <tex>Bit-Shift(j)</tex> как вектор, полученный сдвигом вектора для столбца <tex>j</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется. <br />
То есть <tex>Bit-Shift(j)</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>j</tex>.<br />
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex><br />
<br />
Из определения, нулевой столбец <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>. <br />
<tex>M[j] = Bit-Shift(M[j - 1]) and U(t[j])</tex><br />
Например, …<br />
<br />
==Псевдокод==<br />
<br />
'''string''' bitap_search('''string''' text, '''string''' pattern)<br />
n = |pattern|<br />
m = |length|<br />
'''if''' n == 0<br />
'''return''' text<br />
M = new array [n][m + 1] of bit, initially all 0 <br />
U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0<br />
'''for''' i = 1..n<br />
U[pattern[i]][i] = 1<br />
M[0][i] = 0<br />
'''for''' j = 1..m<br />
M[j] = Bit-Shift(M[j - 1]) '''and''' U[t[j]]<br />
'''for''' j = 1..m<br />
'''if''' M[n][j]<br />
'''return''' text[j - n + 1..j]<br />
'''return''' null<br />
<br />
==Корректность==<br />
Докажем, что метод <tex>Shift-Or</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> вычисляются правильно и алгоритм находит все вхождения образца в текст. <br />
<br />
==Эффективность==<br />
Сложность алгоритма составляет <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> соответсвенно.</div>178.71.141.146