- •Глава 3. Кодирование символьной информации
- •3.1. Постановка задачи кодирования. Первая теорема Шеннона
- •3.2. Способы построения двоичных кодов 3.2.1. Алфавитное неравномерное двоичное кодирование сигналами равной длительности. Префиксные коды
- •3.2.2. Равномерное алфавитное двоичное кодирование. Байтовый код
- •3.2.3. Алфавитное кодирование с неравной длительностью элементарных сигналов. Код Морзе
- •3.2.4. Блочное двоичное кодирование
- •Глава 6. Кодирование
- •6.1 Алфавитное кодирование
- •6.1.1. Префикс и постфикс слова
- •6.1.2. Таблица кодов
- •6.1.3. Разделимые схемы
- •6.1.4. Префиксные схемы
- •6.1.5. Неравенства Макмиллана
- •6.2. Кодирование с минимальной избыточностью
- •6.2.1. Минимизация длины кода сообщения
- •6.2.2. Цена кодирвания
- •6.2.3. Алгоритм Фано
- •6.2.4. Оптимальное кодирование
- •6.2.5. Алгоритм Хаффмана
- •6.3. Помехоустойчивое кодирование
- •6.3.1. Кодирование с исправлением ошибок
- •6.3.2. Классификация ошибок
- •6.3.3. Возможность исправления всех ошибок
- •6.3.4. Кодовое расстояние
6.2.5. Алгоритм Хаффмана
Следующий рекурсивный алгоритм строит схему оптимального префиксного алфавитного кодирования для заданного распределения вероятностей появления букв.
Алгоритм 6.2. Построение оптимальной схемы – рекурсивная процедура Huffman
Вход: n – количество букв, P : array [1..n] of real – массив вероятностей букв, упорядоченный по убыванию.
Выход: C : array [1..n,1..L] of 0..1 – массив элементарных кодов, l : array [1..n] of 1..L – массив длин элементарных кодов схемы оптимального префиксного кодирования.
if n=2 then
C [1, 1] := 0; l[1] := 1; { первый элемент }
C [2, 1] := 1; l[2] := 1; { Второй элемент }
else
q := P[n-1]+P[n] { сумма двух последних вероятностей }
j := Up (n, q) { поиск места и вставка суммы }
Huffman (P, n-1) { рекурсивный вызов }
Down (n, j) { достраивание кодов }
End if
Функция Up находит в массиве P место, в котором должно находиться число q (см. предыдущий алгоритм) и вставляет это число, сдвигая вниз остальные элементы.
Вход: n – длина обрабатываемой части массива p, q – вставляемая сумма.
Выход: измененный массив P.
for I from n-1 downto 2 do
if P [i-1] <= q then
P[i] := P[i-1] { сдвиг элемента массива }
else
j:=i-1 { определение места вставляемого элемента }
exit for I { все сделано – цикл не нужно продолжать }
end if
end for
P[j] := q;
return j
Процедура Down строит оптимальный код для n букв на основе построенного оптимального кода для n-1 буквы. Для этого код буквы с номером j временно исключается из массива C путем сдвига вверх кодов букв с номерами, большими j, а затем в конец обрабатываемой части массива С добавляется пара кодов, полученных из кода буквы с номером j удлинением на 0 и 1, соответственно. Здесь C[I,*] означает вырезку из массива, то есть i-ю строку массива С.
Вход: n – длина обрабатываемой части массива P, j – номер «разделяемой» буквы.
Выход: оптимальные коды в первых n элементах массивов С и l.
c := C [j, *] { запоминание кода буквы j }
l := l[j] { и длины этого кода }
for i from j to n-2 do
C[I,*]:=C[i+1,*] { сдвиг кода }
l[i] := l[i+1] { и его длины }
end for
C[n-1,*]:=c; C[n,*] := c { копирование кода буквы j }
C[n-1,l+1]:=0; C[n, l+1] := 1 { наращивание кодов }
L[n-1] := l+1; l[n] := l+1 { и увеличение длин }
Обоснование
Для пары букв при любом распределении вероятностей оптимальное кодирование очевидно: первой букве нужно назначить код 0, а второй – 1. Именно это и делается в первой части оператора if основной процедуры Huffman. Рекурсивная часть алгоритма в точности следует доказательству теоремы предыдущего подраздела. С помощью функции Up в исходном упорядоченном массиве P отбрасываются две последние (наименьшие) вероятности, и их сумма вставляется в массив P, так чтобы массив (на единицу меньшей длины) остался упорядоченным. Заметим, что при этом место вставки сохраняется в локальной переменной j. Так происходит до тех пор, пока не останется массив их двух элементов, для которого оптимальный код известен. После этого в обратном порядке строятся оптимальные коды для трех, четырех и т. д. элементов. Заметим, что при этом массив вероятностей Р уже не нужен – нужна только последовательность номеров кодов, которые должны быть изъяты из массива кодов и продублированы в конце с добавлением разряда. А эта последовательность храниться в экземплярах локальной переменной j, соответствующих рекурсивным вызовам процедуры Huffman.