Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
Донской государственный технический университет
Кафедра ПОВТ и АС
Методы сжатия информации.
Алгоритмы Хаффмана и Лемпеля-Зива.
Методические указания к практическим занятиям по курсу
«Теория информации»
Ростов-на-Дону
2008
Составитель Н.С. Могилевская
Методы сжатия информации. Алгоритмы Хаффмана и Лемпеля-Зива. Методические указания по курсу «Теория информации». / Ростов – на – Дону: Издательский центр ДГТУ, 2008, 14 с.
Методические указания предназначены для студентов специальности 090102 «Компьютерная безопасность» и преподавателей, ведущих практические занятия по курсу «Теория информации»; в них содержатся краткие сведения об идеях сжатия информации, способах оценки эффективности сжатия, представлены алгоритм Хаффмана и две модификации алгоритма Лемпеля-Зива.
Печатается по решению методической комиссии факультета «Автоматизация и информатика».
Рецензент: заведующий кафедрой «Математика» ДГТУ, канд. физ.-мат. наук Г. Ю. Рябых
Издательский центр ДГТУ, 2008.
Кодирование источника
Задачей сжатия данных является минимизация технических затрат на хранение или передачу данных путем оптимального кодирования источников [1, стр. 75]. Согласно классической схеме системы связи [1, 2], сжатие данных, т.е. более компактное их представление производится в кодере источника, а задачей декодера источника является соответственно восстановление сжатых данных.
Используя материалы [1-3], укажем основные понятия, связанные с задачей сжатия данных.
Несущественная информация - это информация, которой можно пренебречь при передаче. Например, телефонная связь использует полосу частот в диапазоне 3,4 кГц. Все остальные спектральные составляющие речи отбрасываются, при этом существенная часть информации теряется. Ясно, что первоначальный сигнал не может быть восстановлен полностью. В этом случае говорят о кодировании с потерями.
Избыточная информация - неоднократное повторение в сообщении необходимой для приемника информации. Избыточность может быть устранена без потери информации. Если алгоритм кодирования отбрасывает только избыточную информацию, то говорят о кодировании без потерь.
Степень сжатия определяется затратами для передачи или хранения информации без сжатия и затратами с использованием некоторого метода сжатия
.
Степень сжатия зависит от используемого алгоритма и свойств источника.
Средняя длина кода вычисляется как сумма длин двоичных кодов, взвешенных вероятностью этих кодовых символов:
Коэффициент сжатия, определяющий эффективность сжатия, задается, как отношение числа бит на выборку до сжатия к среднему числу бит на выборку после сжатия.
Коды сжатия можно классифицировать как коды фиксированной и переменной длины, префиксные и непрефиксные коды.
Перечислим, согласно [2], желаемые свойства полезных кодов источника.
2. Алгоритм Хаффмана
Код Хаффмана – это свободный от префикса код, который может давать самую короткую среднюю длину кода для данного входного алфавита. Заметим, что самая короткая средняя длина кода для конкретного алфавита может быть значительно больше энтропии алфавита источника. Алгоритм кодирования Хаффмана может применяться для преобразования между двумя любыми алфавитами, чаще всего его используют для преобразования произвольного алфавита в двоичный [2].
Рассмотрим работу алгоритма Хаффмана на примере.
Пример. Построить двоичный код Хаффмана для представленного в таблице алфавита. В таблице использованы следующие обозначения Xi – i-тый символ алфавита, Р(Xi) – вероятность появления символа Xi.
|
Xi |
а |
b |
с |
d |
|
Р(Xi) |
0,12 |
0,3 |
0,38 |
0,2 |
Упорядочим символы алфавита по убыванию вероятностей их появления и сопоставим их ветвям двоичного дерева.
Два входа с самой низкой относительной частотой объединим в новую ветвь. Вероятность, соответствующую этой ветви вычислим как сумму вероятностей объединенных ветвей. После объединения переупорядочим все ветви дерева таким образом, чтобы в дереве сохранялась убывающая вероятность ветвей. В случае, когда необходимо построить выходной алфавит не двоичным, а например m-ичным, то необходимо объединять ветви дерева по m штук, которым соответствуют наименьшие значения вероятностей.
Будем продолжать этот процесс до достижения корня дерева.
После формирования всего дерева пометим ветви, выходящие из всех вершин символами “0” и “1”. Помечать ветви дерева можно произвольным образом, для определенности ветвь, идущую вверх будем помечать символом “1”, а ветвь, идущую вниз – символом “0”.
После обозначения вершин пройдем все возможные пути по дереву от вершины (крайнее правое положение) дерева до его каждой выходной ветви (крайнее левой положение), запоминая встретившиеся двоичные символы. Полученные последовательности будут являться кодами символов входного алфавита.
Значения, характеризующие построенный код Хаффмана, сведем в таблицу следующего вида. В первом столбце перечислим все символы алфавита (Xi); во втором столбце расположим соответствующие вероятности появления символов входного алфавита Р(Xi); в третьем столбце запишем кодовые слова, соответствующие символам входного алфавита; в последнем – четвертом столбце поместим значения .
|
Xi |
Р(Xi) |
Код |
Длина кода, , бит |
|
|
с |
0,38 |
0 |
1 |
0,38 |
|
b |
0,3 |
10 |
2 |
0,6 |
|
d |
0,2 |
111 |
3 |
0,6 |
|
a |
0,12 |
110 |
3 |
0,36 |
Среднюю длину кода вычислим по формуле:
.
Результирующее значение =1,94 бит на знак, что не означает, что для передачи одного символа необходимо передавать нецелое число бит, а означает, что для передачи 100 входных символов из алфавита мощностью 4 потребуется примерно 194 бита.
2. Идеи построения алгоритма сжатия Лемпеля-Зива
Существует большое количество модификаций алгоритма Лемпеля-Зива [1, 3], все модификации этого алгоритма основаны на принципе динамических словарей. Перечислим основные идеи, на которых базируется алгоритм Лемпеля-Зива.
1. Каждая очередная закодированная последовательность символов добавляется к раннее закодированным символам таким образом, что вместе с ними она образует разложение всей принятой и переданной информации на несовпадающие между собой фразы. Такое разложение хранится в памяти и используется в дальнейшем в качестве словаря.
2. Кодирование осуществляется при помощи указателей на фразы из уже сформированного словаря фраз. Кодирование является динамической процедурой, ориентированной на блоки. Сам процесс кодирования может быть дополнен скользящими окнами, содержащими текущий словарь фраз, и Look-ahead буфером.
3.1. Zip–модификация алгоритма Лемпеля-Зива
Согласно [3] процесс кодирования начинается с пустого словаря, так что первые элементы являются позициями, которые не ссылаются на более ранние позиции. В словаре рекуррентно формируется выполняемая последовательность адресов. Каждому адресу соответствует последовательность из элементов алфавита. Закодированные данные хранятся в виде пакетов со следующей структурой:
<ссылка на адрес словаря, следующий знак данных>.
Каждый новый входной элемент словаря образован как пакет, содержащий адрес того словаря, за которым следует следующий символ. Код предполагает, что существующий словарь содержит уже закодированные сегменты последовательности символов алфавита. Данные кодируются с помощью просмотра существующего словаря для согласования со следующим сегментом кодируемой последовательности. Если согласование найдено, то так как получатель уже имеет этот сегмент кода в памяти, то нет необходимости пересылать его вновь, требуется только определить адрес, чтобы найти сегмент. Код ссылается на расположение последовательности сегмента в памяти, затем дополняет следующий символ в последовательности, чтобы образовать новую позицию в словаре кода.
Пример. Используя Zip–модификацию алгоритма Лемпеля-Зива, закодировать последовательность
abaababbbbbbbabbbba. (*)
Результат кодирования будем записывать в таблицу, содержащую три строки. В первой строке – адрес пакета данных, во второй – пакет данных в виде <адрес словаря, следующий знак данных>, в третьей – содержимое текущего пакета данных.
На начальном этапе работы алгоритма динамически формируемый словарь пуст. Пока словарь пуст, будем просматривать кодируемую фразу посимвольно и кодировать отдельные символы, по мере заполнения словаря будем пытаться кодировать в один пакет данных несколько подряд идущих символов.
Сформируем первый пакет данных и добавим его в словарь. Первый символ кодируемой последовательности (*) – «а» запишем по первому адресу. Пакет данных будет иметь вид: <0,a>. При формировании текущего пакета данных не используется ссылка на содержимое других позиций словаря, поэтому первый элемент пакета данных равен нулю, значение следующего знака данных равно «а», – символу, который необходимо записать в словарь.
Адрес: 1
Пакет данных: <0,a>
Содержимое: а.
Второй символ кодируемой последовательности (*) – «в» запишем по второму адресу. Пакет данных будет иметь вид: <0,в>. При формировании этого пакета данных также не используется ссылка на содержимое других позиций словаря, поэтому первый элемент пакета данных равен нулю, а значение следующего знака данных равно «в», – символу, который необходимо записать в словарь.
Адрес: 2
Пакет данных: <0,в>
Содержимое: в.
Просматриваем далее входную последовательность abaababbbbbbbabbbba. Будем отмечать в ней подчеркиванием уже закодированные символы. Следующий из незакодированных символов – «а» уже встречался в словаре, поэтому теперь в один пакет запишем объединение этого символа со следующим
Адрес: 3
Пакет данных: <1,а>
Содержимое: аа.
Запись <1,а> в пакете данных означает, что необходимо взять символ(ы) записанные по адресу 1 и добавить к ним символ «а». Далее будем аналогичным образом продолжать процесс кодирования, каждый раз просматривая динамически формируемый словарь справа налево, т.е. с последней записи к первой. Оформим процесс кодирования в таблицу.
|
Адрес |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
Пакет данных |
<0,a> |
<0,b> |
<1,a> |
<2,a> |
<2,b> |
<5,b> |
<5,a> |
<6,b> |
<1,-> |
|
Содер-жимое |
a |
b |
aa |
ba |
bb |
bbb |
bba |
bbbb |
a |
Обратите внимание, что последний пакет данных, записанный по адресу 9, не содержит знака данных
3.2. LZW-модификация алгоритма Лемпеля-Зива
Эта модификация отличается от рассмотренной ранее Zip–модификации структурой пакета данных. Концепция адреса не используется, наоборот имеются ссылки предшествующие последовательности данных, а также допускаются рекуррентные ссылки на параметр длины. Пакет данных формируется из трех значений: <А, В, С>, первые два из которых указывают на уже закодированную подпоследовательность данных, следующим образом: число А указывает на сколько знаков необходимо отступить назад, чтобы найти начало нужной подпоследовательности, В – длина подпоследовательности которую необходимо считать, С – следующий знак.
Пример. Используя LZW–модификацию алгоритма Лемпеля-Зива, закодировать последовательность
abaababbbbbbbabbbba. (**)
|
Пакет данных |
<0,0,a> |
<0,0,b> |
<2,1,a> |
<3,2,b> |
<1,1,b> |
<3,3,b> |
<8,5,a> |
|
Содер-жимое пакета |
A |
b |
aa |
bab |
bb |
bbbb |
bbbb |
|
Уже Закоди-рованный текст |
a |
ab |
abaa |
Aba abab |
Aba ababbb |
Abaaba bbbbbbb |
AbAa bab bbbbbb |
Для кодирования алгоритмом Лемпеля-Зива установлено, что [1, стр. 83]:
Контрольные вопросы
|
Xi |
А |
В |
С |
|
Р(Xi) |
0,73 |
0,25 |
0,02 |
Для данного алфавита построены следующие шесть вариантов кодов.
|
Символ |
Код 1 |
Код 2 |
Код 3 |
Код 4 |
Код 5 |
Код 6 |
|
А |
00 |
00 |
0 |
1 |
1 |
1 |
|
В |
00 |
01 |
1 |
10 |
00 |
01 |
|
С |
01 |
10 |
11 |
100 |
01 |
11 |
Изучите предлагаемые коды и определите, какие коды являются практичными.
Упражнения для самостоятельного выполнения
1. Закодируйте предложенную фразу рассмотренными выше ZIP и LZW-модификациями алгоритма Лемпеля-Зива.
|
Номер варианта |
Последовательность для кодирования |
|
1 |
12112323212123333333 |
|
2 |
ABAABAABBBAABBBB |
|
3 |
WWQEWQEEWWEQEWW |
|
4 |
1212231223311213 |
|
5 |
АВСВСВАВСААВАВСС |
|
6 |
SPSPPQQPPQQQSPSQ |
|
7 |
3331211233323332223 |
|
8 |
12323332331231122333 |
|
9 |
ЩФЫФЫФЩФЫЩЩФЩФЫЫ |
|
10 |
YXZYXZZZXXYXYXXYXY |
|
11 |
ZZXXYXZYXZZXXZYYYY |
|
12 |
22311232231123123321 |
|
13 |
ЭЮЭЮЮЯЭЮЮЯЯЭЭЮЭЯ |
|
14 |
ЭЮЯЭЮЯЯЯЭЭЯЭЮЯЭЮЯ |
|
15 |
QWEQWEQQWWEEWQWEQWE |
|
16 |
ABCABCACCABBBB |
|
17 |
SRPRPRPSRSSPPRSRR |
|
18 |
12312313312222 |
|
19 |
EQWQWQQEQWQQEWQE |
|
20 |
EEWQEWEEWQQWEEWE |
2. Для указанного входного алфавита, мощностью 5 элементов дважды постройте код Хаффмана для выходных алфавитов различной мощности. Вычислите средние длины построенных кодов. Сравните значения энтропии исходного кода и среднюю длину кода.
|
Номер варианта |
P(a) |
P(b) |
P(c ) |
P(d) |
P(e) |
P(f) |
Мощность нового алфавита |
|
1 |
0,16 |
0,32 |
0,27 |
0,05 |
0,19 |
0,01 |
2, 3 |
|
2 |
0,64 |
0,15 |
0,03 |
0,06 |
0,08 |
0,04 |
2, 4 |
|
3 |
0,09 |
0,01 |
0,17 |
0,32 |
0,23 |
0,18 |
2, 3 |
|
4 |
0,12 |
0,35 |
0,05 |
0,1 |
0,1 |
0,28 |
2, 4 |
|
5 |
0,08 |
0,47 |
0,12 |
0,1 |
0,1 |
0,13 |
2, 3 |
|
6 |
0,44 |
0,01 |
0,34 |
0,1 |
0,1 |
0,01 |
2, 3 |
|
7 |
0,01 |
0,34 |
0,37 |
0,03 |
0,1 |
0,15 |
2, 4 |
|
8 |
0,34 |
0,4 |
0,06 |
0,1 |
0,05 |
0,05 |
2, 3 |
|
9 |
0,01 |
0,65 |
0,12 |
0,1 |
0,04 |
0,08 |
2, 4 |
|
10 |
0,21 |
0,01 |
0,45 |
0,1 |
0,1 |
0,13 |
2, 3 |
|
11 |
0,34 |
0,04 |
0,12 |
0,1 |
0,1 |
0,3 |
2, 4 |
|
12 |
0,29 |
0,37 |
0,08 |
0,1 |
0,1 |
0,06 |
2, 3 |
|
13 |
0,12 |
0,02 |
0,24 |
0,1 |
0,1 |
0,42 |
2, 4 |
|
14 |
0,07 |
0,45 |
0,01 |
0,1 |
0,1 |
0,27 |
2, 3 |
|
15 |
0,06 |
0,12 |
0,58 |
0,1 |
0,1 |
0,04 |
2, 4 |
|
16 |
0,14 |
0,37 |
0,08 |
0,1 |
0,1 |
0,21 |
2, 3 |
|
17 |
0,03 |
0,1 |
0,05 |
0,1 |
0,1 |
0,62 |
2, 4 |
|
18 |
0,03 |
0,17 |
0,34 |
0,1 |
0,1 |
0,26 |
2, 3 |
|
19 |
0,31 |
0,11 |
0,35 |
0,1 |
0,1 |
0,03 |
2, 4 |
|
20 |
0,33 |
0,11 |
0,36 |
0,01 |
0,1 |
0,09 |
2, 3 |
|
21 |
0,39 |
0,31 |
0,02 |
0,1 |
0,1 |
0,08 |
2, 4 |
|
22 |
0,12 |
0,02 |
0,32 |
0,1 |
0,1 |
0,34 |
2, 3 |
|
23 |
0,49 |
0,03 |
0,09 |
0,1 |
0,1 |
0,19 |
2, 4 |
|
24 |
0,21 |
0,22 |
0,03 |
0,1 |
0,1 |
0,34 |
2, 3 |
|
25 |
0,01 |
0,08 |
0,4 |
0,01 |
0,1 |
0,4 |
2, 4 |
Литература