Max Home IndustryМы широко используем алгоритмы сжатия, чтобы сэкономить как хранилище, так и время. Наиболее популярные алгоритмы основаны на сжатии словаря LZ и используются в форматах GIF, Deflate, Zip, PNG. Его даже назвали вехой IEEE. Но мы мало о них знаем. Один давний вопрос: может ли добавление одного бита в файл кардинально изменить достигнутую степень сжатия? Конечно нет!
Сжатие LZ, в частности LZ 78, представляет как практический, так и теоретический интерес. Это один из классов методов сжатия словарей, изобретенных в 1978 году Абрахамом Лемпелем и Якобом Зивом.
Метод сжатия по словарю работает без потерь и работает путем создания словаря коротких последовательностей, которые затем можно использовать для кодирования рассматриваемого файла. Например, если у вас есть файл, состоящий только из 10 000 «A», то единственная словарная запись «A» и кодирование 10 000 обеспечат очень эффективное сжатие. В реальном мире, конечно, файлы состоят из сложных битовых последовательностей, но, если они не случайны, некоторые последовательности повторяются. Сложность в том, чтобы их найти.
Оптимальная кодировка словаря дает верхнюю границу колмогоровской сложности строки. Сложность Колмогорова — это просто самая короткая программа, которая будет генерировать строку, и очевидно, что алгоритм сжатия (плюс словарь) квалифицируется как программа, и, следовательно, любая другая программа, которая выполняет эту работу, должна быть короче.
Учитывая все это, возникает вопрос: «Может ли добавление одного бита существенно изменить степень сжатия?». Иногда это называют «однобитной катастрофой».
«Предположим, вы сжимали файл, используя свой любимый алгоритм сжатия, но понимаете, что произошла опечатка, из-за которой вы добавили один бит к исходному файлу. Сжимайте его еще раз, и вы получаете сжатый файл гораздо большего размера, только с разницей в один бит. между исходными файлами. К счастью, большинство алгоритмов сжатия не имеют такого странного поведения; но если ваш любимый алгоритм сжатия называется LZ’78, один из самых известных и изученных из них, то этот удивительный сценарий вполне может случиться … »
Вопрос как в природе порядка и энтропии, так и в методах сжатия. Вы могли бы перефразировать это как «может ли один бит значительно изменить порядок в битовой последовательности или строке?»
Ответ, открытый Гийомом Лагардом и Сильвеном Перифелем в Сорбонне, заключается в том, что для бесконечно-битовых последовательностей добавление одного нуля к началу превращает сжимаемую последовательность в несжимаемую.
Я думаю, вы могли бы сказать, что один-единственный бит может превратить порядок в беспорядок, но это может быть немного театрально.
Для конечных слов ситуация не так плоха, поскольку сжимаемость слова с добавленным битом должна быть близка к исходному слову. Но есть слова, которые легко сжимаются, которые преобразуются в слова, которые намного сложнее сжать, добавив один бит.
Это теоретическое размышление имеет практическое значение:
«Эта« катастрофа »показывает, что LZ’78 не является устойчивым в отношении добавления или удаления битов. Поскольку обычное хорошее поведение функций, используемых в представлении данных, является своего рода« непрерывностью », наши результаты показывают, что в этом отношении , LZ’78 — не лучший выбор, так как два слова, которые отличаются одним битом, могут иметь изображения очень далеко друг от друга «.