Сжатие данных: объяснение
Каждая загружаемая вами веб-страница, каждый ZIP-файл и каждое изображение PNG были сжаты: уменьшены без потери единого бита и снова распакованы по прибытии. Методы, которые за этим стоят, удивительно просты. Они ищут то, что повторяется, и вместо того чтобы повторять это ещё раз, говорят «то же, что и раньше». Как далеко заходит эта идея и где она упирается в предел — одна из самых изящных историй в информатике.
Без потерь и с потерями
Сжатие бывает двух видов. Сжатие без потерь возвращает в точности оригинал, что необходимо для текста, программ, электронных таблиц и всего, где имеет значение даже один неверный бит. Сжатие с потерями, применяемое для фотографий, музыки и видео, отбрасывает детали, которые люди почти не воспринимают, и достигает гораздо меньших размеров, но оригинал утрачивается навсегда. Эта страница и демонстратор посвящены сжатию без потерь, которое работает за счёт поиска и устранения избыточности — тех частей данных, которые можно было предсказать.
Кодирование длин серий
Простейший метод заменяет серию одинаковых символов счётчиком и самим символом: двенадцать белых пикселей превращаются в 12W. Его использовали факсимильные аппараты, ранние растровые форматы и графический формат PCX, ведь отсканированные страницы и простые рисунки полны длинных серий. На обычном тексте он бесполезен и даже вреден: серии редки, а запись счётчика при каждой отдельной букве удваивает размер. Тем не менее кодирование длин серий продолжает жить внутри других методов — для серий нулей, остающихся после первичного преобразования.
LZ77: ссылки назад
В 1977 году Абрахам Лемпель и Якоб Зив, два исследователя из Техниона в Израиле, опубликовали метод, изменивший всю область. Кодер хранит окно только что обработанного текста. Если следующие символы уже встречались в окне, он записывает пару: как далеко назад начинается более ранняя копия и какова её длина. Иначе он записывает сам символ. Декодеру вообще не нужен словарь — только текст, который он уже восстановил. Ссылка может даже перекрывать текст, который она порождает, так что серия из 100 одинаковых букв — это одна буква и одна ссылка.
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 бит на букву.
Попробуйте сами
Откройте демонстратор сжатия, чтобы запустить LZ77, LZW и кодирование длин серий на абзаце, песне с припевом, ряде пикселей, таблице данных, случайных буквах или ДНК либо на собственном тексте. Нажмите на любую ссылку LZ77, чтобы увидеть, что она копирует, понаблюдайте, как растёт словарь LZW, и сравните все методы с ZIP и пределом энтропии.
Часто задаваемые вопросы
Что означает степень сжатия 3 : 1?
То, что оригинал в три раза больше сжатой версии, то есть сжатый файл занимает треть места и экономит две трети. Текст с ZIP обычно достигает от 2 : 1 до 4 : 1; данные с большим количеством повторов, например файлы журналов (логи), — часто гораздо большего.
Почему повторное сжатие ZIP-файла не помогает?
Первый проход уже устранил повторы, и его результат выглядит почти случайным. Второй проход не находит ничего, на что можно сослаться, и только добавляет собственные накладные расходы, поэтому файл остаётся того же размера или немного растёт.
Почему большее окно LZ77 лучше?
Большее окно позволяет кодеру находить повторы, лежащие дальше в прошлом, например припев, который возвращается через несколько куплетов. Цена в том, что запись каждого расстояния требует больше битов, а поиск занимает больше времени, — поэтому deflate ограничивается 32 KB, а более новые методы допускают мегабайты.
Сжатие — то же самое, что шифрование?
Нет. Сжатие делает данные меньше, и обратить его может кто угодно; шифрование делает данные нечитаемыми без ключа. Их часто сочетают, и тогда данные нужно сначала сжать: зашифрованные данные выглядят случайными и уже не сжимаются.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Открыть демонстратор сжатия