91582

Статический алгоритм Хафмана

Доклад

Информатика, кибернетика и программирование

Пусть x1 xN совокупность двоичных кодов и пусть l1 l2 lN длины этих кодов. Можно показать что для любого ансамбля сообщений с полным числом более 2 существует двоичный код в котором два наименее вероятных кода xN и xN1 имеют одну и ту же длину и отличаются лишь последним символом: xN имеет последний бит 1 а xN1 0. Сначала группируются два наименее вероятные сообщения предпоследнему сообщению ставится в соответствие код с младшим битом равным нулю а последнему код с единичным младшим битом на рисунке m4 и m5. Код...

Русский

2015-07-21

41.64 KB

0 чел.

Статический алгоритм Хафмана

Статический алгоритм Хафмана можно считать классическим (см. также Р. Галлагер. Теория информации и надежная связь. “Советское радио”, Москва, 1974.) Определение статический в данном случае отностится к используемым словарям. Смотри также http://www.ics.ics.uci.edu/~dan/pubs/DataCompression.html.

Пусть сообщения m(1),…,m(N) имеют вероятности P(m(1)),… P(m(N)) и пусть для определенности они упорядочены так, что P(m(1)) P(m(2)) P(m(N)). Пусть x1,…, xN – совокупность двоичных кодов и пусть l1, l2,…, lN – длины этих кодов. Задачей алгоритма является установление соответствия между m(i) и xj. Можно показать, что для любого ансамбля сообщений с полным числом более 2 существует двоичный код, в котором два наименее вероятных кода xN и xN-1 имеют одну и ту же длину и отличаются лишь последним символом: xN имеет последний бит 1, а xN-10. Редуцированный ансамбль будет иметь свои два наименее вероятные сообщения сгруппированными вместе. После этого можно получить новый редуцированный ансамбль и так далее. Процедура может быть продолжена до тех пор, пока в очередном ансамбле не останется только два сообщения. Процедура реализации алгоритма сводится к следующему (см. рис. 2.6.5.1). Сначала группируются два наименее вероятные сообщения, предпоследнему сообщению ставится в соответствие код с младшим битом, равным нулю, а последнему – код с единичным младшим битом (на рисунке m(4) и m(5)). Вероятности этих двух сообщений складываются, после чего ищутся два наименее вероятные сообщения во вновь полученном ансамбле (m(3) и m`(4); P(m`(4)) = P(m(4)) + P(m(5))).

Код

Сообщение

P(m(i))

00

m(1)

0.3

01

m(2)

0.25

10

m(3)

0.25

110

m(4)

0.1

111

m(5)

0.1

=1.0

Рис. 2.1. Пример реализации алгоритма Хафмана

На следующем шаге наименее вероятными сообщениями окажутся m(1) и m(2). Кодовые слова на полученном дереве считываются справа налево. Алгоритм выдает оптимальный код (минимальная избыточность).

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

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


 

А также другие работы, которые могут Вас заинтересовать

63558. Роль философских идей психоанализа в понимании человека и общества 47.5 KB
  Если какой то предок бросился с моста то далекого потомка может на мосту тянуть кинуться с высоты но если помочь сознательно отделить жизнь этого человека от жизни неизвестного ему предка то он перестанет бояться высоты...
63559. Россия между Западом и Востоком. Философские западники и почвенники 40 KB
  Философией в России доныне занимается в основном гуманитарная политизированная интеллигенция а действительно полезные для исканий истины естествоиспытатели в философии России редки. Современность показывает ту же закономерность: по мере ослабления России растут притязания на ее богатства соседних а теперь и заокеанских государств.
63560. Перспективы учения о ноосфере, философии космизма и «общего дела» 31 KB
  Ноосфера как особая оболочка земного шара становящаяся новым этапом развития биосферы атмосферы и гидросферы могущество вооруженного наукой и техникой человечества должно быть направлено на помощь силам природы в планетарном масштабе. Все природные процессы стали уже протекать не так как протекали бы в отсутствии человечества на планете.
63561. Знешняя палiтыка Беларусi на сучасным этапе 83 KB
  Сёння ў свеце існуе больш 220 вялікіх і малых дзяржаў, 187 з якіх з’яўляюцца членамі ААН. Пачэснае месца сярод гэтых краін займае Рэспубліка Беларусь. Яе, як незалежную краіну прызналі і устанавілі з ёй дыпламатычныя адносіны 153 краіны свету.
63562. Организация и проведение специальной обработки 94.5 KB
  Сущность приёмы и способы специальной обработки техники материальных средств. Заражение РВ ОВ БС может привести к потерям среди личного состава и вызовет необходимость проведения аварийноспасательных и других неотложных работ с применением...
63563. Специальные налоговые режимы. Патентная система налогообложения 252.5 KB
  Патентная система налогообложения При переходе на УСН ЕСхН ЕНВД предусматривается особый порядок определения прибыли или убытка оценки Д и Р учитываемых для цели н о особый порядок определения налоговых обязательств.
63565. Статистика. Вводная часть 116.5 KB
  Уважаемые студенты Вы приступаете к изучению новой учебной дисциплины статистики которая занимает важное место в системе высшего экономического образования как базовая дисциплина формирующая профессиональный уровень современного специалиста в области экономики и финансов.
63566. Струйные принтеры (Liquid ink-jet) 136.5 KB
  Схема устройства непрерывной струйной печати Устройства дискретного действия В настоящее время именно эти технологии струйной печати получили широкое распространение. Достигнутый в этой области прогресс приведший к повышению качества печати снижению ее себестоимости и удешевлению печатных устройств способствовал...