Контекстное моделирование: угадать символ по предыдущим

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

Как думаешь, сколько бит стоит угаданный символ

Перед тобой начало строки журнала: GET /api/user. Какой символ следующий? Ты ответишь s раньше, чем дочитаешь вопрос.

Частотная модель из прошлой главы этого не знает. Буква s для неё - один из двадцати шести символов журнала с долей около семи процентов, и стоит она почти четыре бита. Прежде чем читать дальше, подумай: сколько бит ДОЛЖЕН стоить символ, который угадывается наверняка? И что нужно хранить, чтобы программа угадывала так же, как ты?

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

Представь игру. Ведущий задумал текст и открывает его по букве. Перед каждой буквой ты называешь свою догадку; если ошибся - называешь следующую, пока не угадаешь. Ведущий записывает не буквы, а число попыток.

Для осмысленного текста запись будет почти сплошь из единиц: большинство букв угадываются с первой попытки. Второй игрок, который угадывает точно так же, как ты, восстановит текст по этим числам. Вся информация о тексте - в редких местах, где угадать не удалось. Этот опыт в 1951 году поставил Клод Шеннон и получил около одного бита на букву английского текста вместо привычных пяти.

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

Механизм: счётчики по контекстам и выход

Контекст порядка k - это k символов, стоящих перед текущим. Контекстная модель хранит для каждого встретившегося контекста таблицу: какой символ сколько раз шёл после него.

Таблицы порядка 2 для слова abracadabra:

контекст    что шло после       контекст    что шло после
   ab       r - 2 раза             ca       d - 1 раз
   br       a - 2 раза             ad       a - 1 раз
   ra       c - 1 раз              da       b - 1 раз
   ac       a - 1 раз

После ab оба раза шла r. Модель, увидев ab, отдаёт r большую часть доли, и арифметический кодировщик из прошлой главы потратит на неё log₂(1/доля) бит - меньше бита, а когда таких встреч накопятся десятки, малую часть бита.

Модель адаптивная: счётчики начинаются с нуля и обновляются после каждого символа. Распаковщик ведёт те же счётчики по уже распакованному тексту, поэтому таблицы передавать не нужно - тот же принцип, что у словаря LZW.

Отсюда трудность. Пришёл символ, которого в этом контексте ещё не было. Его счётчик - ноль, доля - ноль, а log₂(1/0) - бесконечность. Давать нулевую долю нельзя ничему, что может встретиться.

PPM (предсказание по частичному совпадению) решает это так. В каждой непустой таблице этой модели есть особый исход - выход: «символа здесь нет». Его доля тем больше, чем больше разных символов уже видел этот контекст: выход считается ещё одним исходом, который «встретился» по разу на каждый символ, впервые появившийся здесь. Если в непустой таблице символ не найден, кодируется выход, и модель переходит к контексту на символ короче: от трёх предыдущих к двум, от двух к одному, потом к простым частотам, и в самом конце - к таблице, где все 256 значений байта равноправны и символ стоит log₂ 256 = 8 бит.

Правило

Пусть в текущем контексте всего учтено n символов, из них d разных, а нужный символ встречался c раз. Если c > 0, его доля c / (n + d) и цена log₂((n + d) / c) бит. Если c = 0 и n > 0, кодируется выход с долей d / (n + d), и поиск повторяется в контексте на символ короче; цены складываются. Сумма всех счётчиков равна n, выходу отдано d - поэтому в знаменателе n + d, и все доли вместе дают единицу. Контекст, который не встречался ни разу, проходится бесплатно: распаковщик видит ту же пустую таблицу. После символа обновляются счётчики всех порядков. Длинный контекст может дать более точное предсказание, но встречается реже, и на нём чаще приходится платить за выход - поэтому у порядка есть оптимум, и он зависит от данных.

Разбор: программа, которая считает цену

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

from math import log2

def cena_ppm(s, poryadok):
    schet = {}                        # контекст -> {символ: сколько раз шёл после}
    bit = 0.0
    i = 0
    while i < len(s):
        k = min(poryadok, i)
        while True:
            if k < 0:
                bit = bit + 8         # символ не встречался нигде: байт как есть
                break
            tabl = schet.get(s[i - k:i], {})
            n = sum(tabl.values())
            d = len(tabl)
            if s[i] in tabl:
                bit = bit + log2((n + d) / tabl[s[i]])
                break
            if n > 0:
                bit = bit + log2((n + d) / d)     # цена выхода
            k = k - 1                 # контекст на символ короче
        k = min(poryadok, i)
        while k >= 0:                 # обновляем счётчики всех порядков
            tabl = schet.setdefault(s[i - k:i], {})   # взять таблицу, а нет - завести пустую
            tabl[s[i]] = tabl.get(s[i], 0) + 1
            k = k - 1
        i = i + 1
    return bit

