Страница: 21/29
Если исходные символы передаются не равновероятно и не независимо, то энтропия источника будет ниже своей максимальной величины HMAX(Х)=log2 N. В этом случае возможно более экономное кодирование. При этом на каждый исходный символ в среднем будет затрачено n*= Н(Х) символов кода. Для характеристики достижимой степени сжатия используется коэффициент избыточности RИЗБ = 1—Н(Х)/HMAX(Х). Для характеристики же достигнутой степени сжатия на практике применяют так называемый коэффициент сжатия Кcж. Коэффициент сжатия — это отношение первоначального размера данных к их размеру в сжатом виде, — обычно дается в формате К.сж:1 Путем несложных рассуждений можно получить соотношение RИЗБ ≥1—1 /Kcж.
Известные методы сжатия направлены на снижение избыточности, вызванной как неравной априорной вероятностью символов, так и зависимостью между порядком поступления символов. В первом случае для
кодирования исходных символов используется неравномерный код. Часто появляющиеся символы кодируются более коротким кодом, а менее вероятные (редко встречающиеся) — более длинным кодом.
Устранение избыточности, обусловленной корреляцией между символами, основано на переходе от кодирования отдельных символов к кодированию групп этих символов. За счет этого происходит укрупнение алфавита источника, так как число N тоже растет. Общая избыточность при укрупнении алфавита не изменяется. Однако уменьшение избыточности, обусловленной взаимными связями символов, сопровождается соответствующим возрастанием избыточности, обусловленной неравномерностью появления различных групп символов, то есть символов нового укрупненного алфавита. Происходит как бы конвертация одного вида избыточности в другой.
Таким образом, процесс устранения избыточности источника сообщений сводится к двум операциям — декорреляции (укрупнению алфавита) и кодированию оптимальным неравномерным кодом.
Сжатие бывает с потерями и без потерь. Потери допустимы при сжатии (и восстановлении) некоторых специфических видов данных, таких как видео и аудиоинформация. По мере развития рынка видеопродукции и систем мультимедиа все большую популярность приобретает метод сжатия с потерями MPEG 2 (Motion Pictures Expert Group), обеспечивающий коэффициент сжатия до 20:1. Если восстановленные данные совпадают с данными, которые были до сжатия, то имеем дело со сжатием без потерь. Именно такого рода методы сжатия применяются при передаче информации в СПД.
На сегодняшний день существует множество различных алгоритмов сжатия данных без потерь, подразделяющихся на несколько основных групп.
Кодирование повторов (Run-Length Encoding, RLE).
Этот метод является одним из старейших и наиболее простым. Он применяется в основном для сжатия графических файлов. Самым распространенным графическим форматом, использующим этот тип сжатия, является формат PCX. Один из вариантов метода RLE предусматривает замену последовательности повторяющихся символов на строку, содержащую этот символ, и число, соответствующее количеству его повторений. Применение метода кодирования повторов для сжатия текстовых или исполняемых (*.ехе, *.соm) файлов оказывается неэффективным. Поэтому в современных системах связи алгоритм RLE практически не используется.
Вероятностные методы сжатия
В основе вероятностных методов сжатия (алгоритмов Шеннона-Фано (Shannon Fano) и Хаффмена (Huffman)) лежит идея построения "дерева", положение символа на "ветвях" которого определяется частотой его появления. Каждому символу присваивается код, длина которого обратно пропорциональна частоте появления этого символа. Существуют две разновидности вероятностных методов, различающих способом определения вероятности появления каждого символа:
Ø статические (static) методы, использующие фиксированную таблицу частоты появления символов, рассчитываемую перед началом процесса сжатия;
Ø динамические (dinamic) или адаптивные (adaptive) методы, в которых частота появления символов все время меняется и по мере считывания нового блока данных происходит перерасчет начальных значений частот.
Статические методы характеризуются хорошим быстродействием и не требуют значительных ресурсов оперативной памяти. Они нашли широкое применение в многочисленных программах-архиваторах, например ARC, PKZIP и др., но для сжатия передаваемых модемами данных используются редко — предпочтение отдается арифметическому кодированию и методу словарей, обеспечивающим большую степень сжатия.
Арифметические методы
Принципы арифметического кодирования были разработаны в конце 70-х годов В результате арифметического кодирования строка символов заменяется действительным числом больше нуля и меньше единицы. Арифметическое кодирование позволяет обеспечить высокую степень сжатия, особенно в случаях, когда сжимаются данные, где частота появления различных символов сильно варьируется. Однако сама процедура арифметического кодирования требует мощных вычислительных ресурсов, и до недавнего времени этот метод мало применялся при сжатии передаваемых данных из-за медленной работы алгоритма. Лишь появление мощных процессоров, особенно с RISC-архитектурой, позволило создать эффективные устройства арифметического сжатия данных.
Реферат опубликован: 31/07/2007