После BWT: move-to-front и из чего собраны архиваторы

Если ты применишь MTF к строке bbbaab, объяснишь, почему после BWT нельзя сразу взять код Хаффмана, и назовёшь ступени gzip, bzip2 и xz, - листай до «Теперь сам».

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

BWT превратил журнал в 85 серий: сорок нулей, сорок букв T, потом полоса из s с редкими l, и так далее. Осталось это сжать.

Код Хаффмана считает частоты символов. Прежде чем читать дальше, ответь себе: изменились ли частоты символов после BWT? И если нет - чем тогда текст после BWT лучше исходного для кода Хаффмана? Что надо сделать с сериями, чтобы они превратились в перекошенные частоты?

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

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

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

Механизм: список, который помнит недавнее

Move-to-front (MTF, «переместить в начало») держит список всех символов алфавита. Для каждого символа текста он выдаёт его номер в списке, считая с нуля, и переставляет этот символ на первое место.

список в начале: a b c

символ    номер в списке    список после
  a             0             a b c
  a             0             a b c
  a             0             a b c
  b             1             b a c
  b             0             b a c
  b             0             b a c
  c             2             c b a
  c             0             c b a
  c             0             c b a

aaabbbccc  →  0 0 0 1 0 0 2 0 0

Девять символов трёх видов поровну превратились в семь нулей и два ненулевых числа. А вот тот же набор символов без серий:

abcabcabc  →  0 1 2 2 2 2 2 2 2

Ноль один, в самом начале; дальше каждый символ всякий раз достаётся со дна. MTF ничего не сжимает и на тексте без серий бесполезен. Он переводит «одинаковые символы рядом» в «маленькие числа часты» - а с перекошенными частотами уже справляются код Хаффмана и арифметическое кодирование.

Обратное преобразование ведёт тот же список: по номеру берёт символ и так же переносит его в начало.

Правило

MTF выдаёт для символа его текущий номер в списке и переносит символ в начало списка; обратное преобразование по номеру берёт символ и делает ту же перестановку. Длина не меняется. Серия из k одинаковых символов даёт одно число и k − 1 нулей. BWT частоты символов не меняет; пара «BWT, затем MTF» превращает зависимость символа от соседей в перекос частот чисел, и только после этого работает энтропийное кодирование.

Разбор: программа и замер на журнале

def mtf(s, alf):
    spisok = list(alf)
    nomera = []
    for c in s:
        i = spisok.index(c)
        nomera.append(i)
        spisok.pop(i)
        spisok.insert(0, c)           # символ - в начало
    return nomera

def obratno_mtf(nomera, alf):
    spisok = list(alf)
    out = []
    for i in nomera:
        c = spisok[i]
        out.append(c)
        spisok.pop(i)
        spisok.insert(0, c)
    return "".join(out)

print(mtf("annb$aa", ["$", "a", "b", "n"]))       # [1, 3, 0, 3, 3, 3, 0]

На семи символах banana выигрыша не видно - строка слишком коротка. Журнал из урока про LZ77, с символом конца 827 символов. Начальный список MTF - все разные символы текста в порядке кодов. Энтропия считается по частотам, в битах на символ; после MTF «символами» в формуле служат сами номера:

что измеряем                   журнал, 40 строк      журнал, 400 строк     tekst(1000, 4, 1)
энтропия исходного текста           4,34                  4,40                  2,01
энтропия после BWT                  4,34                  4,40                  2,01
энтропия после BWT и MTF            0,80                  0,35                  2,02
нулей после BWT и MTF           742 из 827           7751 из 8183           270 из 1001
бит при такой энтропии        662 вместо 3589      2830 вместо 35 999      2024 вместо 2011

Ответ на вопрос из начала урока - вторая строка таблицы. После BWT энтропия по частотам та же до третьего знака: символы те же, изменился только порядок, а частотам порядок безразличен. Код Хаффмана сжал бы переставленный текст ровно так же, как исходный.

