RLE и энтропия: откуда берётся предел сжатия

Если ты объяснишь, почему не существует архиватора, сжимающего любой файл, посчитаешь энтропию строки aaab и скажешь, почему строка abab… сжимается лучше своей энтропии, - листай до «Теперь сам».

Как думаешь, бывает ли архиватор для всего

Реклама обещает: «наш архиватор уменьшает ЛЮБОЙ файл хотя бы на один бит, и из сжатого файла исходный восстанавливается точно».

Прежде чем читать дальше, ответь себе: возможно ли это хотя бы в принципе? Не «трудно ли написать», а может ли такая программа существовать. И если нет - что тогда вообще значит «хороший архиватор»?

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

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

Сжатие - тот же гардероб. Файлы - пальто, короткие записи - крючки. Восстановить файл точно можно, только если у каждого файла своя запись. Коротких записей меньше, чем файлов, поэтому сжать все нельзя. Хороший гардеробщик не вешает сто одно пальто на сто крючков - он знает, какие посетители приходят часто, и держит ближние крючки для них.

Механизм: счёт записей, RLE и энтропия

Счёт. Файлов длиной ровно n бит - 2ⁿ штук. Записей короче n бит - 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ − 1. Одной не хватает. Больше того: если архиватор укорачивает хоть один файл, какой-то другой он обязан удлинить. Пусть не удлиняет никого. Тогда файлам длиной до k бит достаются записи длиной до k бит, а тех и других поровну - значит, заняты все, и так при каждом k. Выходит, каждый файл получил запись своей же длины, и никто не укорочен. Это ответ на вопрос из начала: архиватора для всего не бывает, и не из-за нехватки изобретательности.

Значит, сжатие - это ставка на то, какие данные встречаются на практике. Первая ставка - на повторы символа подряд. RLE (кодирование длин серий) заменяет серию одинаковых символов парой «длина, символ»:

aaaabbbcca        →   (4, a) (3, b) (2, c) (1, a)          10 символов → 4 пары
abracadabra       →   (1, a) (1, b) (1, r) (1, a) …        11 символов → 11 пар

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

Вторая ставка - на неравные частоты: частым символам короткие коды, редким длинные. Это код Хаффмана из раздела про жадные алгоритмы. Там же было названо число, ниже которого он опуститься не может, - энтропия. Теперь - откуда оно берётся.

Пусть в тексте восемь разных символов, и каждый встречается одинаково часто - в одной восьмой позиций. Чтобы указать один из восьми, нужно три вопроса «да или нет»: каждый делит оставшихся пополам, а 8 → 4 → 2 → 1 - это три деления. Три бита, и 3 = log₂ 8. Логарифм здесь - не украшение, а число делений пополам, как в двоичном поиске.

Теперь символ встречается в доле p позиций. Он ведёт себя как «один из 1/p»: при p = 1/8 - один из восьми, при p = 1/2 - один из двух. На него нужно log₂(1/p) бит. Когда 1/p - не степень двойки, число выходит дробным. Отдельному символу дробное число бит выдать нельзя; это средняя цена, к которой можно приблизиться на длинном тексте. Энтропия - среднее этого числа по всем позициям текста: каждый символ входит с весом своей доли.

H = Σ p · log₂(1/p)        бит на символ; знак Σ - сумма по всем разным символам текста

Правило

Ни один способ сжатия без потерь не укорачивает все файлы: укорачивая одни, он удлиняет другие. RLE выгоден, только когда средняя длина серии заметно больше единицы. Если кодировать каждый символ отдельно и учитывать только его частоту, в среднем нельзя потратить меньше H = Σ p · log₂(1/p) бит на символ. Это предел для способов, которые знают о тексте только частоты символов; способ, который видит связи между соседними символами, уходит ниже.

Разбор: RLE на четырёх строках

def rle(s):
    pary = []
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j = j + 1                 # ищем конец серии
        pary.append([j - i, s[i]])
        i = j
    return pary

def obratno(pary):
    kuski = []
    for para in pary:
        kuski.append(para[1] * para[0])
    return "".join(kuski)

