Хороший суффикс и что стоит в библиотеках

Если ты посчитаешь сдвиги хорошего суффикса для abab, объяснишь, зачем в правиле условие про предыдущий символ, и скажешь, что стоит за in в Python, - листай до «Теперь сам».

Как думаешь, что выбросил Хорспул

Текст - тысяча букв a. Образец - b и девять букв a. Хорспул сравнивает с конца: девять раз a = a, на десятом сравнении a ≠ b. Под концом окна стоит a, сдвиг по таблице - единица. И так 991 раз, 9910 сравнений.

Прежде чем читать дальше, подумай: что алгоритм знает о тексте после девяти успешных сравнений и одного неуспешного? И на сколько можно сдвинуть окно, если этим знанием воспользоваться?

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

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

Двигать ключ на один зубец бессмысленно, если после этого под известными пазами окажутся зубцы другой формы. Имеет смысл только тот сдвиг, при котором под тремя знакомыми пазами снова встанет участок ключа той же формы. Где у ключа есть ещё такой участок - можно выяснить дома, заранее, разглядывая один ключ.

Механизм: совпавший хвост как знание о тексте

Расхождение случилось в позиции j образца. Всё, что правее, совпало: кусок p[j+1 .. m−1] стоит в тексте. Его называют хорошим суффиксом. Про текст известно ещё одно: символ над позицией j - НЕ p[j].

Образец abcab. Пусть совпал хвост ab, расхождение на c:

текст      . . X a b . . . . .          X ≠ c,  ab совпало
образец    a b c a b                    j = 2
сдвиг 1      a b c a b                  под "ab" встало "ca" - не годится
сдвиг 2        a b c a b                под "ab" встало "bc" - не годится
сдвиг 3          a b c a b              под "ab" встало "ab" - годится

Сдвиг на 3 - первый, который не противоречит известному. Для каждого места расхождения такой сдвиг считается заранее:

расхождение в позиции     совпавший хвост     сдвиг
        4                     (пусто)            1
        3                     b                  5
        2                     ab                 3
        1                     cab                3
        0                     bcab               3
   нет (вхождение)            abcab              3

Строка j = 3 стоит разобрать. Совпал хвост b, расхождение на a. Буква b в образце есть ещё в позиции 1 - сдвиг на 3 поставил бы её под знакомый кусок текста. Но перед ней стоит a, та самая буква, которая только что не подошла: расхождение повторится в том же месте. Правило такой сдвиг запрещает. Других b нет, и сам образец с b не начинается - сдвиг на всю длину, 5.

Строки j = 1 и j = 0 - второй случай: целиком совпавший хвост в образце больше не встречается, но его КОНЕЦ (ab) совпадает с НАЧАЛОМ образца. Сдвиг совмещает их.

Правило

После расхождения в позиции j окно сдвигается на наименьшее s ≥ 1, при котором выполнены два условия. Первое: каждый символ образца, оказавшийся под совпавшим хвостом, равен символу хвоста над ним (позиции хвоста, под которыми после сдвига образца уже нет, не проверяются). Второе: символ образца, оказавшийся под местом расхождения, не равен p[j]. После найденного вхождения сдвиг равен периоду образца - наименьшему сдвигу, при котором образец совпадает сам с собой на перекрытии; в главе про КМП это было m − π[m − 1]. Полный Бойер-Мур берёт максимум из этого сдвига и сдвига по плохому символу - тому, на котором случилось расхождение.

Разбор: таблица по определению и поиск с двумя правилами

Таблицу можно посчитать за O(m) через Z-функцию перевёрнутого образца. Здесь она считается прямо по правилу - медленно, зато каждая строка читается как формулировка:

def horoshij(p):
    m = len(p)
    gs = [0] * (m + 1)                # gs[j + 1] - сдвиг при расхождении в j; gs[0] - после вхождения
    j = -1
    while j < m:
        s = 1
        while True:
            ok = True
            x = j + 1
            while x < m:              # условие первое: под хвостом те же символы
                if x - s >= 0 and p[x - s] != p[x]:
                    ok = False
                    break
                x = x + 1
            if ok and j >= 0 and j - s >= 0 and p[j - s] == p[j]:
                ok = False            # условие второе: под расхождением другой символ
            if ok:
                break
            s = s + 1
        gs[j + 1] = s
        j = j + 1
    return gs

print(horoshij("abcab"))              # [3, 3, 3, 3, 5, 1]

Цикл по s всегда кончается: при s = m образец уезжает за хвост целиком, проверять нечего.

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

