Конспект: контекстное моделирование, BWT и словарные методы

Понятия

LZ78 - разбиение текста на фразы «фраза из словаря плюс символ»; на выходе пары «номер, символ». LZW - вариант, где словарь заранее содержит все одиночные символы и на выходе одни номера.

Контекст порядка k - k символов перед текущим. Контекстная модель - для каждого контекста счётчики того, что шло после него.

PPM - контекстная модель с выходом: если в непустой таблице символа не было, кодируется выход к более короткому контексту. Пустую таблицу проходят бесплатно.

BWT - последний столбец отсортированной таблицы циклических сдвигов текста с символом конца. LF-отображение - соответствие «k-е вхождение символа в последнем столбце = k-е в первом».

MTF - замена символа его номером в списке с переносом символа в начало списка.

Что унести

LZW
упаковка:    w = самая длинная фраза словаря в начале непрочитанного
             выдать номер w;  добавить в словарь w + следующий символ
распаковка:  выписать фразу кода;  добавить «предыдущая фраза + первый символ текущей»
ОСОБЫЙ СЛУЧАЙ: код равен следующему свободному индексу
    фраза = предыдущая + её первый символ
прочий неизвестный код - повреждение, а не этот особый случай

abababab  (a = 0, b = 1)  →  0 1 2 4 1        код 4 выдан сразу после создания
aaaaaaa   (a = 0)         →  0 1 2 0

Тысяча a кодируется одной ссылкой в учебной модели LZ77 с перекрытием и без ограничения длины ссылки. В реальном формате ограничение длины может потребовать нескольких ссылок. Длины последовательных фраз LZW не обязаны расти.

КОНТЕКСТНАЯ МОДЕЛЬ: цена символа
в контексте учтено n символов, разных d, нужный встречался c раз
c > 0:   доля c / (n + d),   цена log₂((n + d) / c) бит
n > 0 и c = 0: выход с долей d / (n + d)
    перейти к более короткому контексту, складывая цены
n = 0: бесплатно перейти к более короткому контексту
после символа обновить счётчики ВСЕХ порядков - обе стороны одинаково

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

BWT:  banana$  →  annb$aa
bwt[i] = t[sa[i] − 1]                    символ ПЕРЕД суффиксом; длина не меняется

обратно:  первый столбец = отсортированный последний
          lf[i] = начало блока символа L[i] в первом столбце + сколько таких уже встретилось в L
          начать со строки 0;  выписывать L[строка];  строка = lf[строка];  n − 1 раз
          выписано от конца к началу - развернуть

MTF:  aaabbbccc → 0 0 0 1 0 0 2 0 0       серия из k символов → число и k − 1 нулей

ИЗ ЧЕГО СОБРАНЫ АРХИВАТОРЫ
gzip     LZ77 (32 КБ) → Хаффман
zstd     LZ77 (мегабайты) → Хаффман и ANS
xz       LZ77 (мегабайты) → контекстная модель битов → кодирование диапазона
bzip2    серии → BWT блоками → MTF → серии нулей → Хаффман
7-Zip    умеет PPMd - контекстную модель с арифметическим кодированием

Ловушки джокера

Распаковщик LZW без особого случая. Падает на aaa… и ababab… - на самых сжимаемых данных.

Ширина кода переключена не на том коде. Распаковщик отстаёт на фразу; ошибка на единицу.

Словарь LZW без предела. Формат задаёт предел и правило сброса; стороны обязаны совпадать.

Нулевая доля в модели. Невиданный символ обязан иметь ненулевую долю - через выход.

Энтропия по готовым таблицам высокого порядка. 78 бит вместо 672: не посчитаны сами таблицы.

Случайные данные в показанном замере. Старшие порядки увеличили цену; это результат конкретного опыта, а не запрет короткого описания отдельной последовательности.

Символ конца в BWT не наименьший или не единственный. Обход стартует не с той строки.

BWT сортировкой строк таблицы. Квадратичная память. Строить через суффиксный массив.

Обратный BWT сортировкой. 811 415 шагов вместо 2280 на 111 символах.

Хаффман сразу после BWT. Частоты те же, выигрыш ноль. Между ними MTF.

MTF без BWT. В данном журнале 3,98 бита вместо 4,34; на готовых длинных сериях MTF может дать выигрыш и без BWT.

Разный начальный список MTF у сторон. Другой текст на выходе, без единой ошибки.

Выбор архиватора по одной цифре. Смотреть три: размер, упаковка, распаковка.

Куда это ведёт

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