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

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. Гугл.
Поделиться публикацией
Комментарии 16
    0
    Правильно ли я понимаю, что этот алгоритм ничем не лучше наивного сравнения? Если так, то для чего он нужен?
      +3
      Пардон, не сразу понял, что речь идёт про нечёткий поиск.
        +1
        На сколько я знаю, есть два варианта алгоритма — один для четкого, другой для нечеткого поиска.

        На практике работает довольно быстро. Выигрыш достигается за счет побитовых операций.
          0
          Что-то не совсем понятно, в чем преимущество перед префикс-функцией. Ну разве что для паттернов короче 64 символов может быть будет чуть быстрее.
        0
        Он достаточно быстр, если искомое слово влазит в машинное слово (простите за каламбур), работаем с маленьким алфавитом (ASCII, например) и имеем большой текст в котором нужно искать.
        –3
        Спасибо, хорошая статья.
          0
          Не совсем понятно, как находить частичные совпадения, если Вы предлагаете хранить только два столбца. Разве при этом информация не теряется?
            0
            Не совсем понял вопроса. Например, на этой картинке:
            image
            если у нас есть только 8 столбец, то по нему мы можем определить, что на данном символе (8 в T) заканчивается совпадение первых 4 символов из P (т.к. в 4 строке стоит единица). То есть у нас совпали предыдущие 4 символа.

            Или я не правильно понял, что Вы имеете ввиду?
            +1
            Ув. tltshnik, ссылки на источники информации в завершающей части статьи оформляйте аккуратнее. Сайт поисковой системы, на который Вы указываете, — слишком всеобъемлющий источник.
              +15
              Ваша ссылка вообще никуда не ведёт.
                0
                Список используемой литературы:
                — Библиотека им. Ленина

                Удобно для дипломников. Наверняка что-нибудь найдется.
                  0
                  Обязательно учту при написании других постов.
                  0
                  похоже на репост учебника по СиАОДу третьего курса. раз автор не удосужился, я накидаю ссылок: Виктор Дмитриевич Колдаев «Алгоритмы и структуры данных». я у него учился, да. алсо, автор забыл указать что для частных случаев функция сложности этого алгоритма квадратичная, поэтому его оценка сложности неверная. вычислять эти сдвиги побитово очень плохо, да и вообще есть гораздо более простой алгоритм, где просто так же передвигаем окно с шагом в 1 байт и добавляем к контрольной сумме байт, входящий в окно и вычитаем байт, покидающий окно и на каждом шаге просто сравнимаем контрольную сумму окна и образца.
                    0
                    кому интересно — в книжке выше есть так же алгоритм кнута-морриса-пратта и другие алгоритмы поиска с гарантированным временем O(n). правда насчёт редакции книжки подсказать не могу, но наверняка в последней всё есть
                      0
                      насчёт функции сложности прошу прощения — всё верно указано
                      0
                      На самом деле, бо́льшую часть информации я брал из книги, которая стоит первой в ссылках. Но изложил тему, как мне кажется, в менее формализованном виде. А про учебник, о котором Вы сказали, я слышу в первый раз.

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое