Редактирование: Алгоритм Shift-Or

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
#перенаправление [[Алгоритм Shift-And]]
+
В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-Or</tex>, хотя, исходя из самого алгоритма, естественней назвать его <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета.
 +
 
 +
==Алгоритм==
 +
 
 +
Пусть <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> соответсвенно.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)