- •Оптимальное и эффективное кодирование
- •Понятие кодирования. Кодовое дерево.
- •Уровень
- •Теорема кодирования источников, неравенство Крафта.
- •Методы оптимального кодирования. Сжатие данных.
- •Метод кодирования Шеннона - Фано.
- •Метод кодирования Хаффмана.
- •4.3.3. Арифметическое кодирование.
- •Алгоритм универсального кодирования методом Лемпела-Зива.
- •Особенности программ- архиваторов.
- •Сжатие с потерями.
Особенности программ- архиваторов.
Если коды алгоритмов типа LZ передать для кодирования алгоритму Хаффмана или арифметическому алгоритму, то полученный двухшаговый алгоритм дает результат сжатия, подобный случайным программам-архиваторам, таким, как GZ, AGZ, PK zip. Наибольшую степень сжатия дают двухпроходные алгоритмы, которые последовательно сжимают два раза исходные данные, но они соответственно и работают в два раза медленнее. Большинство программ- архиваторов сжимают каждый файл по отдельности, хотя некоторые способны это делать в потоке файлов, что дает соответствующее увеличение степени сжатия, но и одновременно усложняет способы работы с полученным архивом. Например, замена в таком архиве файла на более новую версию может потребовать перекодирования всего архива. В общем потоке с файлами способен работать архиватор RAR, а в ОС Unix практически все архиваторы, такие как Gzip, Bzip2 и т.д.
Расширение файла |
Программа-архиватор |
Тип кодирования |
ark |
arc, PKazc |
LZW, Хаффана |
zip |
zip, PKzip, unzip, PKunzip |
LZW, LZ77, Хаффмана, Шеннона – Фано |
azj |
azj |
LZ77, Хаффмана |
pak |
pak |
LZW |
gif |
графика |
LZW |
tif, tiff |
факс |
LZW |
Сжатие с потерями.
Сжатие с потерями используется в основном для трех видов данных:
1.Полноцветная графика.
2.Видеоинформация.
3.Звуковая информация.
Сжатие с потерями обычно происходит в два этапа:
1.Исходная информация с потерями приводится к виду, в котором ее можно эффективно сжимать алгоритмами второго этапа сжатия без потерь.
Основная идея сжатия графической информации с потерями состоит в следующем: каждая точка графической картинки характеризуется тремя равноценными атрибутами – яркость, цветность, насыщенность. Человек воспринимает их не как равные, т.е. полностью воспринимается информация о яркости, и гораздо меньшей степени о цветности и насыщенности, что позволяет отбрасывать часть информации о двух последних атрибутах без существенной потери качества изображения. Для сжатия графической информации с потерями в конце 80-х годов был установлен единый стандарт JPEG. В этом формате сложно регулировать степень сжатия, задавая степень потери качества.
Сжатие видеоинформации основано на том, при переходе от одного кадра к другому на экране обычно ничего не меняется, поэтому сжатая видеоинформация представляет собой запись некоторых базовых кадров и последовательности изменения в них, при этом часть информации естественно может отображаться. А сжатую таким образом информацию можно и дальше сжимать другими методами, но уже без потерь.
На сегодняшний день существует много форматов сжатия видеоинформации, но наиболее распространенным является MPEG. Этот стандарт был предложен в 1988 году и является практически единственным для спутникового телевидения и записи информации на DVD, CD и т.д.
Сжатие звуковой информации с потерями осуществляется на основе ограничении спектра звукового сигнала диапазоном реальной слышимости человека. Используют для этого различные стандарты сжатия звуковых файлов и достаточно часто MPEG без видеоданных.