Наивный поиск: где в нём прячется квадрат

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

Как думаешь, сколько сравнений

Текст - тысяча букв a подряд. Образец - девять букв a и буква b в конце, всего десять символов. В тексте его нет: там вообще нет буквы b.

Прежде чем читать дальше, прикинь, сколько раз программа сравнит символ текста с символом образца, прежде чем ответит «не найдено». Около тысячи - по разу на позицию? Около десяти тысяч? И что изменится, если букву b переставить из конца образца в начало?

Слова, которыми пользуется весь раздел

Префикс строки - её начало любой длины, суффикс - её конец; на этих двух словах стоит половина раздела. Текст - строка, в которой ищут; её длина всюду дальше n. Образец - строка, которую ищут; её длина m, и почти всегда m намного меньше n. Вхождение - позиция i в тексте, начиная с которой все m символов совпадают с образцом: t[i] = p[0], t[i + 1] = p[1] и так до t[i + m − 1] = p[m − 1]. Позиции считаются с нуля, как индексы в Python.

Алфавит - набор символов, из которых составлены обе строки. Важен его размер: у двоичных данных он равен двум, у записи ДНК - четырём (A, C, G, T), у латинского текста без заглавных - двадцати шести. Дальше станет видно, что цена поиска зависит от размера алфавита сильнее, чем кажется.

Вхождений может быть несколько, и они могут перекрываться: в тексте ababab образец abab входит с позиции 0 и с позиции 2. Задача - найти все.

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

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

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

Механизм: окно, которое едет по одной клетке

текст     a b r a c a d a b r a        n = 11
образец   a b r a                      m = 4

i = 0     a b r a                      4 сравнения, вхождение
i = 1       a . . .                    1 сравнение: b ≠ a
i = 2         a . . .                  1 сравнение: r ≠ a
i = 3           a b . .                2 сравнения: a = a, c ≠ b
i = 4             a . . .              1
i = 5               a b . .            2 сравнения: a = a, d ≠ b
i = 6                 a . . .          1
i = 7                   a b r a        4 сравнения, вхождение

Последняя позиция, на которую образец ещё помещается, - n − m = 7: дальше он вылез бы за край текста. Всего позиций n − m + 1 = 8. Сравнений вышло 4 + 1 + 1 + 2 + 1 + 2 + 1 + 4 = 16, вхождений два - с позиций 0 и 7.

Программа повторяет эту таблицу буквально. Счётчик sravn в алгоритм не входит - он нужен, чтобы мерить цену:

def naive(t, p):
    n = len(t)
    m = len(p)
    sravn = 0
    nashli = 0
    i = 0
    while i + m <= n:                 # образец ещё помещается
        j = 0
        while j < m:
            sravn = sravn + 1
            if t[i + j] != p[j]:
                break                 # первое расхождение - дальше не смотрим
            j = j + 1
        if j == m:                    # дошли до конца образца без расхождений
            nashli = nashli + 1
        i = i + 1
    return [nashli, sravn]

print(naive("abracadabra", "abra"))   # [2, 16]

Правило

Наивный поиск проверяет n − m + 1 позиций и на каждой делает от одного до m сравнений. В худшем случае это (n − m + 1) · m сравнений; при m около n / 2 это примерно n² / 4, то есть квадрат от длины текста. В лучшем случае - около n сравнений; на типичном тексте - от n до 2n (чем меньше алфавит, тем ближе к 2n), потому что расхождение находится на первых же символах. Худший случай достигается, когда образец долго совпадает и расходится в самом конце: на данных из длинных повторов.

Разбор: тысяча букв и образец с подвохом в хвосте

Ответ на вопрос из начала урока. Текст "a" * 1000, образец "a" * 9 + "b". На каждой позиции первые девять сравнений успешны - там и там буква a, - и только десятое находит расхождение. Позиций 1000 − 10 + 1 = 991, сравнений на каждой ровно десять:

образец                 позиций    сравнений    на позицию
"a" * 9   + "b"           991         9 910         10
"a" * 99  + "b"           901        90 100        100
"a" * 499 + "b"           501       250 500        500

