Алгоритм Shift-Or - История изменений

178.71.141.146: Перенаправление на Алгоритм Shift-And

2014-06-08T17:02:47Z

Перенаправление на Алгоритм Shift-And

178.71.141.146: /* Псевдокод */

2014-06-07T19:25:59Z

‎Псевдокод

178.71.141.146: /* Псевдокод */

2014-06-07T19:21:23Z

‎Псевдокод

178.71.141.146: /* Псевдокод */

2014-06-07T19:17:57Z

‎Псевдокод

178.71.141.146: /* Псевдокод */

2014-06-07T19:17:13Z

‎Псевдокод

178.71.141.146: /* Псевдокод */

2014-06-07T19:04:11Z

‎Псевдокод

178.71.141.146: /* Псевдокод */

2014-06-07T19:02:31Z

‎Псевдокод

178.71.141.146 в 19:02, 7 июня 2014

2014-06-07T19:02:05Z

178.71.173.116: /* Псевдокод */

2014-06-07T17:34:32Z

‎Псевдокод

178.71.173.116: Отмена правки 37936 участника 178.71.173.116 (обсуждение)

2014-06-07T17:31:54Z

Отмена правки 37936 участника 178.71.173.116 (обсуждение)

← Предыдущая		Версия 17:02, 8 июня 2014
Строка 1:		Строка 1:
−	В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-Or</tex>, хотя, исходя из самого алгоритма, естественней назвать его <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета.	+	#перенаправление [[Алгоритм Shift-And]]
−
−	~~==Алгоритм==~~
−
−	~~Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.~~
−
−	Нам потребуется двоичный массив <tex>M</tex> размером <tex>n \cdot (m + 1)</tex>, в котором индекс <tex>i</tex> пробегает значения от <tex>1</tex> до <tex>n</tex>, а индекс <tex>j</tex> {{---}} от <tex>0</tex> до <tex>m</tex>.
−
−	~~<tex>M~~[i][j] = 1</tex>, если первые <tex>i</tex> символов <tex>p</tex> точно совпадают с <tex>i</tex> символами <tex>t</tex>, кончаясь на позиции <tex>j</tex>; иначе <tex>M[i][j] = 0</tex>.
−
−	~~<tex> M[i][j] =~~
−	~~\left\{~~
−	~~\begin{array}{ll}~~
−	~~1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\~~
−	~~0, & \mbox {otherwise}~~
−	~~\end{array}~~
−	~~\right.~~
−	~~</tex>~~
−
−	~~Например, пусть <tex>t = california</tex>, <tex>p = for</tex>. Тогда <tex>M[1][5] = M[2][6] = M[3][7] = 1</tex>, остальные <tex>M[i][j] = 0</tex>.~~
−
−	Получаем, что элементы, равные <tex>1</tex>, в строчке <tex>i</tex> показывают все места в <tex>t</tex>, где заканчиватся копии <tex>p[1..i]</tex>, а столбец <tex>j</tex> показывает все префиксы <tex>p</tex>, которые заканчиваются в позиции <tex>j</tex> строки <tex>t</tex>.
−	~~<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>.~~
−	~~То есть вычисление последней строки <tex>M</tex> решает задачу точного совпадения.~~
−
−	~~Построение массива <tex>M</tex>.~~
−
−	Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>.
−	~~Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex>~~
−
−	~~Определим <tex>Bit-~~Shift(j)</tex> как вектор, полученный сдвигом вектора для столбца <tex>j</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется.
−	~~То есть <tex>Bit~~-~~Shift(j)</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>j</tex>.~~
−	~~<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex>~~
−
−	~~Из определения, нулевой столбец <tex>M</tex> состоит из нулей. Элементы любого другого столбца <tex>M[j~~], j > 0</tex> получаются из столбца <tex>M[j - 1]</tex> и вектора <tex>U</tex> для символа <tex>t[j]</tex>. А именно, вектор для столбца <tex>j</tex> получается операцией побитового логического умножения <tex>and</tex> вектора <tex>Bit-Shift(M[j - 1]~~)</tex> и вектора <tex>U(t[j])</tex>.~~
−	~~<tex>M[j] = Bit-Shift(M[j - 1]) and U(t[j])</tex>~~
−	~~Например, …~~
−
−	~~==Псевдокод==~~
−
−	~~'''string''' bitap_search('''string''' text, '''string''' pattern)~~
−	~~n = pattern.length~~
−	~~m = text.length~~
−	~~'''if''' n == 0~~
−	~~'''return''' text~~
−	~~M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer~~
−	~~fill(M, 0)~~
−	~~U = new array [<tex>\|\Sigma\|</tex>][n] of bit, initially all 0~~
−	~~'''for''' i = 1..n // препроцессинг - вычисление вектора U~~
−	~~U[pattern[i]][i] = 1~~
−	~~'''for''' j = 1..m~~
−	~~M = Bit-Shift(M) '''&''' U[t[j]]~~
−	~~'''if''' M[n]~~
−	~~'''return''' text[j - n + 1..j]~~
−	~~'''return''' null~~
−
−	~~==Корректность==~~
−	Докажем, что метод <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> вычисляются правильно и алгоритм находит все вхождения образца в текст.
−
−	~~==Эффективность==~~
−	Сложность алгоритма составляет <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> соответсвенно.

@@ Строка 45: / Строка 45: @@
              '''return''' text
          M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer
-         M = 0
+         fill(M, 0)
          U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0
          '''for''' i = 1..n // препроцессинг - вычисление вектора U
@@ Строка 51: / Строка 51: @@
          '''for''' j = 1..m
              M = Bit-Shift(M) '''&''' U[t[j]]
-        '''for''' j = 1..m
+             '''if''' M[n]
                  '''return''' text[j - n + 1..j]
          '''return''' null

@@ Строка 47: / Строка 47: @@
          M = 0
          U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0
-         '''for''' i = 1..n
+         '''for''' i = 1..n // препроцессинг - вычисление вектора U
              U[pattern[i]][i] = 1
          '''for''' j = 1..m

@@ Строка 50: / Строка 50: @@
              U[pattern[i]][i] = 1
          '''for''' j = 1..m
-             M = Bit-Shift(M) '''and''' U[t[j]]
+             M = Bit-Shift(M) '''&''' U[t[j]]
          '''for''' j = 1..m
              '''if''' M[j]

@@ Строка 40: / Строка 40: @@
      '''string''' bitap_search('''string''' text, '''string''' pattern)
-         n = |pattern|
+         n = pattern.length
-         m = |text|
+         m = text.length
          '''if''' n == 0
              '''return''' text
-         M = new array [n][m + 1] of bit, initially all 0
+         M = new array [n] of bit // для поиска коротких слов достаточно одной переменной типа integer
          U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0
          '''for''' i = 1..n
              U[pattern[i]][i] = 1
          '''for''' j = 1..m
-             M[j] = Bit-Shift(M[j - 1]) '''and''' U[t[j]]
+             M = Bit-Shift(M) '''and''' U[t[j]]
          '''for''' j = 1..m
-             '''if''' M[n][j]
+             '''if''' M[j]
                  '''return''' text[j - n + 1..j]
          '''return''' null

@@ Строка 33: / Строка 33: @@
 <tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex>
-Из определения, нулевой столбец <tex>M</tex> состоит из нулей. Элементы любого другого столбца <tex>j > 0</tex> получаются из столбца <tex>j - 1</tex> и вектора <tex>U</tex> для символа <tex>t[j]</tex>. А именно, вектор для столбца <tex>j</tex> получается операцией побитового логического умножения <tex>and</tex> вектора <tex>Bit-Shift(j - 1)</tex> и вектора <tex>U(t[j])</tex>.
+Из определения, нулевой столбец <tex>M</tex> состоит из нулей. Элементы любого другого столбца <tex>M[j], j > 0</tex> получаются из столбца <tex>M[j - 1]</tex> и вектора <tex>U</tex> для символа <tex>t[j]</tex>. А именно, вектор для столбца <tex>j</tex> получается операцией побитового логического умножения <tex>and</tex> вектора <tex>Bit-Shift(M[j - 1])</tex> и вектора <tex>U(t[j])</tex>.
-<tex>M[j] = Bit-Shift(j - 1)  and  U(t[j])</tex>
+<tex>M[j] = Bit-Shift(M[j - 1])  and  U(t[j])</tex>
 Например, …
 ==Псевдокод==
-     string bitap_search(string text, string pattern)
+     '''string''' bitap_search('''string''' text, '''string''' pattern)
-         m = length(pattern)
+        n = |pattern|
-         if m == 0
+         m = |length|
-             return text
+         '''if''' n == 0
-         M := new array[m+1] of bit, initially all 0
+             '''return''' text
-         M[0] = 1
+         M = new array [n][m + 1] of bit, initially all 0
-         for i = 0..length(text)
+         U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0
-             for k = m..1 /* Update the bit array. */
+         '''for''' i = 1..n
-                M[k] = M[k - 1] & (text[i] == pattern[k - 1])
+            U[pattern[i]][i] = 1
-             if M[m]:
+             M[0][i] = 0
-                 return (text + i - m) + 1
+        '''for''' j = 1..m
-         return null
+            M[j] = Bit-Shift(M[j - 1]) '''and''' U[t[j]]
 ==Корректность==

@@ Строка 39: / Строка 39: @@
 ==Псевдокод==
-     int preSo(char *x, int m, unsigned int S[]) {
+    algorithm bitap_search(text : string, pattern : string) returns string
-          unsigned int j, lim;
+        m := length(pattern)
-          int i;
+        if m == 0
-          for (i = 0; i < ASIZE; ++i)
+            return text
-          S[i] = ~0;
+        /* Initialize the bit array R. */
-          for (lim = i = 0, j = 1; i < m; ++i, j <<= 1) {
+        R := new array[m+1] of bit, initially all 0
-             S[x[i]] &= ~j;
+        R[0] = 1
-             lim |= j;
+        for i = 0; i < length(text); i += 1:
+            /* Update the bit array. */
-          lim = ~(lim>>1);
+            for k = m; k >= 1; k -= 1:
-          return(lim);
+                R[k] = R[k-1] & (text[i] == pattern[k-1])
+            if R[m]:
+                return (text+i - m) + 1
-    void SO(char *x, int m, char *y, int n) {
+        return nil
 ==Корректность==