Бойер-Мур: читать образец с конца и прыгать

Если ты построишь таблицу сдвигов Хорспула для слова data, объяснишь, почему длинный образец ищется быстрее короткого, и назовёшь данные, на которых алгоритм проигрывает КМП, - листай до «Теперь сам».

Как думаешь, можно ли не читать текст

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

Прежде чем читать дальше, ответь себе: верно ли, что любой правильный поиск обязан прочитать весь текст? И второй вопрос, на интуицию: что искать быстрее - слово из пяти букв или фразу из сорока?

На что это похоже

Представь, что ты ищешь в длинной строке слово kolobok и кладёшь на строку трафарет шириной в семь букв. Смотришь не на первую букву под трафаретом, а на последнюю, седьмую. Там стоит z.

В слове kolobok буквы z нет. Значит, как бы трафарет ни лежал, если он накрывает эту z - слово не совпадёт. Таких положений семь, и все они отброшены одним взглядом. Трафарет переезжает целиком за z, а шесть букв перед ней ты так и не прочёл - и не нужно.

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

Механизм: таблица сдвигов по символу под концом окна

Правило, по которому окно сдвигают, глядя на один символ текста, называют правилом плохого символа. У Бойера и Мура этот символ - тот, на котором случилось расхождение; у Хорспула - тот, что стоит под концом окна. Начнём с варианта Хорспула: он проще. Для каждого символа заранее считается сдвиг: на сколько надо передвинуть окно, чтобы под этим символом текста оказался такой же символ образца - самый правый из возможных.

образец    k  o  l  o  b  o  k           m = 7
индекс     0  1  2  3  4  5  6

сдвиг = расстояние от самого правого такого символа до конца образца,
        последняя позиция образца в расчёт не берётся

k → 6    (стоит в позиции 0;  позиция 6 - последняя, не считается)
o → 1    (самая правая o в позиции 5)
l → 4
b → 2
любой другой символ → 7 = m

Прогон по тексту okolo kolokola kolobok, 22 символа; пробел в схеме показан знаком _. Сравнение идёт справа налево и останавливается на первом расхождении; сдвиг берётся по символу текста под последней позицией окна, чем бы сравнение ни кончилось.

окно с 0    o k o l o _ k      k = k, _ ≠ o       2 сравнения    под концом k → сдвиг 6
окно с 6    k o l o k o l      l ≠ k              1              под концом l → сдвиг 4
окно с 10   k o l a _ k o      o ≠ k              1              под концом o → сдвиг 1
окно с 11   o l a _ k o l      l ≠ k              1              под концом l → сдвиг 4
окно с 15   k o l o b o k      все семь равны     7              вхождение

Пять окон и 12 сравнений на 22 символа текста. Наивный поиск на этих данных проверяет 16 позиций и делает 33 сравнения. Символов текста прочитано меньше, чем в нём есть.

Правило

Окно сравнивается с образцом справа налево. После сравнения - удачного или нет - окно сдвигается на величину из таблицы для символа текста под последней позицией окна. Таблица: для символа, который есть в образце не на последнем месте, - расстояние от его самого правого такого вхождения до конца образца; для всех остальных - m. Сдвиг всегда не меньше единицы и никогда не перескакивает вхождение. В лучшем случае алгоритм делает n / m сравнений, в худшем - n · m.

Разбор: программа и почему сдвиг безопасен

def horspool(t, p):
    n = len(t)
    m = len(p)
    sdvig = {}
    i = 0
    while i < m - 1:                  # последняя позиция образца не участвует
        sdvig[p[i]] = m - 1 - i       # правое вхождение перезаписывает левое
        i = i + 1
    sravn = 0
    nashli = 0
    i = 0
    while i + m <= n:
        j = m - 1
        while j >= 0:                 # справа налево
            sravn = sravn + 1
            if t[i + j] != p[j]:
                break
            j = j - 1
        if j < 0:
            nashli = nashli + 1
        c = t[i + m - 1]              # символ под концом окна
        if c in sdvig:
            i = i + sdvig[c]
        else:
            i = i + m
    return [nashli, sravn]

Почему вхождение нельзя перескочить. Пусть под концом окна стоит символ c. В любом вхождении, которое начинается правее текущего окна и ещё накрывает эту позицию, под c должен оказаться символ образца, равный c, - и стоящий левее последней позиции. Самый маленький сдвиг, при котором это возможно, ставит под c самое правое такое вхождение. Все сдвиги короче дали бы под c другой символ - расхождение гарантировано. Если c в образце (кроме последней позиции) нет, окно обязано уехать за c целиком.

Разбор: замер и где алгоритм проигрывает

