Сделай Сам Свою Работу на 5

Сжатие способом кодирования серий (RLE)

Наиболее известный простой подход и алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE). Это самый простой из методов упаковки информации. Предположите, что вы имеете строку текста, и в конце строки стоит 40 пробелов. Налицо явная избыточность имеющейся информации. Проблема сжатия этой строки решается очень просто - эти 40 пробелов (40 байт) сжимаются в 3 байта с помощью упаковки их по методу повторяющихся символов (running). Первый байт, стоящий вместо 40 пробелов в сжатой строке, фактически будет являться пробелом, (последовательность была из пробелов). Второй байт - байт счета (в нашем случае это будет 40). Как вы сами можете видеть, достаточно, чтобы любой раз, когда мы имеем последовательность из более 3-х одинаковых символов, заменять их вышеописанной последовательностью, чтобы на выходе получить блок информации меньший по размеру, но допускающий восстановление информации в исходном виде.

Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений.

Например:
44 44 44 11 11 11 11 11 01 33 FF 22 22 - исходная последовательность
03 44 04 11 00 03 01 03 FF 02 22 - сжатая последовательность

Первый байт указывает сколько раз нужно повторить следующий байт.

Если первый байт равен 00, то затем идет счетчик, показывающий, сколько за ним следует неповторяющихся данных.

Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов.

Недостатком метода RLE является достаточно низкая степень сжатия.

 

Алгоритм Хаффмана

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

Если мы будем учитывать все 256 символов, то для нас не будет разницы в сжатии текстового и EXE файла.



После подсчета частоты вхождения каждого символа, необходимо просмотреть таблицу кодов ASCII и сформировать бинарное дерево.

Пример:

Мы имеем файл длиной в 100 байт и имеющий 6 различных символов в себе. Мы подсчитали вхождение каждого из символов в файл и получили следующее :

Символ A B C D E F
Число вхождений

 

Теперь мы берем эти числа и будем называть их частотой вхождения для каждого символа.

Символ C E B F A D
Число вхождений

 

Мы возьмем из последней таблицы 2 символа с наименьшей частотой. В нашем случае это D (5), и какой-либо символ из F или A (10), можно взять любой из них, например A.

Сформируем из "узлов" D и A новый "узел", частота вхождения для которого будет равна сумме частот D и A :

Номер в рамке - сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исключем из просмотра D и A и рассматриваем вместо них новый "узел" с суммарной частотой вхождения. Самая низкая частота теперь у F и нового "узла". Снова сделаем операцию слияния узлов :

Рассматриваем таблицу снова для следующих двух символов (B и E).

Мы продолжаем в эту процедуру пока все "дерево" не сформировано, т.е. пока все не сведется к одному узлу.

Теперь, когда наше дерево создано, мы можем кодировать файл. Мы должны всегда начинать из корня (Root). Кодируя первый символ (лист дерева С), мы прослеживаем вверх по дереву все повороты ветвей, и, если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так, для C мы будем идти влево к 55 (и запомним 0), затем снова влево (0) к самому символу. Код Хаффмана для нашего символа C - 00. Для следующего символа ( А ) у нас получается - влево, вправо, влево, влево, что выливается в последовательность 0100. Выполнив выше сказанное для всех символов, получим:

C = 00 (2 бита)
A = 0100 (4 бита)
D = 0101 (4 бита)
F = 011 (3 бита)
B = 10 (2 бита)
E = 11 (2 бита)

При кодировании заменяем символы данными последовательностями. Достоинствами метода Хаффмана являются его достаточно высокая скорость и хорошее качество сжатия. Этот алгоритм сравнительно давно известен и широко применяется; примерами могут служить программа compress ОС UNIX (программная реализация) и стандарт кодирования для факсов [Hunter] (аппаратная реализация).

Кодирование Хаффмана имеет минимальную избыточность при условии, что каждый символ кодируется отдельной цепочкой в алфавите {0,1}). Недостатком кодирования Хаффмена является зависимость степени сжатия от близости вероятностей символов к отрицательным степеням 2; это связано с тем, что каждый символ кодируется *целым* числом бит. Наиболее ярко это проявляется при кодировании двухсимвольного алфавита: в этом случае сжатие *всегда* отсутствует, несмотря на различие вероятностей символов; алгоритм фактически "округляет" их до 1/2!Эта проблема может быть частично решена за счет блокирования входного потока (т.е. введения в рассмотрение новых символов вида 'ab', 'abc', ... где a, b, c -- символы исходного алфавита). Однако это не позволяет полностью избавиться от потерь (они лишь уменьшаются пропорционально размеру блока) и приводит к резкому росту кодового дерева: если, например, символами входного алфавита являются 8-битовые байты со значениями 0 .. 255, то при блокировании по два символа мы получаем 65536 символов (и столько же листьев кодового дерева), а при блокировании по три -- 16777216! Соответственно возрастут требования к памяти и время построения дерева (а при адаптивном кодировании – и время обновления дерева, а значит, и время сжатия). Потери же составят в среднем 1/2 бита на символ при отсутствии блокирования, а при его наличии -- 1/4 и 1/6 бита соответственно для блоков длин 2 и 3.Большую степень сжатия, не зависящую от близости значений вероятности символов к степеням 1/2, может дать так называемое арифметическое кодирование.

 



©2015- 2017 stydopedia.ru Все материалы защищены законодательством РФ.