КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Метод Хаффмана
Поиск оптимального кода по этому методу тоже начинают с построения рабочей таблицы (первая процедура), в которой в крайней справа и соседней с ней колонках, как и в предыдущем случае, размещают символы естественного алфавита источника информации и их вероятности в порядке их убывания. Старые символы, обозначающие репертуар источника информации, как и раньше, разбивают на две группы с равными суммарными вероятностями входящих в них символов. Но здесь (в технологии Хаффмана) это делают путём последовательного (из таблицы видно, каким образом) образования промежуточных вспомогательных групп с из символов (и образованных накануне групп) с наименьшими вероятностями – групп-алфавитов с более равномерным распределением вероятностей. Рабочая таблица метода Хаффмена
Из таблицы видно, что вновь образуемые группы (в таблице для них указаны только вероятности их символов) каждый раз выстраиваются в новой колонке по убыванию вероятностей, а в новой колонке снова образуется вспомогательная группа. Делается это до тех пор, пока не останется двух групп состояний кодируемого источника, с приблизительно одинаковой вероятностью образующих их состояний. В последней колонке – контрольная цифра, которая выражает, что последний алфавит – ансамбль.
На этом первая процедура метода, который ещё называют методом промежуточных группировок, заканчивается. Вторая процедура – построение кодового дерева Хаффмана. В ходе её графически воспроизводится процесс последовательного разделения общей (равной единице) суммарной вероятности реализации, хотя бы одного старого символа в рамках реализации каждой из групп. Это распределение прослеживается в порядке, обратном порядку образования групп. Ниже такое дерево показано и оно означает, что для реализации любого символа старого алфавита вначале должна реализоваться одна из двух полученных в итоге разбиения и приблизительно равновероятных групп, групп. Именно это символизирует первое «прикорневое» разветвление дерева, а далее все ветви помечены взятыми из предпоследней колонки рабочей таблицы вероятностями реализации состояний источника из соответствующих групп. Последующие разветвления с соответствующими цифрами из расположенных всё левее и левее колонок показывают, как распределяются между меньшими группами и отдельными символами старого алфавита те вероятности, которые приходились на предыдущие более крупные группы. При этом, если при первом ветвлении правой оказалась ветвь с большей вероятностью, то и при всех последующих разветвлениях такая ветвь всегда должна быть правой. Построение дерева с соблюдением указанных условий продолжается до тех пор, пока две последние ветви дерева не будут упираться, как все предыдущие, в последнюю пару наименее вероятных символов старого алфавита с наименьшими вероятностями. Последний этап формирования оптимального кода методом Хаффмана – построение кодовых слов для каждого символа старого алфавита, заполнение последней колонки рабочей таблицы.
Кодовое дерево Хаффмана 0,42 0,58
Дата добавления: 2015-06-27; Просмотров: 544; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |