Лабораторная работа №4 1 Теоретические сведения
жүктеу/скачать 349,84 Kb. Pdf көрінісі
|
ОИС лаб4 2018
|
4.1.2 Методика Хаффмена Методика Шеннона – Фэно не всегда приводит к однозначному построению кода. Ведь при разбиении на подгруппы можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппу. От указанного недостатка свободна методика Хаффмена. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву. Для двоичного кода методика сводится к следующему. Буквы алфавита сообщений выписываются в основной столбец в порядке убывания вероятностей. Две последние буквы объединяются в одну вспомогательную букву, которой приписывается суммарная вероятность. Вероятности букв, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительном столбце, а две последние объединяются. Процесс продолжается до тех пор, пока не получим единственную вспомогательную букву с вероятностью, равной единице. Методика поясняется примером, представленным табл. 1. Для составления кодовой комбинации, соответствующей данному сообщению, необходимо проследить путь перехода сообщения по строкам и столбцам таблицы. Таблица 1 Буква Вероятности Вспомогательные столбцы Z 1 Z 2 Z 3 Z 4 Z 5 Z 6 Z 7 Z 8 0.22 0.20 0.16 0.16 0.10 0.10 0.04 0.02 1 2 3 4 5 6 7 0.22 0.20 0.16 0.16 0.10 0.10 0.06 0.22 0.20 0.16 0.16 0.16 0.10 0.26 0.22 0.10 0.16 0.16 0.32 0.26 0.22 0.20 0.42 0.32 0.26 0.58 0.42 1 Для наглядности строится кодовое дерево. Из точки, соответствующей вероятности 1, направляются две ветви, причем ветви с большей вероятностью присваивается символ 1, а с меньшей 0. Такое последовательное ветвление продолжаем до тех пор, пока не дойдем до каждой буквы. Кодовое дерево для алфавита букв, рассматриваемого в табл. 1, приведено на рисунке 1. Рисунок 1 – Кодовое дерево Теперь, двигаясь по кодовому дереву сверху вниз, можно записать для каждой буквы соответствующую ей кодовую комбинацию: z l z2 z3 z4 z5 z6 z7 z8 01 00 111 110 100 1011 10101 10100 Эффективность рассмотренных алгоритмов достигается благодаря присвоению более коротких кодовых комбинаций (кодовых символов) символам источника сообщений, вероятность которых более высока, и более длинных кодовых комбинаций - символам источника сообщений с малой вероятностью. Это ведет к различиям в длине кодовых символов и, как следствие, к трудностям при их декодировании. Для разделения отдельных кодовых символов можно использовать специальный разделительный элемент, но при этом существенно снижается эффективность кода, т.к. средняя длина кодового символа фактически увеличивается на один элемент символа кода. Целесообразнее обеспечить декодирование без введения дополнительных элементов символов. Этого можно добиться, если в эффективном коде ни одна кодовая комбинация не будет совпадать с началом более длинной кодовой комбинации. Коды, удовлетворяющие этому условию, называют префиксными кодами (префиксом или началом называют первый элемент в кодовом символе, а последний элемент – окончанием или постфиксом). Коды, построенные по алгоритмам Шеннона–Фэно или Хаффмена, являются префиксными. жүктеу/скачать 349,84 Kb. Достарыңызбен бөлісу:
|