Z-функция: те же знания, записанные от начала строки

Коротко

Z-функция строки - список чисел: z[i] равно числу символов, на которое кусок строки с позиции i совпадает с её началом. Для abracadabra это 0 0 0 1 0 1 0 4 0 0 1. Считается за линейное время благодаря одному наблюдению: если кусок [l, r) уже совпал с началом, то про позиции внутри него всё известно из ранее посчитанных значений. Поиск подстроки сводится к Z-функции склейки образец + "#" + текст: вхождения там, где z равно длине образца. Замер на строке из тысячи букв a: по определению 499 500 сравнений, с этим наблюдением - 999.

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

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

Строка - тысяча букв a. Для каждой позиции надо узнать, на сколько символов кусок, начинающийся с неё, совпадает с началом строки. Ответ для позиции i очевиден: 1000 − i, до самого конца.

Если считать по определению - прикладывать начало строки к каждой позиции и сравнивать, пока совпадает, - выйдет 999 + 998 + … + 1 = 499 500 сравнений. Прежде чем читать дальше, прикинь: сколько сравнений действительно необходимо, чтобы заполнить весь список? И что именно нужно запомнить, чтобы не сравнивать лишнего?

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

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

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

Механизм: Z-блок и три случая

индекс    0  1  2  3  4  5  6  7  8  9  10
строка    a  b  r  a  c  a  d  a  b  r  a
z         0  0  0  1  0  1  0  4  0  0  1

z[7] = 4:  с позиции 7 стоит abra - это первые четыре символа строки

Значение z[0] по определению равнялось бы длине всей строки; его принято писать нулём, оно нигде не используется.

Z-блок - это кусок [l, r), про который уже известно, что он совпадает с началом строки, причём из всех таких выбран тот, что кончается правее всех. Символ с индексом r в блок не входит.

Пусть мы считаем z[i], и i попало внутрь блока. Блок - копия начала, значит позиция i в нём соответствует позиции i − l в начале, а про неё значение z[i − l] уже посчитано. До правого края блока от i остаётся r − i символов.

случай 1:  i >= r                 про i ничего не известно: сравниваем с нуля
случай 2:  z[i − l] < r − i       совпадение кончается внутри блока: z[i] = z[i − l];
                                  одно сравнение только подтверждает, что дальше не совпадает
случай 3:  z[i − l] >= r − i      до края блока совпадает точно; что за краем - неизвестно:
                                  начинаем с r − i и сравниваем дальше символ за символом

Все три случая укладываются в одну строку: начальное значение min(r − i, z[i − l]), потом попытка продлить сравнениями. Во втором случае продление сразу упирается в расхождение. В третьем каждое успешное сравнение сдвигает край r вправо.

Правило

Для позиции i внутри Z-блока [l, r) значение z[i] не меньше min(r − i, z[i − l]): начинать сравнение можно с этого числа, а не с нуля. Если после продления i + z[i] оказалось правее r, блоком становится [i, i + z[i]). Успешное сравнение всегда сдвигает r вправо, а r не может превысить n, поэтому успешных сравнений не больше n; неуспешных не больше одного на позицию. Всего не больше 2n.

Разбор: программа и проход по abacaba

def zf(s):
    n = len(s)
    z = [0] * n
    l = 0
    r = 0
    sravn = 0
    i = 1
    while i < n:
        if i < r:
            z[i] = min(r - i, z[i - l])       # то, что известно из блока
        while i + z[i] < n:
            sravn = sravn + 1
            if s[z[i]] != s[i + z[i]]:
                break
            z[i] = z[i] + 1                   # продлили на символ
        if i + z[i] > r:
            l = i                             # новый блок кончается правее
            r = i + z[i]
        i = i + 1
    return [z, sravn]

print(zf("abacaba"))                          # [[0, 0, 1, 0, 3, 0, 1], 8]

i   блок до    начальное z[i]            сравнения                    z[i]   блок после
1   пусто           0                    b ≠ a                          0     пусто
2   пусто           0                    a = a,  c ≠ b                  1     [2, 3)
3   [2, 3)          0  (i вне блока)     c ≠ a                          0     [2, 3)
4   [2, 3)          0  (i вне блока)     a = a, b = b, a = a, конец     3     [4, 7)
5   [4, 7)     min(2, z[1]) = 0          b ≠ a                          0     [4, 7)
6   [4, 7)     min(1, z[2]) = 1          нет: i + z[i] = 7 = n          1     [4, 7)

Строка i = 6 - тот самый выигрыш: значение взято из z[2] готовым, ни одного сравнения. Строка i = 5 - второй случай: z[1] = 0 меньше расстояния до края, и единственное сравнение только подтверждает ноль. Всего восемь сравнений; по определению было бы девять. На семи символах разница в одно сравнение, на длинных повторах - на порядки.

Разбор: замер и поиск через склейку

строка          по определению    с Z-блоком
"a" * 100             4 950            99
"a" * 1000          499 500           999
"a" * 2000        1 999 000         1 999
"ab" * 500          250 000         1 498

Ответ на вопрос из начала урока: 999 сравнений. На позиции 1 программа честно сравнивает до конца строки - 999 успешных сравнений - и получает блок [1, 1000). Для всех остальных позиций значение берётся из блока готовым: min(1000 − i, z[i − 1]), и продлевать некуда - строка кончилась.

Теперь поиск. Склеим образец, разделитель и текст в одну строку:

def poisk_z(t, p):
    s = p + "#" + t
    z = zf(s)[0]
    m = len(p)
    nashli = 0
    i = m + 1                         # первая позиция текста внутри склейки
    while i < len(s):
        if z[i] == m:
            nashli = nashli + 1       # в тексте это позиция i - m - 1
        i = i + 1
    return nashli

Начало склейки - это образец. Значит z[i] = m на позиции текста означает ровно одно: с этого места стоит образец целиком. Разделитель # - символ, которого нет ни в образце, ни в тексте; на нём любое совпадение обрывается, поэтому z не бывает больше m.

Цена на худших данных для наивного поиска - текст "a" * 1000, образец "a" * 9 + "b": 2009 сравнений, из них 18 уходит на часть «образец и разделитель» и 1991 - на текст. У наивного было 9910. У КМП по тексту те же 1991 сравнение; подготовку образца его счётчик не считал. Z-функция и префикс-функция несут одно и то же знание и стоят одинаково; одну можно пересчитать в другую за линейное время.

Различие в том, с какой стороны записан ответ. π[i] смотрит назад: сколько символов ПЕРЕД позицией i включительно совпадают с началом. z[i] смотрит вперёд: сколько символов НАЧИНАЯ с позиции i совпадают с началом. Вопрос «на сколько символов образец совпадает с текстом, если приложить его вот сюда» - это дословно z, и там, где нужен именно он, Z-функция удобнее.

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

Первое: минимум забыт. Если написать z[i] = z[i − l] без min, значение может вылезти за край блока - туда, где про строку ничего не известно. Строка aaa: правильный ответ 0 2 1, без минимума выходит 0 2 2 - на позиции 2 записано совпадение в два символа, хотя до конца строки остался один. Значение z[i − l] говорит, что было в начале строки; внутри блока это верно и для копии, а за краем блока - уже нет. Продление сравнениями такую ошибку не исправит: оно умеет только увеличивать значение.

Второе: блок не обновляется. Строки l = i и r = i + z[i] можно забыть - ответ останется верным, потому что продление сравнениями всё равно доведёт z[i] до правильного значения. Пропадёт только скорость: на тысяче букв a снова будет 499 500 сравнений. Ошибка, которую не ловит ни один тест на правильность, - только замер.

Третье: разделитель встречается в тексте. Образец ab, текст ab#ab, склейка ab#ab#ab. На позиции 3 совпадение перешагивает через # и даёт z = 5, а проверка z[i] == m ждёт ровно 2 - вхождение потеряно. Либо разделитель гарантированно чужой, либо проверка пишется как z[i] >= m.

Четвёртое: путаница с z[0]. Одни пишут туда ноль, другие длину строки. Программы этого урока z[0] не читают вовсе, но чужая формула, взятая из книги с другой договорённостью, может на него рассчитывать. Смешивать две договорённости в одной программе нельзя.

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

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

Второй - подготовка образца для быстрых алгоритмов. Правило «хорошего суффикса» в алгоритме Бойера-Мура (следующая глава) требует знать для каждой позиции образца, сколько символов перед ней совпадает с его концом. Это Z-функция перевёрнутого образца, и в книге Гасфилда вся теория поиска построена на ней как на основной заготовке.

Третий - сжатие и повторы. Наименьший i, для которого i + z[i] = n и n делится на i, - длина куска, повторением которого составлена вся строка. Так находят, что содержимое файла - это один блок, записанный много раз.

Теперь сам

Посчитай Z-функцию для строки aabaab. Для каких позиций значение получилось без единого успешного сравнения благодаря блоку?

Ответ.

индекс    0  1  2  3  4  5
строка    a  a  b  a  a  b
z         0  1  0  3  1  0

Позиция 1: a = a, затем b ≠ a - единица, блок [1, 2). Позиция 2: b ≠ a - ноль. Позиция 3: aab совпало с началом до самого конца строки - тройка, блок [3, 6).

Позиции 4 и 5 лежат внутри блока [3, 6). Для 4: min(6 − 4, z[1]) = min(2, 1) = 1 - значение взято готовым; одно сравнение (b против a) только подтверждает, что дальше не совпадает. Для 5: min(1, z[2]) = 0, одно неуспешное сравнение. Успешных сравнений на этих двух позициях нет: всё, что совпало, было известно из блока.

Главное

Z-функция хранит для каждой позиции длину совпадения с началом строки, и считается за линейное время потому, что найденное совпадение - это копия начала, а про начало всё уже посчитано. Сравнивать приходится только за правым краем самого дальнего совпадения, и каждый успех двигает этот край вперёд - отсюда 2n. Поиск образца превращается в одну строку: посчитать Z-функцию склейки p + "#" + t и найти значения, равные m. Знание то же, что у префикс-функции; выбор между ними - вопрос удобства формулировки, а не скорости.