Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Методы сжатия без потерь

В основе всех методов сжатия лежит простая идея: если представлять часто используемые элементы короткими кодами, а редко используемые -длинными кодами, то для хранения блока данных требуется меньший объем памяти, чем если бы все элементы представлялись кодами одинаковой дли­ны. Данный факт известен давно: вспомним, например, азбуку Морзе, в ко­торой часто используемым символам поставлены в соответствие короткие последовательности точек и тире, а редко встречающимся - длинные.

Точная связь между вероятностями и кодами установлена в теореме Шеннона о кодировании источника, которая гласит, что элемент shвероят­ность появления которого равняется p(s,), выгоднее всего представлять -1о& p(sj) битами. Если при кодировании размер кодов всегда в точности получа­ется равным -log2 p(s,) битам, то в этом случае длина закодированной по­следовательности будет минимальной для всех возможных способов коди­рования. Если распределение вероятностей F= {pis,)} неизменно, и вероят­ности появления элементов независимы, то мы можем найти среднюю длину кодов как среднее взвешенное

Это значение также называется энтропией распределения вероятно­стей F или энтропией источника в заданный момент времени.

Обычно вероятность появления элемента является условной, т. е. зави­сит от какого-то события. В этом случае при кодировании очередного эле­мента st распределение вероятностей F принимает одно из возможных зна­чений Fk, т. е. F = Ft и соответственно Я = Я*. Можно сказать, что источник находится в состоянии к, которому соответствует набор вероятностей pt(si) генерации всех возможных элементов st. Поэтому среднюю длину кодов можно вычислить по формуле

где Рк - вероятность того, что F примет к-е значение, или, иначе, вероят­ность нахождения источника в состоянии к.

Итак, если нам известно распределение вероятностей элементов, генери­руемых источником, то мы можем представить данные наиболее компакт­ным образом, при этом средняя длина кодов может быть вычислена по фор­муле (1.2).

Но в подавляющем большинстве случаев истинная структура источника нам неизвестна, поэтому необходимо строить модель источника, которая позволила бы нам в каждой позиции входной последовательности оценить вероятность p(s,) появления каждого элемента st алфавита входной последо­вательности. В этом случае мы оперируем оценкой q(si) вероятности эле­мента S/.

Методы сжатия- могут строить ММдель источника адаптивно по мере ©б> работки потока данных или использовать фиксированную модель, создан­ную на основе априорных представлений о природе типовых данных, тре­бующих сжатия.

Процесс моделирования может быть либо явным, либо скрытым. Веро­ятности элементов могут использоваться в методе как явным, так и неявным образом. Но всегда сжатие достигается за счет устранения статистической избыточности в представлении информации.

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

Существует 2" различных файлов длины п бит, где л = 0, 1, 2, ... Если размер каждого такого файла в результате обработки уменьшается хотя бы на 1 бит, то 2" исходным файлам будет соответствовать самое большее 2"-1 различающихся сжатых файлов. Тогда по крайней мере одному архивному файлу будет соответствовать несколько различающихся исходных, и, сле­довательно, его декодирование без потерь информации невозможно в принципе.

Вышесказанное предполагает, что файл отображается в один файл и объ­ем данных указывается в самих данных. Если это не так, то следует учиты­вать не только суммарный размер архивных файлов, но и объем информации, необходимой для описания нескольких взаимосвязанных архивных файлов и/или размера исходного файла. Общность доказательства при этом сохраняется.

Поэтому невозможен "вечный" архиватор, который способен бесконеч­ное число раз сжимать свои же архивы. "Наилучшим" архиватором является программа копирования, поскольку в этом случае мы можем быть всегда уверены в том, что объем данных в результате обработки не увеличится.

Регулярно появляющиеся заявления о создании алгоритмов сжатия, "обеспечивающих сжатие в десятки раз лучшее, чем у обычных архивато­ров", являются либо ложными слухами, порожденными невежеством и по­гоней за сенсацией, либо рекламой аферистов. В области сжатия без потерь, т. е. собственно сжатия, такие революции невозможны. Безусловно, степень сжатия компрессорами типичных данных будет неуклонно расти, но улуч­шения составят в среднем десятки или даже единицы процентов, при этом каждый последующий этап эволюции будет обходиться значительно дороже предыдущего. С другой стороны, в сфере сжатия с потерями, в первую оче­редь компрессии видеоданных, все еще возможно многократное улучшение сжатия при сохранении субъективной полноты получаемой информации.