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

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

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


 

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

63629. Планування трудових ресурсів та ФОП на підприємствах зв’язку 77.5 KB
  Роботу з кадрами на підві виконують усі лінійні керівники а також деякі функціональні відділи та окремі спеціалісти і менеджери: відділ кадрів відділ праці та з плати відділ технічн. Внутрішній набір – набір кадрів з внутрішніх резервів: заміщення посад в звâ€язку з декретними відпустками працівників перехід...
63630. Общее экономическое равновесие. Экономика благосостояния и теория общественных благ 547.47 KB
  Состояние экономики называется Парето-эффективным в распределении благ между потребителями если невозможно перераспределить блага таким образом чтобы благосостояние хотя бы одного из потребителей увеличилось без уменьшения благосостояния других.
63631. Форми узагальнення результатів наукових досліджень 78.04 KB
  Форми узагальнення результатів наукових досліджень Результати наукового дослідження узагальнюються з метою перетворення їх у джерело інформації. Формою узагальнення результатів дослідження може бути усний виклад або друкована праця.
63634. Формы современных государств 255.39 KB
  Форма государства –это организация государственной власти выраженная в форме правления государственного устройства и политического государственного режима. Значение формы велико так как от того: насколько форма соответствует содержанию зависит эффективность действия государственной власти.
63635. ВАРТİСТЬ İ ОПТИМİЗАЦİЯ СТРУКТУРИ КАПİТАЛУ 787.31 KB
  Перше наукове визначення капіталу дав Аристотель. У перелічених визначеннях категорія капіталу пов’язується з речовою формою і не враховує грошового капіталу який не можна ототожнювати з засобами виробництва і який призначається для їх придбання для забезпечення безперервності руху капіталу у сферах виробництва та обігу.
63637. Захватно-опорные приспособления 1.8 MB
  Захваты для закрепления образцов при испытании на одноосное растяжение. В зависимости от материала испытываемого образца различают захваты для испытаний жестких материалов металлы пластмассы керамика и резины полимерных пленок текстильных нитей и тканей.