Контекст порядка 0 - пустая строка: s[i:i]. Его таблица - обычные частоты символов.

Текст - zhurnal из урока про LZ77: сорок строк, 826 символов, 6608 бит без сжатия.

порядок     бит       на символ
   0       3 852        4,66
   1       1 180        1,43
   2         683        0,83
   3         688        0,83
   4         672        0,81
   5         687        0,83
   6         701        0,85

Ответ на вопрос из начала урока. Символ, угаданный наверняка, должен стоить почти ноль, и он столько и стоит: при порядке 4 на символ в среднем уходит 0,81 бита, а вся цена сосредоточена в первых строках, пока модель ещё не видела путей, и в том месте каждой строки, где путь действительно выбирается.

Один шаг с порядка 0 на порядок 1 - сжатие втрое. Дальше выигрыш быстро кончается: порядки от 2 до 5 дают почти одно и то же, от 672 до 688 бит, а к порядку 6 цена уже заметно растёт.

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

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

Журнал в десять раз длиннее - тот же генератор, но 400 строк вместо 40, 8182 символа, - и случайный текст из четырёх букв:

порядок     журнал, 400 строк     tekst(1000, 4, 1)
   0             36 387                2 067
   1              7 090                2 163
   2              2 008                2 407
   4              1 584                3 212
   6              1 633                3 473

Левый столбец повторяет форму первой таблицы: лучший порядок - 4, дальше хуже. Длинных контекстов много, каждый встречается редко. За выход платят на тех порядках, где таблица уже непуста, но нужного символа ещё нет; пустые таблицы проходятся бесплатно. Модель дробит статистику мельче, чем хватает данных.

Правый столбец показывает другой результат: в этом опыте цена выросла с 2067 до 3473 бит. Для источника с четырьмя равновероятными независимыми символами энтропия равна двум битам на символ: знание прошлого не уменьшает её. Это нижняя граница средней длины однозначно декодируемого кода такого источника, а не запрет короткого описания отдельного конечного текста. Наш генератор детерминирован, поэтому сам этот опыт не доказывает независимость символов и не устанавливает абсолютную границу для данной последовательности.

И одна ловушка в самом замере. Если построить таблицы порядка 4 заранее по всему тексту и взять для каждой позиции log₂(n / c) без всякого выхода, получится 78 бит вместо 672. Число верное и бесполезное: оно не включает сами таблицы, которые распаковщику надо как-то передать. При длинном контексте таблицы просто запоминают текст. Честная цена - адаптивная: модель платит за всё, чего ещё не знает.

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

Первое: нулевая доля. Модель без выхода присваивает невиданному символу долю ноль. Кодировщик делит на ноль или сужает отрезок до пустого - сообщение потеряно. Каждый исход, который может встретиться, обязан иметь ненулевую долю.

Второе: память. Число контекстов растёт с порядком: до 826 · 5 таблиц для нашего журнала при порядке 4, миллионы - для мегабайтного файла. Рабочие реализации ограничивают память и, заполнив её, сбрасывают модель или её часть.

Третье: скорость в обе стороны. Каждый символ - несколько обращений к таблицам и шаг арифметического кодировщика. Распаковщик тоже поддерживает модель. У LZ77 восстановление совпадения сводится к копированию; у показанной контекстной модели обе стороны обновляют таблицы. Это объясняет разную работу алгоритмов, но не задаёт универсального отношения скоростей: его измеряют для конкретных реализаций и данных.

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

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

Нужно хранить журналы сервиса и быстро открывать нужный день при расследовании сбоя. Повторяющиеся маршруты и поля могут помочь контекстной модели, но сами по себе не обещают выигрыш над методом со ссылками на повторы. Возьми одинаковую выборку журналов и измерь размер, время упаковки и время восстановления. Если данные читаются часто, меньший архив не обязательно окупит медленную распаковку.

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

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

Теперь сам

В контексте th модель видела: e - 6 раз, a - 2 раза. Посчитай цену символа e в этом контексте. Затем - сколько бит добавит этот контекст, если следующим пришёл символ i, которого здесь ещё не было. Нужные значения: log₂(10/6) ≈ 0,74, log₂ 5 ≈ 2,32.