Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Легко доказывается теорема.
Для любого N > 0 нет алгоритма сжатия без потерь, который: 1. Любой файл длиной не более N байт или оставляет той же длины, или уменьшает. 2. Существует файл длиной не более N, который уменьшается хотя бы на один байт. |
Доказательство. Не ограничивая общности, можно предположить, что уменьшился файл A длины ровно N. Обозначим алфавит как . Рассмотрим множество . В этом множестве исходных файлов, в то время как сжатых не более чем . Поэтому функция декомпрессии неоднозначна, противоречие. Теорема доказана.
Впрочем, данная теорема нисколько не бросает тень на сжатие без потерь. Дело в том, что любой алгоритм сжатия можно модифицировать так, чтобы он увеличивал размер не более чем на 1 бит: если алгоритм уменьшил файл, пишем «1», потом сжатую последовательность, если увеличил — пишем «0», затем исходную. Пример того, как это реализуется на псевдо-C++, показан ниже:
bin_data_t __compess(bin_data_t input) // bin_data_t - тип данных, означающий произвольную последовательность бит переменной длины{ bin_data_t output = arch(input); // функция bin_data_t arch(bin_data_t input) реализует некий алгоритм сжатия данных if (output.size()<input.size()) // если алгоритм уменьшил размер данных, функция bin_data_t::size() возвращает размер данных { output.add_begin(1); // функция bin_data_t::add_begin(bool __bit__) добавляет бит, равный __bit__ в начало последовательности return output; // возвращаем сжатую последовательность с добавленной «1» } else // иначе (если алгоритм увеличил или не изменил размер данных) { input.add_begin(0); // добавляем «0» к исходной последовательности return input; // возвращаем исходный файл с добавленным «0» }}Так что несжимаемые фрагменты не приведут к бесконтрольному «раздуванию» архива. «Реальных» же файлов длины N намного меньше, чем (говорят, что данные имеют низкую информационную энтропию) — например, маловероятно, чтобы буквосочетание «щы» встретилось в осмысленном тексте, а в оцифрованном звуке уровень не может за один сэмпл прыгнуть от 0 до 100 %. К тому же за счёт специализации алгоритмов на некоторый тип данных (текст, графику, звук и т. д.) удаётся добиться высокой степени сжатия: так, применяющиеся в архиваторах универсальные алгоритмы сжимают звук примерно на треть (в 1,5 раза), в то время как FLAC — в 2,5 раза. Большинство специализированных алгоритмов малопригодны для файлов «чужих» типов: например, звуковые данные плохо сжимаются алгоритмом, рассчитанным на тексты.
Дата публикования: 2015-01-26; Прочитано: 381 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!