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

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

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


 

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

59007. Екзотична новела Проспера Меріме. Матео Фальконе 37 KB
  Екзотична новела Матео Фальконе написана в 1829 році. Таким чином автор готує нас до знайомства з Матео Фальконе людиною відважною і в той же час небезпечною а початок новели є його передісторією. Розмова на уроці далі присвячена Матео Фальконе його вчинкам...
59008. Екологічне виховання молодших школярів 58 KB
  Ураховуючи завдання та мету курсу я намагаюсь пробудити в учнів занепокоєність станом природи їхнього безпосереднього оточення і планети в цілому а також ініціюю екологічне мислення та поведінку в повсякденному житті.
59009. Жінки в історії України 77.5 KB
  Можна навести чималий список жінок, які прославляли рідну землю. Це поетеси Леся Українка та Ліна Костенко, художниця Катерина Білокур, співачки Раїса Кириченко та Ніна Матвієнко, актори Соломія Крушельницька та Наталія Ужвій і багато-багато інших.
59010. Жанрова своєрідність та мова Вибраних місць із листування з друзями М. В. Гоголя 47.5 KB
  І Гоголь хоча й сам переживав важку кризу ретельно відповідав усім хто писав йому: Стоит только хорошенько выстрадаться самому как уже все страдающие становятся тебе понятны и почти знаешь что нужно сказать им. Починає Вибрані місця із листування з друзями передмова в якій Гоголь пояснює чому він вирішив написати цю книгу.
59011. Жанр танка в ліриці Ісікава Такубоку 103 KB
  За деякими японськими джерелами днем народження Такубоку вважається 20 лютого 1886 року дата реєстрації його народження. Ісікава прізвище поета Такубоку літературний псевдонім. Такубоку був першим і єдиним хлопчиком у родині.
59012. Життя людини - найвища цінність 61 KB
  Сухомлинського його твори; збагачувати активний словник учнів розвивати вміння формувати ціннісні судження про гармонійне життя; виховувати бажання глибше ознайомитися з біографією Великого Кобзаря Ліни Костенко Матері Терези Леонардо да Вінчі...
59013. Цікаві завдання та різноманітні інтелектуальні ігри. Задачі. Залізна логіка 129.5 KB
  Гарненька історія промовив інспектор Варніке вислухавши фрау Пепприх у якої тільки що вкрали двох відгодованих до свята гусей. У вашому поясненні парубче дещо не відповідає дійсності сказав інспектор Варніке. Чому інспектор Варніке запідозрив молодика у співучасті в крадіжці...
59014. Здоровя - мудрих гонорар 63.5 KB
  Учителям пропонується пройти стежиною здоровя. Маршрут стежки здоровя Перша зупинка Канони здоровя знайомство з основними заповідями Салернського кодексу здоровя медичного трактату XIV століття.
59015. Знакова система - символічна основа народного орнаменту 47.5 KB
  Завдання до уроку Розробка нескладної композиції орнаменту з використанням символів за власним вибором для оздоблення: керамічної тарілки чи глечика; декоративної серветки; святкового рушничка; килима; козацького поясу; бойової сокири; кіраси; ножен козацької шаблі.