Префиксный код Хаффмана

Способ оптимального префиксного двоичного кодирования был предложен Д. Хаффманом.

Рассмотрим построение кода Х на вышеприведенном примере.

Дан первичный алфавит из 6 символов А=(а1, а2, а3, а4, а5, а6) с вероятностями (0.30, 0.20, 0.20, 0.15, 0.10, 0.05) соответственно.

Создадим новый алфавит А1, объединив 2 знака с наименьшими вероятностями (а5, а6), и заменив их новым знаком а(1). Вероятность нового знака равна сумме вероятностей тех знаков, что в него вошли, то есть 0.15. остальные знаки алфавита включим в новый без изменений. Общее число знаков будет на 1 меньше, чем в исходном.

Аналогичным образом продолжим создавать новые алфавиты, пока в последнем на останется 2 знака. Очевидно, что количество шагов будет равно
(N-2), где N – число знаков исходного алфавита.

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

Всю процедуру построения представим в виде таблицы 4.3.

Таблица 4.3. Промежуточные алфавиты

№ знака	Исх. алф-т А	А(1)	А(2)	А(3)	А(4)
	0.3	0.3	0.3	0.4	0.6
	0.2	0.2	0.3	0.3	0.4
	0.2	0.2	0.2	0.3
	0.15	0.15	0.2
	0.10	0.15
	0.05

Теперь в обратном направлении (против стрелок) проведем процедуру кодирования. Двум знакам последнего алфавита присвоим коды 0 и 1 (которому какой – роли не играет; например, условимся, что верхнему – 0, а нижнему –1). Процесс кодирования представлен в таблице 4.4.

Таблица 4.4 Построение кода Хаффмана

№ знака	Исх. алф-т А	А(1)	А(2)	А(3)	А(4)
вер-сть	коды	вер-сть	коды	вер-сть	коды	вер-сть	коды	вер-сть	коды
	0.30	00	0.3	00	0.3	00	0.4	1	0.6
	0.20	10	0.2	10	0.3	01	0.3	00	0.4
	0.20	11	0.2	11	0.2		0.3
	0.15	010	0.15		0.2
	0.10	0110	0.15
	0.05

Средняя длина кода, как и в предыдущем примере, равна:

2*(0.30+0.20+0.20)+3*0.15+4*(0.10+0.05)=2.45.

Избыточность также равна 0.0249. Однако вероятности 0 и 1 сблизились (0.47 и 0.53 соответственно).

Более высокая эффективность кодов Хаффмана по сравнению с кодами Шеннона-Фано становится очевидной, если сравнить избыточность кодов для естественного языка. Так, для русского языка средняя длина кода К(ru, 2)=4.395, избыточность кода Q(ru,2)=0.0090, т.е. не превышает 1%, что заметно меньше избыточности кода Шеннона-Фано.

Код Хаффмана важен в теоретическом отношении, поскольку можно доказать, что он является самым экономичным из всех возможных, то есть ни для какого метода алфавитного кодирования длина кода не может оказаться меньше, чем код Хаффмана.

Метод Хаффмана и его модификация – метод адаптивного кодирования (динамическое кодирование Хаффмана) – нашли широкое применение в программах-архиваторах, программах резервного копирования файлов и дисков, в системах сжатия информации в модемах и факсах.

4.3 Равномерное алфавитное двоичное кодирование.
Байтовый код

В этом случае двоичный код символов первичного алфавита строится цепочками равной длины, то есть со всеми знаками связано одинаковое количество информации, равное I^(А) = log₂ N.

Формировать признак конца знака не требуется, поэтому для определения длины кода можно воспользоваться формулой К(А, 2) ³ Log₂ N. Приемное устройство просто отсчитывает оговоренное заранее количество элементарных сигналов и определяет символ в соответствии с таблицей кодов.

При этом недопустимы сбои: например пропуск одного элементарного сигнала приведет к сдвигу всей кодовой последовательности и неправильной ее интерпретации (проблема решается путем синхронизации или иными способами).