Текст один и тот же, а цена выросла в двадцать пять раз. Позиций при этом стало МЕНЬШЕ - 501 вместо 991. Растёт произведение: (n − m + 1) · m самое большое, когда m равно половине n, и последняя строка таблицы стоит ровно на этом максимуме.

Теперь переставим b в начало: образец "b" + "a" * 9. Первое же сравнение на каждой позиции - a против b - даёт расхождение. Сравнений 991, по одному на позицию. Те же буквы, тот же текст, цена в десять раз меньше. Наивному поиску важно не из чего состоит образец, а как рано он расходится с текстом.

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

Возьмём текст, в котором буквы идут без закономерности. Чтобы замер можно было повторить, текст строит маленький генератор: он гоняет число s по формуле и на каждом круге берёт по остатку одну из первых k букв алфавита. Числа 75, 74 и 65537 - параметры давно известного простого генератора; важно в нём одно: при одном и том же начальном s текст выходит один и тот же, у тебя и у меня.

def tekst(n, k, s):
    bukvy = "abcdefghijklmnopqrstuvwxyz"
    t = []
    i = 0
    while i < n:
        s = (s * 75 + 74) % 65537
        t.append(bukvy[s % k])
        i = i + 1
    return "".join(t)

t = tekst(1000, 4, 1)
print(naive(t, t[500:510]))           # [1, 1328]

Образец - десять символов, вырезанных из середины самого текста, так что одно вхождение есть наверняка. Замер для трёх размеров алфавита, n = 1000, m = 10, позиций 991:

алфавит k    сравнений    на позицию    k / (k − 1)
    2          1 962         1,98          2,00
    4          1 328         1,34          1,33
   26          1 046         1,06          1,04

Откуда последний столбец. Первое сравнение на позиции делается всегда. Второе - только если первое совпало, а при k равновозможных буквах это случается в среднем на одной позиции из k. Третье - если совпали оба, то есть на одной из k². Сумма S = 1 + 1/k + 1/k² + … равна k / (k − 1). Проверить просто: умножь её на k - получится k + 1 + 1/k + …, то есть k + S; из k · S = k + S выходит S = k / (k − 1). Слагаемых на деле не больше m, но дальние так малы, что на ответ не влияют. Замер ложится на формулу: при двух буквах около двух сравнений на позицию, при двадцати шести - чуть больше одного.

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

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

Первое: граница цикла. Условие i + m <= n легко написать как i + m < n - и последняя позиция не проверяется: образец bra в тексте abracadabra найдётся один раз вместо двух. Обратная ошибка, i < n, коварнее: чтение t[i + j] за концом строки случается, только когда хвост текста совпал с началом образца. Образец abra в том же тексте на последней позиции совпадает первым символом, читает t[11] и падает с IndexError; образец bra расходится сразу, и ошибка молча проходит тест.

Второе: перекрывающиеся вхождения. После находки хочется прыгнуть сразу на m символов вперёд. В тексте abababababab образец abab входит пять раз - с позиций 0, 2, 4, 6, 8, - а прыжок на m найдёт три. Встроенный "abababababab".count("abab") возвращает именно 3: он считает вхождения без перекрытий, и это записано в его описании.

Третье: срез вместо цикла. Строка if t[i:i + m] == p короче, но не дешевле: срез копирует m символов, сравнение читает их ещё раз. Цена m на позицию платится всегда, даже там, где цикл с break остановился бы на первом символе. Квадрат спрятан в одну строку, а не убран.

Четвёртое: пустой образец. При m = 0 условие j == m истинно сразу, и программа честно сообщает n + 1 вхождений. Обычно это не то, чего ждал вызывающий код, - проверку на пустой образец ставят до поиска.

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

Первый сюжет - честная оценка. Короткий образец, обычный текст, несколько мегабайт: наивный цикл отработает за линейное время, и городить сложный алгоритм незачем. Таблица с k / (k − 1) - аргумент в таком разговоре.

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

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

Теперь сам

Текст - двенадцать букв a. Сколько сравнений сделает наивный поиск для образца aab и сколько для образца baa? Вхождений нет ни у одного.