Почему повторное сжатие файла делает его больше

Почему нельзя сжимать файл бесконечно? Zip уменьшает размер файла «Алиса в Стране чудес» с 100 000 байт до примерно 37 000 байт. Если заархивировать этот файл ещё раз, он увеличится в размере. В этом видео показана одна строка текста: «banana band banana bread banana bandana», которая иллюстрирует две идеи Deflate (метод в zip и gzip): указатели, копирующие ранее записанный текст, и короткие коды Хаффмана для распространённых букв. Затем происходит подсчёт. Существует 8 файлов по 3 бита и всего 7 более коротких строк, поэтому ни один компрессор без потерь не может уменьшить каждый файл. Каждый компрессор — это ставка на то, какие файлы у вас действительно будут. Каждое число на экране получено из запущенного кода: игрушечная реализация LZ77 и Хаффмана, а также реальный вывод Deflate из zlib-ng 1.3.1, стандартной zlib 1.3 и GNU gzip 1.12, с libbz2 и liblzma для тестов со случайным файлом и Алисой. Реальные размеры указываются с указанием библиотеки, которая их создала, поскольку zlib-ng и стандартная zlib могут отличаться на один-два байта. Условные значения указаны в битах и ​​не включают кодовую таблицу. Реальные размеры Deflate указаны в байтах и ​​включают всё. Разделы 0:00 Дважды сжатие — и он увеличивается 0:23 Одна строка, 312 бит 0:41 Повторы становятся указателями 1:35 Короткие коды для распространенных букв 2:22 Строка без шаблона 2:44 Реальный Deflate в байтах 3:24 Обе идеи — ставки 3:46 Подсчет: 8 файлов, 7 более коротких строк 5:06 Компрессор — это ставка 5:45 Когда помогает второй проход 6:06 Насколько маленьким может стать файл? 7:32 Проверка утверждения 8:05 Почему Алиса перестала уменьшаться Источник текста: Льюис Кэрролл, «Приключения Алисы в Стране чудес» (1865, общественное достояние), текст проекта Gutenberg из корпуса NLTK. Ссылки Хаффман, «Метод построения кодов с минимальной избыточностью», Труды IRE, 1952 Шеннон, «Математическая теория коммуникации», 1948 RFC 1951, формат сжатых данных DEFLATE: https://www.rfc-editor.org/rfc/rfc1951 RFC 1952, формат файла GZIP: https://www.rfc-editor.org/rfc/rfc1952 #сжатие #информатика #кодированиехаффмана