|
|
| (не показано 16 промежуточных версий 3 участников) |
| Строка 1: |
Строка 1: |
| − | В 1990ые годы Рикардо Беза-Йетс (Baeza-Yates) и Гастон Гоннет (Gonnet) изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом Shift-Or, хотя, исходя из самого алгоритма, естественней назвать его Shift-And. Также алгоритм известен как bitap алгоритм и алгоритм Беза-Йетса-Гоннета.
| + | #перенаправление [[Алгоритм Shift-And]] |
| − | | |
| − | ==Алгоритм==
| |
| − | | |
| − | Пусть p – шаблон длины n, t – текст длины m.
| |
| − | | |
| − | Нам потребуется двоичный массив M размером n * (m + 1), в котором индекс i пробегает значения от 1 до n, а индекс j – от 0 до m.
| |
| − | M(i,j) ={1, если первые i символов p точно совпадают с i символами t, кончаясь на позиции j; 0 — иначе}
| |
| − | | |
| − | То есть M(i,j) = 1 тогда и только тогда, когда p[1..i] = t[j – i + 1..j].
| |
| − | Например, пусть t = california, p = for. Тогда M(1, 5) = M(2, 6) = M(3, 7) = 1, остальные M(i, j) = 0.
| |
| − | Получаем, что элементы, равные 1, в строчке I показывают все места в t, где заканчиватся копии p[1..i], а столбец j показывает все префиксы p, которые заканчиваются в позиции j строки t.
| |
| − | M(n, j) = 1 тогда, когда вхждение p заканчивается в позиции j строки t.
| |
| − | То есть вычисление последней строки M решает задачу точного совпадения.
| |
| − | Построение массива M.
| |
| − | Создадим для каждого символа алфавита x двоичный вектор U(x) длины n. U(x) равно 1 в тех позициях p, где стоит символ x.
| |
| − | Например, p = abacdeab, U(a) = 10100010
| |
| − | | |
| − | Определим Bit-Shift(j) как вектор, полученный сдвигом вектора для столбца j вниз на одну позицию и записью 1 в первой позиции. Старое значение в позиции n теряется.
| |
| − | То есть Bit-Shift(j) состоит из 1, к которой приписаны первые n – 1 битов столбца j.
| |
| − | (0, 0, 0, 1, 0, 1, 1, 0, 1) → (1, 0, 0, 1, 0, 1, 1, 0)
| |
| − | | |
| − | Из определения, нулевой столбец M состоит из нулей. Элементы любого другого столбца j > 0 получаются из столбца j – 1 и вектора U для символа t[j]. А именно, вектор для столбца j получается операцией побитового логического умножения and вектора Bit-Shift(j – 1) и вектора U(t[j]).
| |
| − | M(j) = Bit-Shift(j – 1) and U(t[j])
| |
| − | Например, …
| |
| − | | |
| − | ==Псевдокод==
| |
| − | | |
| − | 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
| |
| − | | |
| − | ==Корректность==
| |
| − | Докажем, что метод Shift-Or правильно вычисляет элементы массива M. Заметим, что для любого I > 1элемент M(i, j) = 1 т и тт, когда p[1..i – 1] совпадает с t[j – i + 1..j], а символ p[i] совпадает с t[j]. Первое условие выполнено, когда элемент массива M(i – 1, j – 1) = 1, а второе — когда i-ый бит вектора U для символа t[j] равен 1. После сдвига столбца j – 1 алгоритм логически умножает элемент M(i – 1, j – 1) столбца j – 1 на элемент i вектора U(t[j]). Следовательно, все элементы M вычисляются правильно и алгоритм находит все вхождения образца в текст.
| |
| − | | |
| − | ==Эффективность==
| |
| − | Сложность алгоритма составляет O(nm), на препроцессинг — построение массива U требуется O(сигма*n) операций и памяти. Если же n не превышает длину машинного слова, то сложность получается O(m) и O(n + сигма) соответсвенно.
| |
