Описание программы кодирования Хаффмана

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

Словарное сжатие – это методы сжатия, хранящие фрагменты данных в "словаре" (некоторая структура данных). Если строка новых данных, поступающих на вход, идентична какому-либо фрагменту, уже находящемуся в словаре, в выходной поток помещается указатель на этот фрагмент. Лучшие словарные методы применяют метод Зива-Лемпела.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.2 Методы  сжатия данных. Арифметическое кодирование

 

Компактное  представление информации — очень  важная проблема в областях, где  приходится работать со сжатием данных. Цель — сжатие потока R-битовых элементов. В общем случае никаких предположений о свойствах значений элементов не делается, поэтому можно говорить об описании способов представления целых чисел.

Арифметическое  кодирование известно сегодня как  один из наиболее эффективных методов  сжатия данных, который применим для большого класса источников информации. Основная идея арифметического кодирования была сформулирована Элайесом ещё в начале 60-х годов. Преимущество арифметического кода по отношению к другим методам заключается в том, что он позволяет достичь произвольно низкой избыточности на символ источника (избыточность – центральное понятие в теории сжатия информации. Любые данные с избыточной информацией можно сжать; в которых нет избыточности – сжать нельзя). Показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов.

Основная идея состоит в том, чтобы отдельно хранить порядок значения элемента X_i («экспоненту» E_i) и отдельно — значащие цифры значения («мантиссу» M_i).

Методы данной группы являются трансформирующими и поточными, то есть могут применяться даже в том случае, когда объем входных данных заранее не известен. В общем случае скорость работы компрессора (содержащего прямое, «сжимающее» преобразование) равна скорости декомпрессора (реализующего обратное, «разжимающее» преобразование) и зависит только от объема исходных данных. Памяти потребуется всего несколько байтов.

Существует  четыре варианта этого метода:

• Fixed+Fixed (фиксированная длина экспоненты – фиксированная длина мантиссы)
• Fixed+Variable (фиксированная длина экспоненты – переменная длина мантиссы)
• Variable+Variable (переменная длина экспоненты – переменная длина мантиссы)
• Variable+Fixed (переменная длина экспоненты – фиксированная длина мантиссы)

В данной работе будут рассмотрены коды переменной длины (Variable+Variable).

1)Унарный код

 

Унарный код сопоставляет числу i двоичную комбинацию вида 1 0.Запись вида 0 или 1 означает соответственно серию из m нулей или единиц. Например, унарными кодами чисел 1, 2, и 3 являются последовательности unar(1)=10, unar(2)=110 и unar(3)=1110 соответственно. Длина кодового слова для числа n равна l_n=n+1. На рисунке 1.1 приведен унарный код чисел от 0 до 6.

 

Рисунок 1.1 – Унарный код чисел от 0 до 6

 

Унарный код оптимален, если числа i распределены по геометрическому закону (1.1) с параметром = :

 

p =(1- ) ,      (1.1)

 

где i=1,2,

Для значений < более эффективен код Голомба.

 

2) Код Голомба

 

Коды Голомба  – это семейство энтропийных  кодеров, являющихся общим случаем  унарного кода. Кодирование энтропии- кодирование словами (кодами) переменной длины, при которой длина кода символа имеет обратную зависимость от вероятности появления символа в передаваемом сообщении. Обычно энтропийные кодировщики используют для сжатия данных коды, длины которых пропорциональны отрицательному логарифму вероятности символа. Таким образом, наиболее вероятные символы используют наиболее наиболее короткие коды. Согласно теореме Шеннона оптимальная длина кода для символа равна -log P, где b- это количество символов, используемых для изготовления выходного кода, и Р- вероятность входного символа. Унарный код – это энтропийное кодирование, которое представляет число n в виде n единиц с замыкающим нулем ( либо n нулей и единица). Например, 5 представляется в виде 111110. Унарное кодирование оптимально для распределения вероятности: P(x)=2 . Также под кодом Голомба может подразумеваться один из представителей этого семейства.

Код Голомба  позволяет представить последовательность символов в виде последовательности двоичных слов. Это представление будет оптимальным при условии, что распределение вероятности символов подчиняется геометрическому закону (1.2):

P(i) = (1-p)p , (1.2)

где i – номер символа, а р – параметр геометрического распределения. Также должно соблюдаться условие (1.3):

 

p = ,     (1.3)

 

где m – основной параметр кода Голомба.

Для кодирования символа  с номером n необходимо представить n в виде (1.4):

 

n = qm + r,     (1.4)

 

где q и r – целые положительные числа, 0 r < m.Затем r кодируется унарным кодом, а q – бинарным. Полученные двоичные последовательности объединяются в результирующее слово.

Пример: Основной параметр кода m=4, кодируемое число n=13 .

• Частное q= = =3;
• унарный код q – 1110;
• остаток r=n mod m=13 mod 4=1;
• бинарный код r – 01;
• результирующее кодовое слово – 111001.

Рассмотрим  несколько примеров кодов Голомба  для различного параметра m в таблице 1.1:

 

Таблица 1.1 –  Коды Голомба для различных параметров m

