LZ77: ссылка назад вместо повтора

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

Как думаешь, что запишет ссылка длиннее расстояния

Правило записи: либо символ как есть, либо пара «назад, длина» - отойти на назад символов от конца уже распакованного и скопировать длина символов.

Распакованный текст пока состоит из одной буквы a. Дальше стоит пара «назад 1, длина 9». Прежде чем читать дальше, подумай: позади всего один символ, а скопировать велено девять. Это ошибка в записи? Или у такой пары есть смысл - и тогда что получится?

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

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

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

Механизм: окно, символы и ссылки

LZ77 (Лемпель и Зив, 1977) идёт по тексту слева направо. В каждой позиции он ищет в окне - последних W символах уже обработанного текста - самый длинный кусок, совпадающий с тем, что стоит дальше. Нашёл достаточно длинный - пишет ссылку (назад, длина) и перепрыгивает через весь кусок. Не нашёл - пишет один символ как есть (такой символ называют литералом) и сдвигается на единицу.

текст       a b r a c a d a b r a
позиция     0 1 2 3 4 5 6 7 8 9 10

позиции 0-6:   a  b  r  a  c  a  d         семь символов как есть: кусков длиной 3 и больше позади нет
позиция 7:     дальше стоит abra; оно же стоит с позиции 0, это 7 символов назад
               → ссылка (назад 7, длина 4)

запись:   a  b  r  a  c  a  d  (7, 4)       8 единиц вместо 11 символов

Короткие совпадения ссылкой не заменяют: ссылка сама занимает место, и на один-два символа она дороже литералов. В этом уроке порог - три символа, как в распространённом формате deflate.

Распаковка зеркальна и проще: символ - дописать; ссылка - отойти назад и скопировать.

Правило

Запись LZ77 - последовательность литералов и ссылок (назад, длина). Ссылка означает: взять символ, стоящий в уже распакованном тексте на назад позиций от конца, дописать его в конец, и повторить это длина раз. Копирование идёт ПО ОДНОМУ СИМВОЛУ, поэтому длина может быть больше расстояния: только что дописанные символы сами становятся источником. Сжатие ограничено окном: повтор, отстоящий дальше W символов, не будет найден.

Разбор: распаковка и перекрытие

def raspakovat(zapis):
    out = []
    for z in zapis:
        if len(z) == 1:
            out.append(z[0])                      # литерал: [символ]
        else:
            nazad = z[0]                          # ссылка: [назад, длина]
            dlina = z[1]
            k = 0
            while k < dlina:
                out.append(out[len(out) - nazad]) # по одному символу
                k = k + 1
    return "".join(out)

print(raspakovat([["a"], [1, 9]]))                # aaaaaaaaaa
print(raspakovat([["a"], ["b"], [2, 6]]))         # abababab

Ответ на вопрос из начала урока. Пара «назад 1, длина 9» после одной буквы a - не ошибка. Первый шаг копирует символ на одну позицию от конца, это a; теперь в тексте aa. Второй шаг снова берёт символ на одну позицию от конца - это a, дописанная только что. И так девять раз. Ссылка догоняет собственный хвост, и получается серия: десять букв a записаны двумя единицами. LZ77 умеет то же, что RLE, не имея для серий отдельного правила.

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

Разбор: упаковка и замер

Упаковщик ищет самое длинное совпадение перебором всех начал в окне. Это медленно, зато читается как определение:

def upakovat(s, okno):
    zapis = []
    i = 0
    while i < len(s):
        luchshaya = 0
        gde = 0
        j = max(0, i - okno)
        while j < i:                              # все начала в окне
            d = 0
            while i + d < len(s) and s[j + d] == s[i + d]:
                d = d + 1                         # j + d может зайти за i - это перекрытие
            if d >= luchshaya and d > 0:
                luchshaya = d
                gde = i - j                       # при равной длине - ближняя ссылка
            j = j + 1
        if luchshaya >= 3:
            zapis.append([gde, luchshaya])
            i = i + luchshaya
        else:
            zapis.append([s[i]])
            i = i + 1
    return zapis

Для замера нужен текст, похожий на настоящий. Вот журнал из сорока строк с четырьмя разными путями:

puti = ["/index.html", "/api/users", "/api/orders", "/static/app.js"]
stroki = []
s = 7
i = 0
while i < 40:
    s = (s * 75 + 74) % 65537
    stroki.append("GET " + puti[s % 4] + " 200\n")
    i = i + 1
zhurnal = "".join(stroki)                         # 826 символов

Замер с окном 4096. Чтобы сравнивать размеры, примем грубую цену: литерал - 9 бит (бит-признак «это литерал» и байт), ссылка - 24 бита (бит-признак, 12 бит расстояния, 11 бит длины). Исходный текст - 8 бит на символ.

текст                                 символов   литералов   ссылок     бит     было бит
abracadabra                               11          7          1        87         88
"abracadabra " * 10                      120          8          2       120        960
zhurnal                                  826         44         21       900      6 608
tekst(1000, 4, 1)                       1000         40        228     5 832      8 000
tekst(1000, 26, 1)                      1000        943         19     8 943      8 000

В журнале первые строки идут литералами, дальше - длинные ссылки: одна ссылка накрывает целую строку журнала, а то и две-три подряд, если такая же последовательность строк уже встречалась. Сжатие в семь раз, и это на данных, энтропия которых по частотам символов - 3578 бит: LZ77 видит повторы КУСКОВ, а подсчёт частот - нет.

Последняя строка - обратная сторона. В случайном тексте из 26 букв кусков длиной три, которые уже встречались, почти нет, и запись вышла ДЛИННЕЕ исходной: каждый литерал несёт лишний бит признака.

Настоящие упаковщики не перебирают окно. Они держат хеш-таблицу «три символа → где они встречались раньше» и смотрят только на эти места. Формат записи от этого не меняется: распаковщику всё равно, как упаковщик искал совпадения.

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

Первое: копирование срезом. Строка out = out + out[nach:nach + dlina], где nach = len(out) - nazad, выглядит как то же самое, но срез берётся из текста, каким он был ДО копирования. Для ссылки (1, 9) срез содержит одну букву, и в тексте окажутся две a вместо десяти. Ошибка проявляется только на перекрывающихся ссылках, то есть как раз на сериях.

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

Третье: окно меньше расстояния между повторами. Формат deflate, на котором работают gzip и zip, видит 32 килобайта назад. Два одинаковых файла по мегабайту, склеенные вместе, он сожмёт так, будто они разные: второй экземпляр начинается за пределами окна. Архиваторы с окном в мегабайты такой повтор находят.

Четвёртое: распаковка без предела. Две единицы записи дали десять символов; тем же приёмом несколько килобайт архива разворачиваются в гигабайты. Это известная атака - «архивная бомба». Программа, которая распаковывает чужие данные, обязана ограничивать размер результата.

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

Первый сюжет - почти всё, что сжато вокруг. Форматы gzip, zip и PNG используют deflate: LZ77 с окном 32 килобайта, после которого литералы, длины и расстояния кодируются кодом Хаффмана - частые значения короче. Сжатие веб-страниц, пакеты программ, образы систем - это потомки той же схемы с большим окном и более точным кодированием: zstd, brotli, xz.

Второй - выбор уровня сжатия. Формат один, а упаковщик может искать совпадения быстро и небрежно или долго и тщательно. Уровни от 1 до 9 в gzip - это не разные алгоритмы, а разная настойчивость поиска. Распаковка при этом одинаково быстра для всех уровней, поэтому то, что упаковывается один раз, а читается миллионы раз, выгодно жать на максимуме.

Третий - понимание, что сжимается хорошо. Журналы, код, таблицы в текстовом виде полны повторяющихся кусков - LZ77 в своей стихии. Уже сжатые картинки и зашифрованные данные повторов не содержат, и на них любой архиватор этого семейства бесполезен.

Теперь сам

Распакуй запись x, y, z, (3, 5), w, (9, 2). Затем скажи, что получится из q, (1, 4), если копировать срезом, как в первой ошибке из списка.

xyz      → x  (третий от конца)     xyzx
xyzx     → y                        xyzxy
xyzxy    → z                        xyzxyz
xyzxyz   → x                        xyzxyzx
xyzxyzx  → y                        xyzxyzxy