Текст tekst(10000, k, 1) из первого урока прошлой главы, образец - m символов, вырезанных с позиции 5000. В столбцах - сравнения символов.

алфавит k     m      наивный       КМП      Хорспул
   26          5      10 408     10 394      2 262
   26         10      10 407     10 394      1 211
   26         20      10 407     10 394        760
   26         40      10 405     10 391        565
    4         20      13 298     12 509      5 195
    2         20      19 933     13 435     14 962

Ответ на оба вопроса из начала урока. Читать весь текст не обязательно: при m = 20 и латинском алфавите сделано 760 сравнений на 10 000 символов. И длинный образец ищется БЫСТРЕЕ короткого - 565 сравнений против 2262: чем длиннее образец, тем дальше прыжок.

Теперь две нижние строки. При четырёх буквах выигрыш перед КМП упал до 2,4 раза, при двух буквах его нет вовсе: Хорспул чуть хуже КМП, 14 962 сравнения против 13 435. Причина в таблице сдвигов: в образце из двадцати символов над двумя буквами обе буквы стоят у самого конца, и сдвиг почти всегда один или два. А сравнение с конца на маленьком алфавите долго не находит расхождения.

Худший случай строится так же, как для наивного поиска, только зеркально:

текст "a" * 1000,  образец "b" + "a" * 9      9 910 сравнений    сдвиг всегда 1
текст "a" * 1000,  образец "b" * 10             100 сравнений    сдвиг всегда 10

В первой строке девять сравнений с конца успешны, десятое находит b, а под концом окна стоит a - символ из предпоследней позиции образца, сдвиг единица. Это те же (n − m + 1) · m, что у наивного поиска. Вторая строка - лучший случай: одно сравнение на окно и прыжок на всю длину.

Что ломается без этого

Первое: последняя позиция в таблице. Если цикл построения идёт до m, а не до m − 1, последний символ образца получает сдвиг ноль. Как только под концом окна окажется этот символ, окно перестанет двигаться - программа зациклится на первом же частичном совпадении.

Второе: оригинальное правило без страховки. У Бойера и Мура сдвиг считается по символу, на котором случилось расхождение, а не по концу окна: совместить его с самым правым таким же символом образца. Если этот символ в образце стоит правее места расхождения, сдвиг выходит отрицательным. Оригинал спасает второе правило (о нём следующий урок) и взятие максимума. Вариант Хорспула этой беды не знает: его сдвиг всегда положителен.

Третье: маленький алфавит. На двоичных данных и на ДНК таблица сдвигов почти бесполезна. Замер выше - не случайность, а свойство метода: чтобы прыгать далеко, нужны символы, которых в образце нет.

Четвёртое: поток без буфера. Алгоритм смотрит на m − 1 символ вперёд от начала окна и возвращается внутри окна назад. Данные, которые нельзя перечитать, придётся складывать в буфер длиной с образец. КМП и автомату буфер не нужен.

Зачем это в работе

Первый сюжет - почему grep быстр. Поиск фиксированной строки в нём построен на Бойере-Муре: утилита не смотрит на каждый байт файла, и длинная строка поиска ускоряет её, а не замедляет. Знание об этом меняет привычку: искать по длинному уникальному куску сообщения выгоднее, чем по короткому слову.

Второй - поиск в редакторе и встроенные функции языков. Когда ты пишешь "слово" in tekst в Python, для большинства пар работает родственник Хорспула - таблица сдвигов по одному символу, ужатая до предела: вместо словаря сдвигов хранится одно число, в битах которого отмечено, какие символы вообще есть в образце. Символа нет - окно уезжает на всю длину. Что стоит рядом с ним для длинных образцов - в следующем уроке.

Третий - выбор по данным. Текст на естественном языке, журналы, исходный код - большой алфавит, Хорспул в своей стихии. Геномные данные, битовые потоки, длинные полосы одинаковых байтов - брать КМП или автомат: там гарантия важнее прыжков, которых всё равно не будет.

Теперь сам

Построй таблицу сдвигов Хорспула для образца data. Затем прогони поиск по тексту a date and data (15 символов, пробелы - обычные символы): назови начала окон по порядку и общее число сравнений.

d → 3      (позиция 0)
a → 2      (позиция 1; a в позиции 3 - последняя, не считается)
t → 1      (позиция 2)
остальные → 4

окно с 0    a _ d a      a = a, d ≠ t        2 сравнения    под концом a → сдвиг 2
окно с 2    d a t e      e ≠ a               1              под концом e → сдвиг 4
окно с 6    _ a n d      d ≠ a               1              под концом d → сдвиг 3
окно с 9    d _ d a      a = a, d ≠ t        2              под концом a → сдвиг 2
окно с 11   d a t a      все четыре равны    4              вхождение