3622
правки
Изменения
Нет описания правки
В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift\texttt{-}And</tex>. Также алгоритм известен как <tex>bitap</tex> алгоритм и алгоритм Беза-Йетса-Гоннета. Существует вариация данного алгоритма под названием <tex>Shift\texttt{-}Or</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> {{Определение|definition =Назовём вектором <tex>Bit\texttt{-}Shift(M[j])</tex> такой вектор, который получен сдвигом столбца <tex>M[j]</tex> вниз на одну позицию и записью <tex>1</tex> в первой позиции. Старое значение в позиции <tex>n</tex> теряется.}} То есть <tex>Bit\texttt{-}Shift(M[j])</tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n - 1</tex> битов столбца <tex>M[j]</tex>. Например,
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 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\texttt{-}Shift(M[j - 1])</tex> и вектора <tex>U([t[j])]</tex>. <tex>M[j] = Bit\texttt{-}Shift(M[j - 1]) \ and \ U([t[j])]</tex>
===Псевдокод===
'''string''' bitap_search('''string''' text, '''string''' pattern)
