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

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

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


 

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

48441. Прикметник як частина мови 38.59 KB
  Мета: навчальна' поглибити знання з теми прикметник як частини мови; навчити застосовувати їх у практичній діяльності навчити класифікувати прикметники виокремлювати їх з інших частин мови; розвивальна: розвивати мовне чуття студентів їхнє уміння сприймати й засвоювати новий матеріал вміння диференційовано підходити до аналізу мовних явищ; виховна: виховувати інтерес до мовного матеріалу. Студенти мають уміти: виділяти прикметники в окремі розряди вміти правильно використовувати ступеньовані форми. Якісні прикметники їх семантичні групи...
48442. Психологія особистості. Конспект лекцій 296.83 KB
  Каратьян Психологія особистості Конспект лекцій Видавництво: Ексмо 2008р. Проблема опису структури особистості ЛЕКЦІЯ № 3. Спори про верховенство впливів середовища і спадковості на розвиток особистості ЛЕКЦІЯ № 4. Уявлення про структуру особистості в різних психологічних теоріях.
48443. Социальная психология. Конспект лекций 137.87 KB
  Поскольку психологическая наука в нашей стране в определении своего предмета исходит из принципа деятельности можно условно обозначить специфику социальной психологии как изучение закономерностей поведения и деятельности людей обусловленных включением их в социальные группы а также психологических характеристик самих этих групп. Социальная психология изучает социальные группы в обществе. Большинство современных социальных психологов считают что социальная психология изучает и личность и группы и социальную психику но в определенном...
48444. Соціологія. Методичні вказівки до семінарських занять 1.92 MB
  Звязок соціології з іншими науками Структура та функції соціологічної системи знань 11 Значення соціології у розвязанні соціальноекономічних та політичнихпроблем українського суспільства. ТИПИ СУСПІЛЬСТВ ТАТЕНДЕНЦІЇ РОЗВИТКУ СУСПІЛЬСТВА 37 Ознаки суспільства. Основні умови розвитку І функціонуваннясуспільства
48445. Тканини внутрішнього середовища 4.83 MB
  Мезенхіма це найбільш примітивна сполучна тканина яка існує тільки на ранніх стадіях ембріонального розвитку. Сполучна тканина виконує ряд важливих функцій:1. Механічна опорна яка полягає у формуванні капсули та строми багатьох органів сполучна тканина входить до складу звязок сухожилків хрящів тощо; 3. Пухка волокниста сполучна тканина супроводжує кровоносні та лімфатичні судини утворює строму внутрішніх органів.
48446. Попит, пропозиція, ринкова ціна у функціонуванні економіки. Конспект уроку з економіки 66.5 KB
  Попит пропозиція ринкова ціна у функціонуванні економіки Завдання уроку: дати означення попит пропозиція визначити принципи функціонування ринку та встановлення ринкової ціни. Ринковий попит і ринкова пропозиція Ринкова рівновага та її порушення. Добрий день Сьогодні у нас нова тема Попит пропозиція ринкова ціна у функціонуванні економіки. Суть ринкових відносин зводиться до відшкодування витрат продавців товаровиробників і...
48447. ФОНЕТИЧНА СИСТЕМА УКРАЇНСЬКОЇ МОВИ. ПРИНЦИПИ УКРАЇНСЬКОЇ ОРФОГРАФІЇ 55.06 KB
  Співвідношення звуків і букв. Ключові поняття: Фонетика фонологія фонема звук класифікація звуків їх зміни в потоці мовлення орфографія орфограма орфоепія орфоепічна норма. Модифікації звуків у потоці мовлення. До них належать: ЗВУК найменший елемент усного мовлення; комплекс артикуляційних рухів і їхній певний акустичний ефект що формує звукову оболонку значущих одиниць мови; СКЛАД частина слова один звук або сполучення звуків що вимовляється одним поштовхом видихуваного повітря; ТАКТ або ФОНЕТИЧНЕ СЛОВО частина мовного...
48448. Філософія і медицина Стародавнього світу 85.83 KB
  Філософія і медицина Стародавнього світу План: Огляд індійських філософських вчень Загальна характеристика китайської філософії Антична філософія: періодизація проблеми особистості Рекомендована література Філософія: Навчальний посібник Л. Практикум з філософії: Методичний посібник для викладачів та студентів ВНЗ. літра по філософії Давньої Греції і Риму Зміст лекції В історії філософської думки існує проблема існування індійської філософії т. актуальним є питання:Чи можна взагалі Для розуміння ролі філософії в індійській...
48449. Загальна характеристика підприємництва 38.3 KB
  за згодою партнерів; ліквідується в разі смерті або виходу з бізнесу одного з партнерів строк дії необмежений якщо корпорація не ліквідується за рішенням відповідних державних органів ...