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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
(Псевдокод)
Строка 39: Строка 39:
 
==Псевдокод==
 
==Псевдокод==
  
    algorithm bitap_search(text : string, pattern : string) returns string
+
    int preSo(char *x, int m, unsigned int S[]) {
        m := length(pattern)
+
          unsigned int j, lim;
        if m == 0
+
          int i;
            return text
+
          for (i = 0; i < ASIZE; ++i)
        /* Initialize the bit array R. */
+
          S[i] = ~0;
        R := new array[m+1] of bit, initially all 0
+
          for (lim = i = 0, j = 1; i < m; ++i, j <<= 1) {
        R[0] = 1
+
            S[x[i]] &= ~j;
        for i = 0; i < length(text); i += 1:
+
            lim |= j;  
            /* Update the bit array. */
+
          }
            for k = m; k >= 1; k -= 1:
+
          lim = ~(lim>>1);
                R[k] = R[k-1] & (text[i] == pattern[k-1])
+
          return(lim);
            if R[m]:
+
    }
                return (text+i - m) + 1
+
 
        return nil
+
    void SO(char *x, int m, char *y, int n) {
 +
          unsigned int lim, state;
 +
          unsigned int S[ASIZE];
 +
          int j;
 +
          if (m > WORD)
 +
              error("SO: Use pattern size <= word size");
 +
          /* Preprocessing */  
 +
          lim = preSo(x, m, S);  
 +
          /* Searching */
 +
          for (state = ~0, j = 0; j < n; ++j) {
 +
              state = (state<<1) | S[y[j]];
 +
              if (state < lim)
 +
              OUTPUT(j - m + 1);
 +
          }
 +
    }
  
 
==Корректность==
 
==Корректность==

Версия 19:00, 7 июня 2014

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

Алгоритм

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

Нам потребуется двоичный массив [math]M[/math] размером [math]n \cdot (m + 1)[/math], в котором индекс [math]i[/math] пробегает значения от [math]1[/math] до [math]n[/math], а индекс [math]j[/math] — от [math]0[/math] до [math]m[/math].

[math]M[i][j] = 1[/math], если первые [math]i[/math] символов [math]p[/math] точно совпадают с [math]i[/math] символами [math]t[/math], кончаясь на позиции [math]j[/math]; иначе [math]M[i][j] = 0[/math].

[math] M[i][j] = \left\{ \begin{array}{ll} 1, & \mbox {if p[1..i] = t[j - i + 1..j]} \\ 0, & \mbox {otherwise} \end{array} \right. [/math]

Например, пусть [math]t = california[/math], [math]p = for[/math]. Тогда [math]M[1][5] = M[2][6] = M[3][7] = 1[/math], остальные [math]M[i][j] = 0[/math].

Получаем, что элементы, равные [math]1[/math], в строчке [math]i[/math] показывают все места в [math]t[/math], где заканчиватся копии [math]p[1..i][/math], а столбец [math]j[/math] показывает все префиксы [math]p[/math], которые заканчиваются в позиции [math]j[/math] строки [math]t[/math]. [math]M[n][j] = 1[/math] тогда, когда вхождение [math]p[/math] заканчивается в позиции [math]j[/math] строки [math]t[/math]. То есть вычисление последней строки [math]M[/math] решает задачу точного совпадения.

Построение массива [math]M[/math].

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

Определим [math]Bit-Shift(j)[/math] как вектор, полученный сдвигом вектора для столбца [math]j[/math] вниз на одну позицию и записью [math]1[/math] в первой позиции. Старое значение в позиции [math]n[/math] теряется. То есть [math]Bit-Shift(j)[/math] состоит из [math]1[/math], к которой приписаны первые [math]n - 1[/math] битов столбца [math]j[/math]. [math](0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)[/math]

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

Псевдокод

    int preSo(char *x, int m, unsigned int S[]) { 
         unsigned int j, lim; 
         int i; 
         for (i = 0; i < ASIZE; ++i) 
         S[i] = ~0; 
         for (lim = i = 0, j = 1; i < m; ++i, j <<= 1) { 
            S[x[i]] &= ~j; 
            lim |= j; 
         } 
         lim = ~(lim>>1); 
         return(lim); 
   } 
   void SO(char *x, int m, char *y, int n) { 
         unsigned int lim, state; 
         unsigned int S[ASIZE]; 
         int j; 
         if (m > WORD) 
             error("SO: Use pattern size <= word size"); 
         /* Preprocessing */ 
         lim = preSo(x, m, S); 
         /* Searching */ 
         for (state = ~0, j = 0; j < n; ++j) { 
             state = (state<<1) | S[y[j]]; 
             if (state < lim) 
             OUTPUT(j - m + 1); 
         } 
   }

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

Докажем, что метод [math]Shift-Or[/math] правильно вычисляет элементы массива [math]M[/math]. Заметим, что для любого [math]i \gt 1[/math] элемент [math]M[i][j] = 1[/math] тогда и только тогда, когда [math]p[1..i - 1][/math] совпадает с [math]t[j - i + 1..j][/math], а символ [math]p[i][/math] совпадает с [math]t[j][/math]. Первое условие выполнено, когда элемент массива [math]M[i - 1][j - 1] = 1[/math], а второе — когда [math]i[/math]-ый бит вектора [math]U[/math] для символа [math]t[j][/math] равен [math]1[/math]. После сдвига столбца [math]j – 1[/math] алгоритм логически умножает элемент [math]M[i – 1][j – 1][/math] столбца [math]j - 1[/math] на элемент [math]i[/math] вектора [math]U(t[j])[/math]. Следовательно, все элементы [math]M[/math] вычисляются правильно и алгоритм находит все вхождения образца в текст.

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

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