Примером равномерного алфавитного кодирования является телеграфный код Бодо, пришедший на смену азбуке Морзе. Исходный алфавит должен содержать не более 32 символов К(А, 2) = 5 = log₂32, т.е. каждый знак первичного алфавита содержит 5 бит информации и кодируется цепочкой из 5 двоичных знаков.

Условие N £ 32 выполняется для языков, основанных на английском алфавите (N = 26+1 = 27).

Однако в русском алфавите 34 буквы. По этой причине в один знак «сжимают» «е, ё» и «ь, ъ». После такого сжатия N =32, однако, не остается свободных кодов для знаков препинания, поэтому в телеграммах они отсутствуют или заменяются буквенными аббревиатурами. Это не является заметным ограничением, так как избыточность языка позволяет легко восстановить информационное содержание сообщения.

Избыточность кода Бодо для русского языка Q(ru, 2) = 0,148, а для английского – Q(en, 2) = 0,239.

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

Чтобы определить длину кода, необходимо начать с установления количества знаков в первичном алфавите. Компьютерный алфавит (С) должен включать:

- 26 * 2 = 52 буквы латинского алфавита (прописные/строчные);

- 33 * 2 = 66 букв русского алфавита (прописные/строчные);

- 0 ¸9 = 10 цифр;

- знаки арифметических операций, препинания, спецсимволы - 20.

Получается общее число символов N = 148. Оценим длину кодовой цепочки К(С, 2) ³ log₂148 ³ 7,21.

Поскольку длина кода – целое число, то K (C, 2) = 8.

Именно такой способ кодирования принят в компьютерных системах – любому символу ставится в соответствие код из 8 двоичных разрядов
(8 бит).

Эта последовательность сохраняется и обрабатывается как единое целое, то есть отсутствует доступ к отдельному биту – по этой причине разрядность устройств компьютера, предназначенная для хранения или обработки информации кратна 8.

Совокупность 8 связанных бит называется байт, а представление таким образом символа - байтовым кодированием.

Байт наряду с битом может использоваться как единица измерения количества информации в сообщении. Один байт соответствует количеству информации в одном знаке алфавита при их равновероятном распределении.

Этот способ измерения количества информации называется объемным.

I_вер £ I_об.

Именно байт принят в качестве единицы измерения количества информации в международной системе единиц СИ. 1 байт = 8 бит. Наряду с байтом для измерения количества информации используется более крупные производные единицы:

1 КБайт = 2¹⁰ байт =1024 байт;

1 МБайт = 2²⁰ байт = 1024 Кбайт;

1 ГБайт = 2³⁰ байт = 1024 М байт;

1ТБайт = 2⁴⁰ байт = 1024 Г Байт (Терабайт).

Использование 8-битных цепочек позволяет закодировать 2⁸ = 256 символов, что превышает оцененное выше N, и, следовательно, дает возможность употребить оставшуюся часть кодовой таблицы для представления дополнительных символов.

Однако недостаточно только условиться об определенной длине кода. Ясно, что способов кодирования очень много. По этой причине для совместимости технических устройств и обеспечения возможности обмена информацией между многими потребителями требуется согласование кодов.

Подобное согласование осуществляется в форме стандартизации кодовых таблиц.

В персональных компьютерах и телекоммуникационных системах применяется международный байтовый код ASCII (American Standard Code for Information Interchange - американский стандартный код обмена информацией).

Он регламентирует коды первой половины кодовой таблицы (номера кодов от 0 до 127, то есть первый бит всех кодов 0). В эту часть попадают коды прописных и строчных английских букв, цифры, знаки препинаний и математических операций, а также некоторые управляющие коды (номера от 0 до 31).

Вторая часть кодовой таблицы - она считается расширением основной - охватывает коды в интервале от 128 до 255 (первый символ -1). Она используется для представления символов национальных алфавитов, а также символов псевдографики. Для этой части также имеются стандарты (например, для русского языка это КОИ-8 и другие).

Как и в основной таблице, так и в ее расширении коды букв и цифр соответствуют их лексикографическому порядку (то есть порядку следования в алфавите).

В настоящее время находит все более широкое применение еще один международный стандарт кодировки - Unicode. Его особенность в том, что в нем использовано 16-битное кодирование (то есть 2 байта на символ). Это позволяет включать в первичный алфавит 65536 знаков.

Это, в свою очередь, позволяет создать и использовать единую для всех распространенных алфавитов кодовую таблицу (в том числе китайский, японский алфавит).

4.4 Алфавитное кодирование с неравной длительностью
элементарных сигналов. Код Морзе

В качестве примера использования данного варианта кодирования рассмотрим телеграфный код Морзе (Азбука Морзе). В нем каждой букве или цифре сопоставляется некоторая последовательность кратковременных импульсов – точек и тире, разделяемых паузами. Длительности импульсов и пауз различны: если продолжительность импульсов, соответствующую точке обозначим t, то длительность тире – 3t. Длительность паузы между точкой/тире – t, пауза между буквами – 3t, пауза между словами (пробел) – 6t.

Таким образом, под знаками Морзе понимают:

· – короткий импульс + короткая пауза;

– – длинный импульс + короткая пауза;

0 – длинная пауза;

т.е. код оказывается троичным.

Свой код Морзе разработал в 1838 году, то есть задолго до исследования относительной частоты появления различных букв в тексте. Однако им был правильно выбран принцип кодирования – буквы, которые встречаются чаще, должны иметь более короткие коды, чтобы сократить общее время передачи информации.

Относительные частоты букв английского языка он оценил простым подсчетом литер в ячейках типографской наборной машины. Поэтому самая распространенная английская буква Е получила код «точка».

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

О – – – Ю · · – –

Е · Щ - - · -

А · - Э · · - · ·

И · · Ф · · - ·

Избыточность кода Морзе для русского алфавита – 0,233,

английского алфавита – 0,19.

Тем не менее, код Морзе имел весьма широкое распространение в ситуациях, когда источником и приемником сигналов являлся человек (не техническое устройство), и на первый план выдвигалась не экономичность кода, а удобство его восприятия человеком.

4.5 Блочное двоичное кодирование

Вернемся к проблеме оптимального кодирования. Пока что наилучший результат был получен при кодировании по методу Хаффмана – для русского алфавита избыточность оказалась менее 1%. При этом указывалось, что код Хаффмана улучшить невозможно.

На первый взгляд это противоречит первой теореме Шеннона, утверждающей, что всегда можно предложить способ кодирования, при котором избыточность будет сколь угодно малой величиной.

На самом деле это противоречие возникло из-за того, что до сих пор мы ограничивали себя алфавитным кодированием.

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

Пример 2. Пусть имеется словарь некоторого языка, содержащий
n =16000 слов (это, безусловно, более чем солидный словарный запас!). Поставим каждому слову равномерный двоичный код. Очевидно, длина кода может быть найдена из соотношения К(А, 2) ³ log₂ n ³ 13,97 = 14.

Следовательно, каждое слово кодируется комбинацией из 14 нулей/единиц - получаются своего рода двоичные иероглифы. Например, пусть следующим словам соответствуют коды:

информатика 10101010101010;

интересная 11100011100011;

наука 00000000000001.

Легко оценить, что при средней длине русского слова К^(r) = 6.3 буквы (5.3 буквы + пробел), средняя информация на знак первичного алфавита при таком способе кодирования будет равна:

I^(A) = K(A, 2)/ K^(ru) = 14/6.3 =2.222 бит.

Это более чем в 2 раза меньше, чем 5 бит при равномерном алфавитном кодировании. Для английского языка такой метод кодирования дает
2.545 бит на знак.

Таким образом, кодирование слов оказывается более выгодным, чем алфавитное.

Еще более эффективным окажется кодирование в том случае, если сначала установить относительную частоту появления различных слов в текстах и затем использовать код Хаффмана. Подобные исследования провел в свое время Шеннон: по относительным частотам 8727 наиболее употребляемых в английском языке слов он установил, что средняя длина информации на знак первичного алфавита оказывается равной 2.15 бит.

Вместо слов можно кодировать сочетания букв - блоки. В принципе блоки можно считать словами равной длины, не имеющими, однако, смыслового содержания. Удлиняя блоки и применяя код Хаффмана теоретически можно добиться того, что средняя информация на знак кода будет сколь угодно приближаться к I_¥.

Пример 3. Пусть первичный алфавит состоит из двух знаков а и b с вероятностями, соответственно 0.75 и 0.25. Сравнить избыточность кода Хаффмана при алфавитном и блочном кодировании.

При алфавитном кодировании

Знак р ₁ Код

а 0.75 0

b 0.25 1

I^(A) _ср = –0.75 log₂0.75 – 0.25 log₂0.25 = 0.915.

K(A, 2) = 1, Q = .

При блочном двухбуквенном кодировании (очевидно, что P _ij = P _i × P_j):

Знак р _ij Код

аа 0,562 0

ab 0,188 11

ba 0,188 100

bb 0,062 101

I_A² = – 0.562×log₂ 0.562 – 0.188×2×log₂ 0.188 – 0.062×log₂ 0.062 = 1.62.

(В пересчете на 1 знак - I_A¹=0,81).

К(А, 2) = 1×0.562 + 2×0.188 + 3×(0.188 + 0.062) = 1.688. (в пересчете на 1 знак К=0.844).

Q(A, 2) = .

Таким образом, блочное кодирование обеспечивает построение более эффективного кода по сравнению с алфавитным. При использовании блоков большей длины (3-х буквенные и более) избыточность стремится к 0 в полном соответствии с 1-ой теоремой Шеннона.

Контрольные вопросы и задания.

1. Считая алфавит самостоятельным, определить количество информации на каждый символ выражения «МЫ НЕ РАБЫ, РАБЫ НЕМЫ». Определить среднее количество информации на знак.

2. Построить коды Шеннона - Фано и Хаффмана для задания 1. Определить среднюю длину кода и оценить избыточность.

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

4. Код Морзе для цифр следующий

0 - - - - - 5 · · · · ·

1 · - - - - 6 - · · · ·

2 · · - - - 7 - - · · ·

3 · · · - - 8 - - - · ·

4 · · · · - 9 - - - - ·

Считая алфавит самостоятельным, а появление различных цифр – равновероятным, найти избыточность кода Морзе для цифрового алфавита

5. В лексиконе «людоедки» Эллочки Щукиной (И.Ильф, Петров «12 стульев») было 17 словосочетаний (Хо - хо! Ого! У вас спина белая! Шутишь, парниша! Блеск! и т.д.). Предложить свой вариант блочного кодирования, оценить избыточность кода.

5. Кодирование и представление чисел в компьютере

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

В связи с этим встает вопрос о выборе оптимального представления чисел в компьютере. Конечно, можно было бы использовать 8-битное кодирование отдельных цифр, а из них составлять числа. Однако такое кодирование не будет оптимальным - на двузначное число 13 потребуется 16 бит, если же определить это число посредством двоичного выбора («угадай-ка 16»), то получим всего 4-битную цепочку 1101.

Важно, что представление определяет не только способ записи данных (букв/чисел), но и допустимый набор операций над ними: в частности, буквы могут быть только помещены в некоторую последовательность (или исключены из нее без изменения их самих); над числами же возможны операции, изменяющие само число.

Представление чисел в компьютере имеет 2 важных отличия:

- числа записываются в двоичной системе счисления;

- для записи и обработки чисел отводится конечное число разрядов.

Следствия, к которым приводят эти отличия, и рассматриваются в данной главе.

5.1 Системы счисления

Общие замечания относительно понятия «число».

Любое число имеет значение (содержание) и форму представления. Значение числа задает его отношение к значениям других чисел (>, <, =) и, следовательно, определяет порядок расположения чисел на числовой оси.

Форма представления определяет порядок записи числа с помощью предназначенных для этого знаков.

При этом значение числа является инвариантом, то есть не зависит от способа его представления. Это означает также, что число с одним и тем же значением может быть записано по-разному, то есть отсутствует взаимно однозначное соответствие между представлением числа и его значением.

В связи с этим возникают вопросы, во-первых, о формах представления чисел, и, во-вторых, о возможности и способах перехода от одной формы к другой.

Способ представления числа определяется системой счисления.