2. Эффективное Кодирование

2.1. Алгоритмы построения эффективных кодов

Метод Шеннона

1. Все имеющиеся сообщений располагают в один столбик в порядке убывания вероятностей.

2. Затем упорядоченные сообщения разбивают на две группы (верхнюю и нижнюю) так, чтобы суммарные вероятности этих групп были по возможности ближе друг к другу.

3. Для сообщений верхней группы в качестве первого символа кодового слова используется «1», а для нижней - «0».

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

5. В качестве второго символа кодового слова используется «1» или «0» в зависимости от принадлежности сообщений к верхней или нижней подгруппе и т.д.

Данный процесс продолжается до тех пор, пока подгруппа не будет состоять из единственного сообщения.

Метод Хаффмена

1. Все имеющиеся сообщений располагают в один столбик в порядке убывания вероятностей.

2. Затем два самых маловероятных сообщения объединяют в одно сообщение , которое имеет вероятность . В результате получают сообщения , вероятности которых . Эти сообщения вновь располагают в порядке убывания вероятностей.

3. Далее берут два сообщения, имеющие наименьшие вероятности, объединяют их в одно и вычисляют их общую вероятность.

4. Шаги 2 и 3 повторяют до тех пор, пока не получат единственное сообщение, вероятность которого равна единице.

5. Проводя линии, объединяющие сообщения и образующие последовательные подмножества, получают дерево, в котором отдельные сообщения являются концевыми узлами. Соответствующие им кодовые слова можно построить, приписывая ветви, которые идут вниз - «0», а вверх - «1».

Арифметическое кодирование

При арифметическом кодировании каждый символ исходного текста представляется отрезком на числовой оси с длиной, равной вероятности его появления, и началом, совпадающим с концом отрезка символа, предшествующего ему в алфавите. Результатом арифметического кодирования является некоторая двоичная дробь из интервала [0, 1).

Пример. Закодировать сообщение «аава».

Вероятность р(а)=3/4; р(b)=1/4.

Пустому слову соответствует весь интервал [0, 1). После получения каждого очередного символа арифметический кодер уменьшает интервал, выбирая ту его часть, которая соответствует вновь поступившему символу.

Процесс кодирования пояснен на рис. 2.1 с учетом табл. 2.1.

Интервал [0, 1) разбивается на части, длина которых пропорциональна вероятностям символов.

На первом шаге берутся первые 3/4 интервала, соответствующие символу “а”. На втором шаге от предыдущего интервала оставляют еще 3/4, соответствующие второму символу “а”. После третьего шага от предыдущего интервала останется его правая четверть в соответствии с положением и вероятностью символа ”b”. На четвертом шаге оставляют лишь первые 3/4 от результата.

Рис.2.1

Таблица 2.1

Шаг	Просмотренная цепочка	Интервал (в десятичной форме)	Интервал (в двоичной форме)
0	“”	[0, 1)	[0, 1)
1	“a”	[0, 3/4)	[0, 0.11)
2	“aa”	[0, 9/16)	[0, 0.1001)
3	“aab”	[27/64, 36/64)	[0.011011, 0.100100)
4	“aaba”	[108/256, 135/256)	[0.01101100, 0.10000111)

В качестве кода можно взять любое число из диапазона, полученного на шаге 4. Например, .

Метод Лемпеля-Зива

1. Последовательность с выхода дискретного источника делятся на блоки переменной длины, которые называются фразами.

2. Каждая новая фраза должна отличаться от всех предыдущих и в одном символе от одной из предыдущих фраз.

3. Все фразы записываются в словарь, который сохраняет расположение существующих фраз.

4. Кодовые слова состоят из двух частей. Первая часть представляет собой номер словаря в двоичной форме предыдущей фразы, которая соответствует новой фразе, кроме последнего символа. Вторая часть – это новый символ, выданный источником. Первоначальный номер ячейки словаря 0000 используется, чтобы кодировать пустую фразу, т. е. «0» или «1».

Пример. Пусть дискретный источник выдает последовательность

111000111111.

Последовательность символов делится на фразы:

Номера ячеек словаря, фразы и полученные кодовые слова приведены в табл. 2.2.

Таблица 2.2

Расположение в словаре	Фразы	Кодовое слово
0001	1	0000 0
0010	11	0001 1
0011	0	0000 0
0100	00	0011 0
0101	111	0010 1
0110	1110	0101 0

Метод Лемпеля-Зива-Велча

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

2. Фразы закрепляются за определенным номером словаря.

3. Выходной код формируется следующим образом:

- если фраза состоит из двух символов, то выходной код соответствует первому символу фразы (левому);

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

Пример. Пусть на вход кодера поступает последовательность символов: 1110001111110.

Последовательность символов делится на фразы:

Фразы закрепляются за номером ячейки словаря. Полученные кодовые слова приведены в табл. 2.3.

Таблица 2.3

Расположение в словаре	Фразы	Кодовое слово
001	11	1
010	110	001
011	00	0
100	001	011
101	111	001
110	1111	101
111	10	1
END	-	0