Третья строка - зачем нужен MTF. Девять символов из десяти стали нулём, и энтропия упала в пять с лишним раз на коротком журнале и почти в тринадцать на длинном. Чем длиннее текст, тем длиннее серии после BWT и тем больше нулей.

Правый столбец - случайный текст: всё осталось как было, 2,01 и 2,02. Нет зависимости между соседями - нет серий после BWT - нет нулей после MTF.

Разбор: из чего собраны архиваторы

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

архиватор    ступени
gzip         LZ77, окно 32 КБ  →  код Хаффмана
zstd         LZ77, окно в мегабайты  →  код Хаффмана для литералов, ANS для ссылок
xz           LZ77, окно в мегабайты  →  контекстная модель битов  →  кодирование диапазона
bzip2        серии  →  BWT блоками до 900 КБ  →  MTF  →  серии нулей  →  код Хаффмана

Первая ступень bzip2 - сжатие длинных серий ещё до BWT - страховка: на блоке из одинаковых символов сортировка была бы слишком медленной.

Замер настоящими программами. Данные - тексты теоретических уроков этого курса, склеенные в один файл: 3,86 МБ. Время - на машине, где собирается сайт; важны не секунды, а их отношения. Для каждой программы - три команды; у остальных ключи те же:

gzip -9 -c uroki.txt | wc -c
time gzip -9 -c uroki.txt > uroki.gz
time gzip -d -c uroki.gz > /dev/null

программа      размер      упаковка    распаковка
gzip -1       1 399 КБ      0,09 с       0,03 с
zstd -3       1 025 КБ      0,05 с       0,02 с
gzip -9         963 КБ      0,61 с       0,03 с
zstd -19        718 КБ      2,52 с       0,03 с
xz -9           697 КБ      2,68 с       0,06 с
bzip2 -9        673 КБ      0,39 с       0,15 с

Что видно. На связном тексте bzip2 сжимает плотнее всех - это типично: BWT учитывает контекст любой длины, а не только повторы кусков. Зато распаковывает он в разы медленнее остальных: обратное преобразование прыгает по всему блоку, а у семейства LZ77 распаковка - копирование подряд.

У zstd и gzip распаковка одинаково быстра на любом уровне сжатия: уровень - это настойчивость упаковщика, формат тот же. Разрыв между zstd -3 и zstd -19 - полсотни раз по времени упаковки и треть по размеру. И zstd -3 быстрее gzip -1 при лучшем сжатии: большое окно и новая энтропийная ступень просто сильнее формата тридцатилетней давности.

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

Первое: Хаффман сразу после BWT. Частоты не изменились, выигрыша ноль. Между ними обязана стоять ступень, превращающая серии в перекос: MTF или кодирование длин серий.

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

Третье: MTF без BWT. На обычном тексте соседние символы разные, и номера выходят большими. Замер на исходном журнале без BWT: энтропия после MTF - 3,98 бита вместо 4,34, почти ничего. MTF - вторая половина пары, отдельно он не работает.

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

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

Первый сюжет - что ставить по умолчанию. Журналы, которые пишутся потоком и изредка читаются: zstd на низком уровне - быстрее gzip и плотнее. Пакеты и образы, которые собираются один раз и скачиваются тысячи раз: zstd на высоком уровне или xz - упаковка долгая, распаковка быстрая. Архив текстов «на хранение»: bzip2 или xz. Совместимость со всем на свете: gzip.

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

Третий - чтение чужих решений. «Почему образы контейнеров перешли с gzip на zstd», «почему ядро Linux распространяется в xz», «почему резервные копии текстовых выгрузок жмут bzip2» - за каждым таким решением стоит одна и та же таблица: размер, время упаковки, время распаковки.

Теперь сам

Применить MTF к строке bbbaab; начальный список - a, b. Сколько нулей в результате? Затем восстанови строку по номерам 1 0 1 1 при том же начальном списке.

символ    номер    список после
  b         1        b a
  b         0        b a
  b         0        b a
  a         1        a b
  a         0        a b
  b         1        b a