Универсальные методы сжатия
Существует достаточно много универсальных (обратимых) методов сжатия, однако в их основе лежит сравнительно небольшое количество теоретических алгоритмов, которые мы рассмотрим на примерах.
Определение:метод сжатия называется обратимым, если из данных, полученных при сжатии, можно точно восстановить исходный массив данных.
Пример:форматы файлов, которые хранят информацию сжатую без потерь:
Графическая информация – 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)
Дата добавления: 2015-11-10; просмотров: 3685;