Обобщение метода кодирования Хаффмана с использованием систем счисления Ковалёв Д.С. Новосибирский Государственный Университет Факультет Информационных Технологий Кафедра Общей Информатики Научный руководитель: к.ф.-м.н. Кренделев С.Ф. Новосибирск, 2006

Кодирование Хаффмана a 1 a 2 a 3 a 4 a 5 a1a2a1a2 a 3 a 4 a 5 a3a3 a4a5a4a5 a1a1 a2a2 a4a4 a5a5 А = {a 1 a 2 a 3 a 4 a 5 } – алфавит Дерево Хаффмана для A: Дерево однозначно определяет коды Коды являются префиксными и могут иметь разные длины В основном используются именно двоичные коды a a a a a Коды Хаффмана для A: В сущности, дерево определяет разбиение алфавита на подмножества, а коды показывают в какие разбиения попадал каждый элемент.

Системы счисления Будем рассматривать только натуральные числа (включая 0) Любое такое число X представимо единственным образом в виде: X = d 0 + d 1 B + d 2 B 2 + …, причем d i < B. Это система счисления с фиксированным основанием B. Также число X представимо в виде: X = d 0 + d 1 B 0 + d 2 B 0 B 1 + d 3 B 0 B 1 B 2 +…, причем d i < B i. Это система счисления со смешанным основанием {B 0 B 1 B 2 B 3 …} Зная X и основание(я) системы счисления всегда можно получить цифры, а зная цифры всегда можно однозначно восстановить X

Предлагаемый алгоритм a 1 a 2 a 3 a 4 a 5 a2a3a2a3 a 4 a 5 a3a3 a1a1 a2a2 a4a4 a5a5 Дерево для A:Коды для A: a a a a a Дерево однозначно определяет коды Коды являются префиксными и могут иметь разные длины В общем случае коды будут небинарными На каждом этапе алфавит можно разбивать на произвольное число частей. Дальнейшая цель – перевести сообщение закодированное новыми кодами в двоичную запись.

Кодирование (1) Новое дерево определяет систему счисления. В этой системе основание следующего разряда определяется зависит от цифры в предыдущем разряде. a 1 – 0 (3) a 2 – 10 (32) a 3 – 11 (32) a 4 – 20 (32) a 5 – 21 (32) Коды и основания для A:

Кодирование (2) Будем кодировать S = {a 1,a 2,a 1,a 5, a 4, a 4 } - последовательность из символов A. Запишем коды и основания для каждого символа (| - разделитель, реально его нет): P = {0|10|0|21|20|20} – коды (префиксность) B = {3|32|3|32|32|32} – основания Представим, что P этого цифры некоторого числа X в системе со смешанными основаниями B. Таким образом, последовательность S можно закодировать одним натуральным X. Бинарное представление для S – это запись X в двоичной системе счисления a 1 – 0 (3) a 2 – 10 (32) a 3 – 11 (32) a 4 – 20 (32) a 5 – 21 (32)

Декодирование (1) Сначала из набора битов получаем обратно X Далее, по X восстанавливаем последовательность кодов P и оснований B

Декодирование (2) Восстановление кодов P и оснований B по числу Х выглядит так: Первый символ из B заранее известен Зная первое основание, можно вычислить первый символ из P Зная первый символ из P, определяем второй символ из B Зная второе основание, можно вычислить второй символ из P и т.д. В силу префиксности исходного кода, всегда можно определить декодирован ли очередной символ до конца или нет.

Спасибо за внимание! Вопросы