Универсальные методы сжатия

Существует достаточно много универсальных (обратимых) методов сжатия, однако в их основе лежит сравнительно небольшое количество теоретических алгоритмов, которые мы рассмотрим на примерах.

Определение:метод сжатия называется обратимым, если из данных, полученных при сжатии, можно точно восстановить исходный массив данных.

Пример:форматы файлов, которые хранят информацию сжатую без потерь:

Графическая информация – gif, tiff, png;

Видеоинформация – avi;

Для любых типов данных - zip, rar, arj,lzh, cab.

Метод упаковки

Напомним, что при кодировании информации каждому объекту (символ, пикселю, измерению звука) ставиться в соответствие двоичный код фиксированной длины i. Тогда объем всей цифровой информации можно определить по формуле V=i⋅k, где k – это количество объектов (символов, пикселей и т.д) в потоке информации.

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

Пример 1. Представлен текст в кодировки ASCII, который содержит не все 256 символов, а только 12: цифры от «0» до «9», знак (минус) и пробел. Использование ASCII кодировки будет ставить в соответствие каждому символу код объемом 8 бит. Тогда текст «280 -1296 48 40 365 -159 13 777» в памяти компьютера займет 30сим • 8бит= 240 бит= 30 байт.

Однако для кодирования такого количества символов достаточно всего 4-х бит. Если упаковать коды данных символов в 4 бита (например, так: «0» - 0000, «1» - 0001, ... «9» - 1001, минус - 1110, пробел - 1111), то получим двукратное сжатие данных (15 байт).

Формат записи чисел, при котором число записывается в десятичной системе, а цифры числа кодируются 4-битовыми кодами, называется BCD-форматом (Binary Code Decimal, или двоично-десятичная запись). BCD-формат нередко используется в программировании для хранения целых чисел, например в базах данных.

Пример 2. Сообщение «КОЛ ОКОЛО КОЛОКОЛА» записанное в кодировке ASCII будет весить

Vascii=8бит • 18 символов = 144 бита, а кодировке Unicode соответственно Vunicode = 16 бит • 18 символов = 288 бит.

Однако данное сообщение содержит всего 5 различных символов, следовательно, каждый символ может быть закодирован тремя битами, например, так: «А» - 000, «К» - 001, «Л» - 010, «О» - 011 и пробел - 111. Тогда объем сообщения будет равен V=18 символов • 3 бит = 54 бита.

В результате мы получаем коэффициент сжатия равный 144/54 = 2,(6) для кодировки ASCII и 288/54=5,(3) для кодировки Unicode.

Одно из преимуществ метода упаковки заключается в том, что любой фрагмент сжатых данных можно распаковать, полностью восстановив исходных данных, совершенно не используя предшествующие данные. Но метод упаковки дает хорошие результаты, только если множество используемых символов, по отношению к полному алфавиту, невелико (см.пример 2). Если же в тексте используются практически все символы алфавита, то коэффициент сжатия окажется незначительным, а возможно, что сжать данные вообще не получиться.

Метод Хаффмана

Недостаток метода упаковки заключается в том, что все символы кодируются битовыми последовательностями одинаковой длины, а изучив раздел «Понятие информации. Измерение количества информации» мы знаем, что оптимального кодирования можно добиться, используя неравномерные коды, например код Хаффмана.

Напомним, что код Хаффмана является неравномерным и префиксным. Неравномерность означает, что те символы, которые встречаются в сообщении чаще, кодируются более короткими кодами, а символы, которые встречаются редко – более длинными. Префиксность говорит о том, что ни один код не является началом другого кода, что позволяет достичь однозначности при декодировании.

Зная вероятности символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Коды Хаффмана обладают свойством префиксности. То есть ни одно кодовое слово не является префиксом другого, что позволяет однозначно их декодировать.

Выделяют побуквенное кодирование и блочное кодирование.

Сжатие методом Хаффмана выполняется за два прохода. На первом проходе читаются все входные данные и подсчитываются частоты встречаемости всех символов. Затем по этим данным строится дерево Хаффмана, по которому вычисляются коды символов. На втором проходе, входные данные читаются еще раз и перекодируются на основе новой кодовой таблицы.

Алгоритм построения побуквенных кодов методом Хаффмана:

1) Подсчитать частоты встречаемости всех символов;

2) Построить дерево кодирования (алгоритм построения дерева);

Построить коды символов (левая ветка- 0, правая ветка -1)