Замер. В третьем столбце - число пар; каждая пара занимает два места (счётчик и символ), так что запись короче исходной, только если пар меньше половины длины. Место - условная ячейка под один символ или одно число; сколько счётчик занимает на самом деле - отдельный вопрос, он в «Что ломается».

строка                                          длина     пар     запись против исходной
"a" * 1000                                       1000        1     2 места вместо 1000
строка скана: 12 w, 3 b, 20 w, 2 b, 13 w           50        5     10 вместо 50
tekst(1000, 4, 1) - случайные четыре буквы       1000      756     1512 вместо 1000
"ab" * 500                                       1000     1000     2000 вместо 1000

Строка скана - это ряд точек чёрно-белой страницы: длинные белые поля, короткие чёрные штрихи. Для таких данных RLE и придуман, и там он сжимает впятеро. На случайном тексте серии короткие - в среднем 1,3 символа, - и запись раздувается в полтора раза. На abab… серий длиннее единицы нет вовсе, и размер удваивается.

Разбор: энтропия abracadabra и где она перестаёт быть пределом

В слове 11 символов: a - пять раз, b и r - по два, c и d - по одному.

символ    доля p     log₂(1/p)     вклад p · log₂(1/p)
  a        5/11        1,138            0,517
  b        2/11        2,459            0,447
  r        2/11        2,459            0,447
  c        1/11        3,459            0,314
  d        1/11        3,459            0,314
                                  H =   2,040 бита на символ

На всё слово - 11 · 2,040 = 22,4 бита. Код Хаффмана для этих частот тратит 23 бита: он обязан выдавать целое число бит на символ и поэтому чуть не дотягивается до предела. Код фиксированной длины - три бита на символ, 33 бита.

Теперь граница. Возьмём строку "ab" * 500. Символов два, доли равны, H = 1 бит на символ, 1000 бит на строку. Но ты только что прочитал эту строку в виде короткой записи: «ab, пятьсот раз». Как запись оказалась короче предела?

Предел честный, но он посчитан для модели, в которой про символ известна только его частота. Такая модель не видит, что после a всегда идёт b. Способ, который это видит, - другая модель, и у неё другой предел. Следующие уроки ровно про это: LZ77Разбирается в разделе 17, глава «Сжатие - RLE, Хаффман, LZ77, арифметическое»: LZ77: ссылка назад вместо повтора замечает повторы кусков, контекстные модели - что символ зависит от предыдущих. Замер из следующего урока: журнал запросов из 826 символов имеет энтропию 3578 бит, а LZ77 записывает его примерно в 900.

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

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

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

Второе: счётчик не помещается. Если на длину серии отведён один байт, серия из 300 символов в него не влезет. Её режут на 255 и 45; забытая проверка даёт счётчик 44 и потерянные 256 символов.

Третье: счётчик и данные записаны одними и теми же знаками. Запись 3a12b понятна, пока в данных нет цифр. Строка 111a запишется как 311a - и это читается и как «три единицы, одна a», и как «триста одиннадцать букв a». Счётчик хранят отдельным полем фиксированного размера, а не цифрами в общем потоке.

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

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

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

Второй - RLE внутри больших форматов. В чистом виде он живёт в старых форматах картинок и в факсах. А как ступень он стоит почти везде: в архиваторе bzip2 (до и после главного преобразования), в JPEG (серии нулей), в форматах хранения таблиц по столбцам, где значение в столбце часто повторяется тысячи раз подряд.

Третий - разговор о невозможном. Когда обещают сжатие «в сто раз для любых данных», счёт записей из этого урока закрывает вопрос за минуту: не для любых, а для каких именно?

Теперь сам

Строка aaab. Запиши её в RLE. Посчитай энтропию в битах на символ (log₂(4/3) ≈ 0,415). Сколько бит потратит на эту строку код Хаффмана и сколько - идеальный кодировщик, достигающий энтропии?

H = 3/4 · log₂(4/3) + 1/4 · log₂ 4 = 0,75 · 0,415 + 0,25 · 2 = 0,311 + 0,5 = 0,811 бита на символ