Pull to refresh

Описание работы алгоритма Shift-OR для поиска подстроки в строке

Reading time 3 min
Views 7.9K
1. Вместо вступления.

Недавно пришлось разбираться в работе алгоритма Shift-Or, который позволяет найти подстроку в строке. По результатам этого разбора я и решил написать этот пост в надежде, что кому-то он поможет понять, как работает этот алгоритм, быстрее чем мне.

Собственно, главное отличие алгоритма от, например, «наивного сравнения», заключается в том, что в его основе лежит логические операции, а именно логическое умножение (оно же AND, оно же конъюнкция).


2. Что нужно для работы алгоритма.

Для начала нужно ввести некоторые обозначения. Пусть у нас P — это будет образец, который мы будем искать в тексте, а T — это собственно сам текст, по которому будет происходить поиск. P имеет длину n, а T — длину m.

В алгоритме строится некая (пока непонятно как образованная) матрица M. Эта матрица по сути своей является просто двоичным массивом (состоит только из 0 и 1). M имеет размеры n x (m+1). В этой матрице у нас i-ый индекс пробегает значения от 1 до n, а j-ый имеет значения от 0 до m. Формально, по определению, «элемент M(i,j) = 1 тогда и только тогда, когда первые i символов P точно совпадают с i символами T, кончаясь на позиции j». Соответственно, так как массив двоичный, то во всех остальных случаях элемент равен 0. Для того, чтобы лучше понять что такое матрица M рассмотрим пример:

Пусть текст T = «CALIFORNIA» и мы хотим найти в этом тексте образец P = «FOR». (Естественно такой короткий «текст» взят для простоты примера). Мы видим, что в тексте «CALIFORNIA» у нас 10 символов, значит m = 10. В образце P у нас 3 символа, значит n = 3. Соответственно, матрица M будет иметь размеры 3x11. Итак, мы получаем вот такую таблицу:


Также можно увидеть, что главной для нас является лишь последняя строка таблицы. Ведь в ней единицы содержатся только в том случае, если образец P полностью входит в текст T.

3. Так как же строится эта матрица M?

Для того, чтобы такую матрицу могла построить программа, необходимо ввести ещё две операции.

3.1. Двоичный вектор U(x).

Этот вектор представляет из себя просто двоичную строку длины n (как и образец P), в которой стоят единицы в тех же позициях, где в образце P стоит буква x.
Например, пусть у нас P = «ABACDEAB». Для него вектор U(A) = 10100010:


3.2. Операция Bit-Shift(j)

Это операция производится над двоичным столбцом j. Она очень простая и заключается лишь в сдвиге столбца на 1 позицию вниз и приписывание сверху единицы. Длина столбца не изменяется, соответственно последнее значение столбца мы теряем.
Например, у нас есть столбец длины 10: 0011010101. Применим к нему три раза операцию Bit-Shift:

На рисунке выше тёмно-бирюзовым цветом выделены элементы, которые остаются от первоначального столбца, а жёлтым выделены те, которые добавляются в результате применения операции Bit-Shift.

Собственно после того как мы ввели эти две операции осталось самая простая и самая важная часть: собственно построение матрицы.
Она вычисляется очень просто. И я предлагаю рассмотреть это построение на примере.
Пусть у нас образец P = «ABAAC» (n = 5) и текст T = «XABXABAAXA» (m = 10).
Первоначально заполняем нулевой столбец нулями:

Все последующие столбцы вычисляются на основании предыдущего. Затем мы применяем операцию Bit-Shift для нулевого столбца. получаем столбец:

И вычисляем столбец U(x). Здесь «x» это первый символ проверяемого текста T. Получим полностью нулевой столбец, так как символ «x» в P не встречается. Затем мы применяем операцию логического умножения AND к этим столбцам:

Пока у нас матрица M выглядит так:

Дальнейшее заполнение матрицы идёт абсолютно аналогично. Для второго столбца U(A) = 10110, а Bit-Shift(1) = 10000. Так второй столбец у нас получается 10000 и т.д. Каждый последующий столбец заполняется на основании предыдущего. Общая формула для заполнения j-го столбца матрицы M выглядит так:

В итоге, после проделывания данной операции над всеми столбцами мы получим готовую матрицу M:

Как видно полного вхождения P в T у нас нет, так как последняя строка матрицы не содержит единиц. Но зато есть частичные вхождения (если они вдруг нам нужны).

4. Вместо заключения.

Сложность данного алгоритма составляет O(mn), что в принципе, не так мало. Но у алгоритма есть и приятные стороны. Во-первых он очень прост в реализации и в понимании того, как он работает. Во-вторых, так как каждый столбец матрицы M вычисляется на основании предыдущего, то нам нет необходимости хранить в памяти всю матрицу, а достаточно держать только два столбика. На практике же алгоритм хорошо справляется при поиске небольших образцов P, таких как, например, английское слово. Несколько модифицированная версия данного алгоритма лежит в основе работы unix'овой утилите agrep которая ищет образец в тексте с заданным числом ошибок.

P.S.

Да, я видел этот топик, в котором описывается тот же алгоритм, но в своём посте я попытался максимально приблизиться к объяснению темы на примерах, так как считаю что в некоторых случаях лучше показать как это работает, нежели рассказать.

Ссылки.

1. Дэн Гасфилд. Строки, деревья и последовательности в алгоритмах. 2003г.
2. Bitap
3. Гугл.
Tags:
Hubs:
+42
Comments 16
Comments Comments 16

Articles