Сжатие данных: объяснение

Каждая загружаемая вами веб-страница, каждый ZIP-файл и каждое изображение PNG были сжаты: уменьшены без потери единого бита и снова распакованы по прибытии. Методы, которые за этим стоят, удивительно просты. Они ищут то, что повторяется, и вместо того чтобы повторять это ещё раз, говорят «то же, что и раньше». Как далеко заходит эта идея и где она упирается в предел — одна из самых изящных историй в информатике.

Строка текста, в которой повторяющиеся фрагменты заменены стрелками, указывающими назад на их первое появление, рядом со столбиками исходного и сжатого размера
Строка текста, в которой повторяющиеся фрагменты заменены стрелками, указывающими назад на их первое появление, рядом со столбиками исходного и сжатого размера

Без потерь и с потерями

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

Кодирование длин серий

Простейший метод заменяет серию одинаковых символов счётчиком и самим символом: двенадцать белых пикселей превращаются в 12W. Его использовали факсимильные аппараты, ранние растровые форматы и графический формат PCX, ведь отсканированные страницы и простые рисунки полны длинных серий. На обычном тексте он бесполезен и даже вреден: серии редки, а запись счётчика при каждой отдельной букве удваивает размер. Тем не менее кодирование длин серий продолжает жить внутри других методов — для серий нулей, остающихся после первичного преобразования.

LZ77: ссылки назад

В 1977 году Абрахам Лемпель и Якоб Зив, два исследователя из Техниона в Израиле, опубликовали метод, изменивший всю область. Кодер хранит окно только что обработанного текста. Если следующие символы уже встречались в окне, он записывает пару: как далеко назад начинается более ранняя копия и какова её длина. Иначе он записывает сам символ. Декодеру вообще не нужен словарь — только текст, который он уже восстановил. Ссылка может даже перекрывать текст, который она порождает, так что серия из 100 одинаковых букв — это одна буква и одна ссылка.

Абрахам Лемпел, который вместе с Яковом Зивом в Технионе в 1977 году опубликовал метод окна и ссылок, ныне известный как LZ77.
Абрахам Лемпел, который вместе с Яковом Зивом в Технионе в 1977 году опубликовал метод окна и ссылок, ныне известный как LZ77.

LZW: словарь, который учится

Второй метод Лемпеля и Зива, LZ78, вместо поиска назад в окне строит словарь. Его усовершенствованный вариант, предложенный Терри Уэлчем в 1984 году, — LZW — начинает со всех 256 значений байта и на каждом шаге отправляет номер самой длинной уже известной строки, а эту строку вместе со следующим символом добавляет как новую запись. Декодер восстанавливает тот же словарь по одним только номерам. LZW был быстрым и простым и попал в команду compress в Unix, графический формат GIF и файлы TIFF, пока патенты на него не вызвали в 1990-х годах долгий спор.

Deflate, ZIP и дальше

Метод deflate Фила Каца, представленный вместе с PKZIP 2 в 1993 году, сочетает LZ77 с кодированием Хаффмана: найдя повторы, он назначает самым частым литералам, длинам и расстояниям самые короткие битовые коды. Deflate используется в ZIP, gzip, изображениях PNG и при сжатии веб-страниц, и именно его демонстратор измеряет с помощью встроенного компрессора браузера. Более новые методы, такие как Zstandard, Brotli и xz, используют окна большего размера, более умный поиск совпадений и более точное энтропийное кодирование и сжимают типичные файлы ещё на 10–30%.

Почему не всё можно сжать

Никакой метод не может уменьшить каждый файл. Существует 2ⁿ файлов длиной n бит, но лишь 2ⁿ − 1 файлов короче, поэтому если бы метод уменьшал их все, два файла превратились бы в одно и то же и восстановить оба было бы невозможно — это принцип Дирихле. Поэтому каждый компрессор увеличивает некоторые входные данные, обычно похожие на случайные: зашифрованные файлы, уже сжатые файлы и шум. Это заодно и проверка на случайность: данные, которые не может сжать ни один компрессор, выглядят случайными.

Предел энтропии

Клод Шеннон показал в 1948 году, что энтропия источника — это наименьшее возможное среднее число битов на символ для любого кода без потерь. При побуквенном подсчёте английский текст имеет энтропию около 4 бит на букву — половину от 8 бит, которыми он хранится. Методы, использующие контекст, такие как LZ77, на тексте с повторами опускаются ниже этого побуквенного значения, потому что ссылка заменяет сразу целый отрезок. Лучшие современные компрессоры, предсказывающие каждую букву по всему, что было до неё, доводят английский до менее чем 2 бит на букву.

Клод Шеннон, который в 1948 году в Bell Labs точно определил, сколько информации содержит сообщение, и измерял её в битах.
Клод Шеннон, который в 1948 году в Bell Labs точно определил, сколько информации содержит сообщение, и измерял её в битах.

Попробуйте сами

Откройте демонстратор сжатия, чтобы запустить LZ77, LZW и кодирование длин серий на абзаце, песне с припевом, ряде пикселей, таблице данных, случайных буквах или ДНК либо на собственном тексте. Нажмите на любую ссылку LZ77, чтобы увидеть, что она копирует, понаблюдайте, как растёт словарь LZW, и сравните все методы с ZIP и пределом энтропии.

Часто задаваемые вопросы

Что означает степень сжатия 3 : 1?

То, что оригинал в три раза больше сжатой версии, то есть сжатый файл занимает треть места и экономит две трети. Текст с ZIP обычно достигает от 2 : 1 до 4 : 1; данные с большим количеством повторов, например файлы журналов (логи), — часто гораздо большего.

Почему повторное сжатие ZIP-файла не помогает?

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

Почему большее окно LZ77 лучше?

Большее окно позволяет кодеру находить повторы, лежащие дальше в прошлом, например припев, который возвращается через несколько куплетов. Цена в том, что запись каждого расстояния требует больше битов, а поиск занимает больше времени, — поэтому deflate ограничивается 32 KB, а более новые методы допускают мегабайты.

Сжатие — то же самое, что шифрование?

Нет. Сжатие делает данные меньше, и обратить его может кто угодно; шифрование делает данные нечитаемыми без ключа. Их часто сочетают, и тогда данные нужно сначала сжать: зашифрованные данные выглядят случайными и уже не сжимаются.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Открыть демонстратор сжатия