def bm(t, p):
    n = len(t)
    m = len(p)
    posl = {}
    i = 0
    while i < m:
        posl[p[i]] = i
        i = i + 1
    gs = horoshij(p)
    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
        s = gs[j + 1]                 # j - где остановилось сравнение, -1 при вхождении
        if j >= 0:
            b = j - posl.get(t[i + j], -1)      # плохой символ: совместить с правым таким же
            if b > s:
                s = b                 # больший из двух сдвигов
        i = i + s
    return [nashli, sravn]

Ответ на вопрос из начала урока. Образец b и девять a, совпал хвост из девяти a, расхождение в позиции 0. Девять букв a подряд в образце есть только в хвосте, и на a образец не начинается. Сдвиг - вся длина, 10. Сравнений: 100 окон по 10, ровно 1000 вместо 9910.

Разбор: замер и граница правила

Те же тексты, что в прошлом уроке, n = 10 000. В столбцах - сравнения символов.

алфавит k     m      КМП       Хорспул     оба правила
   26         20    10 394        760          760
    4         20    12 509      5 195        3 555
    4         40    12 503      4 430        2 376
    2         20    13 435     14 962        5 659
    2         40    13 425     12 101        2 723

На латинском алфавите хороший суффикс не дал ничего: расхождение почти всегда на первом же сравнении, совпавшего хвоста нет, и правило вырождается в сдвиг на единицу - его перекрывает плохой символ. На двух буквах картина обратная: хвосты длинные, плохой символ бессилен, и вся скорость идёт от второго правила. Вместе они закрывают слабые места друг друга - 2723 сравнения на 10 000 символов двоичного текста.

Теперь граница. Текст "a" * 1000, образец "a" * 10: вхождение на каждой позиции. После вхождения сдвиг равен периоду образца - единице, и каждое окно сравнивается заново целиком: 9910 сравнений. Оба правила на месте, а квадрат вернулся. Лечится это правилом Галила: после сдвига на период часть окна гарантированно совпадает, и её не перепроверяют. С ним Бойер-Мур линеен на любых данных. Без него доказано только, что на тексте, где образца нет, сравнений не больше 3n.

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

Первое: слабое правило вместо сильного. Если забыть второе условие - про символ под местом расхождения, - таблица для abcab в строке j = 3 даст 3 вместо 5. Ответ поиска останется верным: слабое правило тоже не перескакивает вхождений. Теряется скорость, и линейная оценка перестаёт выполняться.

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

Третье: квадрат при многих вхождениях. Поиск всех вхождений короткого периодичного образца в периодичном тексте без правила Галила стоит n · m. На тестах «найти первое вхождение» это не видно.

Четвёртое: подготовка дороже поиска. Таблица по определению стоит порядка m³. Для образца в пару десятков символов это незаметно; для тысячи - миллиард действий. В рабочем коде таблицу строят за линейное время, и это самая запутанная часть алгоритма: в первой публикации способ её построения был с ошибкой, которую исправили через три года.

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

Знать правило нужно не затем, чтобы писать его руками, а затем, чтобы понимать выбор готовых инструментов. Вот что стоит за поиском подстроки в разных местах:

где                             что внутри
CPython: str.find, in           Хорспул с битовой маской символов образца;
                                для длинных образцов - двусторонний алгоритм (с версии 3.10)
glibc: strstr, memmem           двусторонний алгоритм
Rust: str::find                 двусторонний алгоритм
GNU grep, фиксированная строка  Бойер-Мур; для набора строк - Ахо-Корасик
Go: strings.Index               команды процессора для коротких образцов, Рабин-Карп для длинных
Java: String.indexOf            наивный поиск, ускоренный командами процессора

Двусторонний алгоритм (Крошмор и Перрен, 1991) режет образец на две части в особой точке: правая сравнивается слева направо, левая - справа налево. Точка находится по одному образцу за линейное время; почему она существует и как её искать - отдельная теория, в курс она не входит. Он линеен в худшем случае, как КМП, прыгает, как Бойер-Мур, и не строит ни одной таблицы - дополнительная память постоянная. Для библиотечной функции это решающее свойство: не надо выделять память на каждый вызов.

До версии 3.10 в CPython двустороннего алгоритма не было, и специально подобранная пара строк делала in квадратичным: на длинных строках поиск занимал секунды вместо миллисекунд. Это была зарегистрированная проблема производительности, а не теория: линейная гарантия понадобилась обычной функции обычного языка.

Теперь сам

Образец abab. Найди сдвиг по правилу хорошего суффикса для расхождения в позиции 2 (совпал хвост b) и в позиции 1 (совпал хвост ab).