LZ78 и LZW: словарь, который обе стороны строят одинаково

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

Как думаешь, ошибся ли упаковщик

Словарь из двух записей: a - номер 0, b - номер 1. Упаковщик LZW сжал строку abababab и выдал пять кодов: 0 1 2 4 1.

Распаковщик читает их по порядку и пополняет свой словарь. Когда он доходит до четвёртого кода, в его словаре записи с номерами от 0 до 3. А код - 4. Прежде чем читать дальше, реши: упаковщик ошибся? Или распаковщик может понять, что это за фраза, которой у него ещё нет?

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

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

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

Механизм: фразы, коды и пополнение словаря

LZ78 (Лемпель и Зив, 1978) режет текст на фразы: каждая новая фраза - это самая длинная фраза, которая уже есть в словаре, плюс один следующий символ. На выход идёт пара «номер старой фразы, символ», а новая фраза получает следующий номер. Вначале в словаре одна пустая фраза с номером 0, и строка abababab превращается в пары (0, a), (0, b), (1, b), (3, a) и остаток - фразу номер 2 без символа: текст кончился.

LZW (Уэлч, 1984) убирает из пары символ. Словарь заранее заполнен всеми одиночными символами, поэтому любой символ уже фраза, и на выход идут одни номера. Правило упаковщика:

w - самая длинная фраза из словаря, совпадающая с началом непрочитанного текста
выдать номер w
добавить в словарь фразу «w + следующий символ» под следующим свободным номером
продолжить С ЭТОГО ЖЕ следующего символа: в словарь он записан, но на выход ещё не выдан

Проход по abababab, в словаре сначала a = 0, b = 1:

непрочитанное     w      выдан код     новая фраза
abababab          a          0          ab   = 2
bababab           b          1          ba   = 3
ababab            ab         2          aba  = 4
abab              aba        4          abab = 5
b                 b          1          -

Пять кодов на восемь символов. Новая словарная фраза длиннее текущей выданной на один символ, но длины выдаваемых фраз не обязаны расти: здесь aba сменяется на b.

Правило

Упаковщик LZW выдаёт номер самой длинной фразы словаря, с которой начинается непрочитанный текст, и добавляет в словарь эту фразу плюс следующий символ. Распаковщик, получив код, выписывает его фразу и добавляет в словарь «предыдущая фраза плюс первый символ текущей». Если пришёл код, которого в словаре ещё нет, - это может быть только фраза, добавленная упаковщиком на предыдущем шаге, и она равна «предыдущая фраза плюс её собственный первый символ».

Разбор: упаковщик и распаковщик

def lzw(s, alf):
    slovar = {}
    for c in alf:
        slovar[c] = len(slovar)       # одиночные символы: номера 0, 1, 2, …
    kody = []
    w = ""
    for c in s:
        if w + c in slovar:
            w = w + c                 # фраза ещё растёт
        else:
            kody.append(slovar[w])
            slovar[w + c] = len(slovar)
            w = c
    if w != "":
        kody.append(slovar[w])
    return kody

def obratno_lzw(kody, alf):
    if not kody:
        return ""
    slova = []
    for c in alf:
        slova.append(c)
    if not 0 <= kody[0] < len(slova):
        raise ValueError("неверный первый код LZW")
    pred = slova[kody[0]]
    out = [pred]
    i = 1
    while i < len(kody):
        k = kody[i]
        if 0 <= k < len(slova):
            tek = slova[k]
        elif k == len(slova):
            tek = pred + pred[0]      # кода ещё нет: фраза, добавленная шаг назад
        else:
            raise ValueError("неверный код LZW")
        out.append(tek)
        slova.append(pred + tek[0])   # то, что упаковщик добавил, выдав pred
        pred = tek
        i = i + 1
    return "".join(out)

print(lzw("abababab", ["a", "b"]))    # [0, 1, 2, 4, 1]

Распаковка кодов 0 1 2 4 1:

код    фраза     добавлено в словарь        в словаре к этому моменту
 0     a         -                          a, b
 1     b         ab  = 2                    a, b, ab
 2     ab        ba  = 3                    a, b, ab, ba
 4     ?         номера 4 ещё нет

Ответ на вопрос из начала урока. Упаковщик не ошибся. Он выдал код 2 (фраза ab) и в тот же момент завёл фразу 4 - ab плюс следующий символ. А следующим кодом выдал эту самую фразу 4. Значит, фраза 4 начинается с ab и её первый символ - a; но «следующий символ после ab» - это и есть первый символ фразы 4. Получается ab + a = aba. Распаковщик восстанавливает фразу из того, что у него уже есть: предыдущая фраза плюс её первый символ.

