Оригинал
Экономия

Метод

Подробнее о сжатии

Демонстратор сжатия

Как файл может стать меньше, не потеряв ни одной буквы? Благодаря тому, что он повторяется. Вставьте текст или выберите пример и посмотрите на три классических метода в работе: LZ77 указывает назад на уже встречавшийся текст, LZW по ходу чтения составляет словарь строк, а кодирование длин серий подсчитывает серии одинаковых символов. Результат каждого метода снова распаковывается, чтобы показать, что ничего не потеряно, а график сравнивает методы с ZIP и с пределом энтропии. Введите или вставьте текст либо выберите пример, а затем выберите метод. LZ77 заменяет повторы ссылками на более ранний текст: нажмите на выделенный фрагмент, чтобы увидеть, что он копирует. LZW по ходу чтения строит словарь строк и отправляет их номера. RLE сжимает серии одинаковых символов. График сравнивает каждый метод с ZIP и с пределом энтропии, а приложение снова распаковывает результат, чтобы проверить, что ничего не потеряно.

Как это работает

  1. Введите или вставьте текст либо выберите пример: абзац, песню с припевом, ряд пикселей, таблицу данных, случайные буквы или ДНК.
  2. Выберите LZ77, LZW или RLE. Для LZ77 задайте, как далеко назад он может заглядывать, и нажмите на выделенную ссылку, чтобы увидеть более ранний текст, который она копирует.
  3. Сравните размеры на плашках и на графике с ZIP и с пределом энтропии; проверка под текстом подтверждает, что распаковка возвращает оригинал.

Всё дело в повторах

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

Почему некоторые данные не сжимаются

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

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

Чем сжатие без потерь отличается от сжатия с потерями?

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

Как ZIP сжимает файлы?

ZIP и gzip используют deflate: сначала работает LZ77 с окном 32 KB, а затем литералы и ссылки записываются кодами Хаффмана — короткими кодами для частых значений и длинными для редких. Именно из-за второго шага ZIP обычно обходит показанный здесь простой LZ77, который тратит на каждый токен фиксированное число битов.

Может ли LZ77 опуститься ниже энтропии?

Показанная энтропия считает символы по одному, без контекста. LZ77 и LZW используют контекст, ведь ссылка копирует целый отрезок предыдущего текста, поэтому на тексте с повторами они могут превзойти это число с большим запасом. Но истинную энтропию источника, учитывающую весь контекст, они не превзойдут никогда.

Почему размеры отличаются от настоящего ZIP-файла?

Демонстратор считает только биты закодированных данных. Настоящий ZIP-файл добавляет заголовки, имя файла, контрольную сумму и таблицы Хаффмана, из-за чего очень маленькие файлы скорее увеличиваются, чем уменьшаются.

Отправляется ли мой текст куда-нибудь?

Нет. Все методы, включая сравнение с ZIP, работают в вашем браузере, а ваш текст остаётся в локальном хранилище этого браузера.

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

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

Перейти в редактор