Спирина, М.С. Дискретная математика

1 0,22 0,20 0,16 0,10 0,16 0,02 0,10 0,04 Z\ 2^ Z t , ^ ^ Д Z i Zf, Рис. 6.6. Кодовое дерево для восьми символов с учетом вероятностей в каждой подгруппе не окажется по одной букве (см. рис. 6.6). Такой способ кодирования не всегда приводит к однозначному построению кода, так как разбиение на группы произвольно. Эту процедуру можно представить в виде двоичного дерева. Рассмотрим пример. На рис. 6.6 показан алфавит кодирования из восьми символов, который представлен в табл. 6.4. Алфавит можно разместить в таблице без учета статистических характери­ стик и с учетом вероятности. В этом примере энтропия набора букв Я = 2,88 < 3, но разброс длины кода от 2 до 5 ведет к не­ однозначному кодированию. В решении этой задачи отсутствие помех служит ограничением при реальном кодировании. Двоичное кодирование непосредственно связано с задачей по­ иска ответа при помощи уточняющих вопросов (см. подразд. 6.3). Т а б л и ц а 6.4 Кодовая таблица Кодовые комбинации Буквы Вероятности без учета с учетом вероятности вероятности Z\ 0,22 и 11 z 2 0,20 101 10 0,16 100 011 z 4 0,10 01 010 Z 5 0,16 001 001 0,02 0001 0001 Z 7 0,10 00001 00001 Zi 0,04 00000 00000 316