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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
==Алгоритм==
 
==Алгоритм==
  
Пусть <tex>p</tex> шаблон длины <tex>n</tex>, <tex>t</tex> текст длины <tex>m</tex>.
+
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.
  
Нам потребуется двоичный массив <tex>M</tex> размером <tex>n * (m + 1)</tex>, в котором индекс <tex>i</tex> пробегает значения от <tex>1</tex> до <tex>n</tex>, а индекс <tex>j</tex> от <tex>0</tex> до <tex>m</tex>.
+
Нам потребуется двоичный массив <tex>M</tex> размером <tex>n * (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] =</tex> { <tex>1</tex>, если первые <tex>i</tex> символов <tex>p</tex> точно совпадают с <tex>i</tex> символами <tex>t</tex>, кончаясь на позиции <tex>j</tex>; <tex>0</tex> иначе }
+
<tex>M[i][j] =</tex> { <tex>1</tex>, если первые <tex>i</tex> символов <tex>p</tex> точно совпадают с <tex>i</tex> символами <tex>t</tex>, кончаясь на позиции <tex>j</tex>; <tex>0</tex> {{---}} иначе}.
  
То есть <tex>M[i][j] = 1</tex> тогда и только тогда, когда <tex>p[1..i] = t[j i + 1..j]</tex>.
+
То есть <tex>M[i][j] = 1</tex> тогда и только тогда, когда <tex>p[1..i] = t[j - i + 1..j]</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>t = california</tex>, <tex>p = for</tex>. Тогда <tex>M[1][5] = M[2][6] = M[3][7] = 1</tex>, остальные <tex>M[i][j] = 0</tex>.  
 
Получаем, что  элементы, равные <tex>1</tex>, в строчке <tex>i</tex> показывают все места в <tex>t</tex>, где заканчиватся копии <tex>p[1..i]</tex>, а столбец <tex>j</tex> показывает все префиксы <tex>p</tex>, которые заканчиваются в позиции <tex>j</tex> строки <tex>t</tex>.  
 
Получаем, что  элементы, равные <tex>1</tex>, в строчке <tex>i</tex> показывают все места в <tex>t</tex>, где заканчиватся копии <tex>p[1..i]</tex>, а столбец <tex>j</tex> показывает все префиксы <tex>p</tex>, которые заканчиваются в позиции <tex>j</tex> строки <tex>t</tex>.  
Строка 19: Строка 19:
  
 
Определим <tex>Bit-Shift(j)</tex> как вектор, полученный сдвигом вектора для столбца <tex>j</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</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>Bit-Shift(j)</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>j</tex>.
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) (1, 0, 0, 1, 0, 1, 1, 0)</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>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>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[j] = Bit-Shift(j 1) and U(t[j])</tex>
+
<tex>M[j] = Bit-Shift(j - 1) and U(t[j])</tex>
 
Например, …  
 
Например, …  
  
Строка 44: Строка 44:
  
 
==Корректность==
 
==Корректность==
Докажем, что метод <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>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(nm)</tex>, на препроцессинг построение массива <tex>U</tex> требуется <tex>O(сигма*n)</tex> операций и памяти. Если же <tex>n</tex> не превышает длину машинного слова, то сложность получается <tex>O(m)</tex> и <tex>O(n + сигма)</tex> соответсвенно.
+
Сложность алгоритма составляет <tex>O(n * m)</tex>, на препроцессинг {{---}} построение массива <tex>U</tex> требуется <tex>O(|\Sigma| * n)</tex> операций и памяти. Если же <tex>n</tex> не превышает длину машинного слова, то сложность получается <tex>O(m)</tex> и <tex>O(n + |\Sigma|)</tex> соответсвенно.

Версия 21:59, 6 июня 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 * (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] =[/math] { [math]1[/math], если первые [math]i[/math] символов [math]p[/math] точно совпадают с [math]i[/math] символами [math]t[/math], кончаясь на позиции [math]j[/math]; [math]0[/math] — иначе}.

То есть [math]M[i][j] = 1[/math] тогда и только тогда, когда [math]p[1..i] = t[j - i + 1..j][/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] Например, …

Псевдокод

   algorithm bitap_search(text : string, pattern : string) returns string
       m := length(pattern)
       if m == 0
           return text
       /* Initialize the bit array R. */
       R := new array[m+1] of bit, initially all 0
       R[0] = 1
       for i = 0; i < length(text); i += 1:
           /* Update the bit array. */
           for k = m; k >= 1; k -= 1:
               R[k] = R[k-1] & (text[i] == pattern[k-1])
           if R[m]:
               return (text+i - m) + 1
       return nil

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

Докажем, что метод [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 * m)[/math], на препроцессинг — построение массива [math]U[/math] требуется [math]O(|\Sigma| * n)[/math] операций и памяти. Если же [math]n[/math] не превышает длину машинного слова, то сложность получается [math]O(m)[/math] и [math]O(n + |\Sigma|)[/math] соответсвенно.