n\ m	1	2	3	4	5
0	0	00	00	000	000
1	10	01	010	001	001
2	110	100	011	010	010
3	1110	101	100	011	0110
4	11110	1100	1010	1000	0111
5	111110	1101	1011	1001	1000
6	1111110	11100	1100	1010	1001
7	11111110	11101	11010	1011	1010
8	111111110	111100	11011	11000	10110
9	1111111110	111101	11100	11001	10111
10	11111111110	1111100	111010	11010	11000
11	111111111110	1111101	111011	11011	11001
12	1111111111110	11111100	111100	111000	11010
13	11111111111110	11111101	1111010	111001	110110
14	111111111111110	111111100	1111011	111010	110111
15	1111111111111110	111111101	1111100	111011	111000
16	11111111111111110	1111111100	11111010	1111000	111001
17	111111111111111110	1111111101	11111011	1111001	111010

 

Ниже приводится рисунок 1.2, поясняющий устройство данных кодов: как именно двоичное представление  остатка следует за унарным кодом :

 

Рисунок 1.2 –  Формирование кодов Голомба

 

3) Код Райса

 

Код Райса идентичен  коду Голомба, когда m является степенью двойки. На самом деле данные коды имеют параметр k, по которому вычисляется значение m = 2^k.

Введем параметр Т=2 . Код Райса для числа n состоит из двух частей. Первая часть – унарный код числа [ ], вторая часть – двоичная запись в виде последовательности длины k остатка от деления n на T. Очевидно, длина кода Райса для числа n равна l_n=[ ]+1+k. Например, при k=3 и n=21 имеем [ ]=2, остаток равен 5. Поэтому кодом Райса числа 21 будет последовательность 110101.

Рассмотрим  несколько примеров кодов Райса  для различных параметров k, которые  представлены в таблице 1.2:

 

Таблица 1.2 –  Коды Райса для различных параметров k

n\ k	1	2	3	4	5	6
0	0	000	0000	00000	000000	0000000
1	10	001	0001	00001	000001	0000001
2	110	010	0010	00010	000010	0000010
3	1110	011	0011	000011	000011	0000011
4	11110	1000	0100	000100	000100	0000100
5	111110	1001	0101	000101	000101	0000101
6	1111110	1010	0110	000110	000110	0000110
7	11111110	1011	0111	000111	000111	0000111
8	111111110	11000	10000	001000	001000	0001000
9	1111111110	11001	10001	001001	001001	0001001
10	11111111110	11010	10010	001010	001010	0001010
11	111111111110	11011	10011	001011	001011	0001011
12	1111111111110	111000	10100	001100	001100	0001100
13	11111111111110	111001	10101	001101	001101	0001101
14	111111111111110	111010	10110	001110	001110	0001110
15	1111111111111110	111011	10111	001111	001111	0001111

 

Код Райса –  это частный случай кода Голомба, это легко увидеть из таблицы 1.3, представленной ниже:

 

 

Таблица 1.3 –  Сравнительная таблица кода Райса  и кода Голомба

Код Голомба	m=1	m=2	m=3	m=4	m=5	m=6	m=7	m=8
Код Райса	k=0	k=1		k=2				k=3
n=1	0	00	00	000	000	000	000	0000
2	10	01	010	001	001	001	0010	0001
3	110	100	011	010	010	0100	0011	0010
4	1110	101	100	011	0110	0101	0100	0011
5	11110	1100	1010	1000	0111	0110	0101	0100
6	111110	1101	1011	1001	1000	0111	0110	0101
7	1111110	11100	1100	1010	1001	1000	0111	0110
8	…	11101	11010	1011	1010	1001	1000	0111
9	…	111100	11011	11000	10110	10100	10010	10000

 

4) Коды Фибоначчи

 

Самые интересные, нетривиальные  коды. В данном кодировании исходное число n раскладывается в сумму чисел  Фибоначчи f_i (f₁ = 1; f₂ = 2; f_i = f_i−1 + f_i−2). Известно, что любое натуральное число однозначно представимо в виде суммы чисел Фибоначчи. Поэтому можно построить код числа как последовательность битов, каждый из которых указывает на факт наличия в n определенного числа Фибоначчи.

Заметим также, что если в разложении числа n присутствует f_i, то в этом разложении не может быть числа f_i+1. Поэтому логично для конца кода использовать дополнительную единицу. Тогда две идущие подряд единицы будут означать окончание кодирования текущего числа.

Рассмотрим несколько  примеров кодов Фибоначчи в таблице 1.4:

 

Таблица 1.4 – Примеры кода Фибоначчи

n\f	1	2	3	5	8	13	21	34
1	1	(1)
2	0	1	(1)
3	0	0	1	(1)
4	1	0	1	(1)
5	0	0	0	1	(1)
6	1	0	0	1	(1)
7	0	1	0	1	(1)
8	0	0	0	0	1	(1)
…	…	…	…	…	…	…
12	1	0	1	0	1	(1)
13	0	0	0	0	0	1	(1)
…	…	…	…	…	…	…	…
20	0	1	0	1	0	1	(1)
21	0	0	0	0	0	0	1	(1)