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). Кодовые слова на полученном дереве считываются справа налево. Алгоритм выдает оптимальный код (минимальная избыточность).

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

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


 

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

51808. Візуальні види мистецтва. Античне мистецтво. Мистецтво доби Відродження 38 KB
  Хто є автором скульптури Менада а Скопас б Лісіпп в Фідій 2. Хто з художників зображав види Толедо а Франсіско Гойя б Дієго Веласкес в Ель Греко 10. Хто з художників працював у напрямі сюрреалізм а Франсіско Гойя б Сальвадор Далі в Дієго Веласкес ІІІ рівень репродуктивнотворчий 1 бал Назвіть видатних скульпторів Давньої Греції. Хто є автором скульптури Сатир який відпочиває а Праксітель б Лісіпп в Мірон Хто є автором славетної праці Дискобол а Афінодор б Мірон в Полідор 3.
51809. Роль мови у формуванні і самовираженні особистості 78 KB
  Яке значення має рідна мова для національної самоідентефікації ЧИТАННЯ МОВЧКИ. Сказав мені один ханжа Що наша мова геть відстала Що краще б йшла мені чужа Коли б я вивчив її змалу....
51810. Германия 47 KB
  Оценивание на этом уроке будет проходить с помощью полоски оценивания Тест Самообразовательная деятельность Активность на уроке Участие в ролевой игре Итоговая оценка При подготовке На уроке Представление темы слайд № 1. Фронтально тест слайд № 2 №3 №;4 Научный спор. Можно ли зная историю современной Франции особенно последних событий однозначно утверждать Чем больше демократии тем лучше Сколько должно быть демократии Мотивация учебной деятельности Слайд №5. Что было самой большой проблемой...
51811. РОК – МУЗИКА - КУМИРИ 1970 – 1980 РОКІВ 380 KB
  ТИП УРОКУ: комбінований ХІД УРОКУ Учні заходять до класу під музику гурту The Betls. Ще раніше на початку 1964 року члени гурту навчалися в Лондонській Вищій політехнічній школі на архітектурному відділені і грали в команді ритм енд блюзу. З приходом до гурту студентів художнього коледжу Сіда Баррета зявилась і назва Pink Floid за іменами улюблених Барретом блюзових музикантів Пінка Андерсона і Флойда Каунсіла. Стиль гурту швидко...