Особый случай разрешён только для следующего свободного номера k==len(slova). Более далёкий номер не мог появиться у согласованного кодировщика; отрицательный номер тоже неверен. Декодер отклоняет такие данные через ValueError, а пустой поток восстанавливает в пустую строку. Это отделяет задержку словаря на один шаг от действительно повреждённого потока.

 4     aba       aba  = 4                   …, aba
 1     b         abab = 5                   …, abab

Выписано a, b, ab, aba, b - исходные восемь символов.

Разбор: замер и сравнение с LZ77

Начальный словарь в каждой строке - разные символы самого текста, по алфавиту.

текст                     символов    кодов LZW    фраз в словаре
abababab                       8           5              6
abracadabra                   11           9             13
"abracadabra " * 10          120          42             47
zhurnal из прошлой главы     826         236            261
tekst(1000, 4, 1)           1000         328            331
"a" * 1000                  1000          45             45

Последняя строка показывает характер метода. Первые полные фразы для тысячи букв a имеют длины 1,2,…,44 и покрывают 990 символов. Оставшиеся 10 символов дают последний, сорок пятый код: длина последней фразы меньше предыдущей. Число кодов для n одинаковых символов имеет порядок √n, точнее около √(2n). В модели LZ77 с перекрытием и без ограничения длины ссылки эту строку можно записать одним литералом и одной ссылкой. У конкретного формата есть пределы длины и окна; тогда длинный повтор приходится разбивать на несколько ссылок.

Журнал: 236 кодов против 65 единиц у LZ77. При фиксированной ширине кодов словарь в 261 фразу требует 9 бит на код: 2124 бита против примерно 900 в сравнении урока. Изменяемая по ходу потока ширина дала бы другой подсчёт. На коротком тексте словарь не успевает вырасти. DEFLATE использует LZ77, а LZW встречается в GIF и TIFF.

                        LZ77                           LZ78 и LZW
на что ссылка           расстояние назад и длина       номер фразы в словаре
что служит словарём     окно уже прочитанного текста   отдельная таблица фраз
как растёт фраза        любая длина сразу              на один символ за использование
забывание               старое выезжает из окна        словарь полон - сброс или заморозка

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

Первое: особый случай не обработан. Распаковщик без ветки «кода ещё нет» падает на первой же строке с повтором вида aaa… или ababab… - то есть на самых сжимаемых данных. На тексте без таких повторов он работает, и ошибка переживает тесты.

Второе: ширина кода переключается не в тот момент. Коды пишут переменной шириной: 9 бит, пока в словаре меньше 512 фраз, потом 10 и так далее. Упаковщик и распаковщик обязаны переключиться на одном и том же коде. Распаковщик отстаёт на фразу, и ошибка на единицу здесь - классика: в форматах TIFF и PDF для неё даже есть параметр «раннее переключение», потому что разные программы поняли момент по-разному.

Третье: словарь растёт без предела. Каждая фраза - запись в таблице. Формат ограничивает число фраз (в GIF - 4096, коды до 12 бит), и на заполнении словарь либо сбрасывают особым кодом, либо перестают пополнять. Обе стороны должны поступать одинаково.

Четвёртое: начальный словарь не согласован. Если упаковщик начал с 256 байтов, а распаковщик - с алфавита текста, первые же коды означают разное.

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

Первый сюжет - старые форматы, которые живы. Картинки GIF, утилита compress и файлы .Z, часть файлов TIFF и потоков внутри PDF сжаты LZW. Чтобы прочитать их или понять, почему файл «битый», нужно знать ровно этот алгоритм.

Второй - урок истории. Патенты на LZW повлияли на выбор алгоритмов в форматах. Утилита gzip появилась в 1992 году как замена Unix compress, избегающая патентных ограничений его LZW. Позднее спор вокруг GIF способствовал созданию PNG в 1994 году. И gzip, и PNG используют DEFLATE, сочетающий LZ77 с кодированием Хаффмана. Это разные этапы истории, а не один ответ на спор вокруг GIF. Хронологию подтверждают описание gzip и справка W3C о PNG.

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

Теперь сам

Закодируй LZW строку из семи букв a; в словаре сначала одна запись, a = 0. Затем распакуй полученные коды и скажи, сколько раз сработал особый случай.

непрочитанное     w       выдан код     новая фраза
aaaaaaa           a           0          aa   = 1
aaaaaa            aa          1          aaa  = 2
aaaa              aaa         2          aaaa = 3
a                 a           0          -