 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Код Хаффмана
|
Читайте также: |
Код Хаффмана строится следующим образом: буквы располагают в порядке убывания их вероятностей. Складывают вероятности двух последних букв, и ряд переписывают снова с учётом новой вероятности (суммы). Далее повторяют операцию, пока не получится 1. Нижнюю букву всегда кодируют нулём, а верхнюю - единицей.
Для составления кодовых комбинаций строится кодовое дерево. Двигаясь по кодовому дереву сверху вниз, можно записать для каждой буквы соответствующую ей кодовую комбинацию.
Код Хаффмана, также как и код Шеннона-Фэно, является префиксным, т.е. в таком коде ни одна комбинация не совпадает с другой, а это позволяет обеспечить однозначное кодирование без введения разделительных символов.
Пример кодирования (который мы разбирали на лекции): Даны шесть букв (х1-х6), расположенные в порядке убывания их вероятностей.
В результате кодирования длина кодового слова изменяется от 2 до 4 символов (2 - для букв с большей вероятностью, 4 - с меньшей).
Аналогично кодируется и русский алфавит (взяты те же 32 буквы, что и для кода Шеннона-Фэно).
Таблица кодов Хаффмана русских букв
| Буква | Код | Буква | Код |
| пробел | я | ||
| о | ы | ||
| е | з | ||
| а | ь,ъ | ||
| и | б | ||
| т | г | ||
| н | ч | ||
| с | й | ||
| р | х | ||
| в | ж | ||
| л | ю | ||
| к | ш | ||
| м | ц | ||
| д | щ | ||
| п | э | ||
| у | ф |
Определяем число элементарных символов на одну букву: 3*0,145+3*0,096+….+9*0,002=4,483.
И подсчитываем количество информации на один символ: 4,42/4,483=0,986 бит.
Сравним результаты кодирования русского алфавита разными методами.
Напомню, что при кодировании Шенноном-Фэно на один элементарный символ приходилось 0.994бит. Следовательно для русских букв оптимальнее кодирование Шенноном.
Поиск по сайту: