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

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

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


 

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

42573. Файловый менеджер FAR 33.5 KB
  040 Memory lod 57 106 bytes in 4 files Sterlik Sterlik Kunchenko Kunchenko lexey.doc Sterlik2.doc Sterlik1.doc...
42574. Расчет перевозки коммерческого груза несколькими рейсами 32 KB
  При недостаточном количестве транспортных средств для перевозки груза одним рейсом и при заданной величине времени отведенного на перевозку груза необходимо определить минимальное количество автомобилей и ВС необходимых для перевозки груза несколькими рейсами.mx = Tотв Твсп 1 2L V Tпр ...
42576. Контроль формирования себестоимости производства продукции (работ, услуг) на ЗАО «Пролетарий» 238.66 KB
  Изучить теоретические основы и нормативное регулирование учета и контроля себестоимости производства продукции (работ, услуг), дать организационно-правовую и экономическую характеристику исследуемого предприятия; оценить состояние учета себестоимости производства продукции (работ, услуг) на предприятии; дать анализ контроля себестоимости производства продукции (работ, услуг) на анализируемом предприятии;
42577. Архиватор WinRar 36.5 KB
  Запустить проводник Windows найти на диске файл более 100Кб скопировать его в папку 1. Найти на диске несколько папок и файлов 5 скопировать их в папку 2. При помощи кнопки dd – добавить в архив файл находящийся в папке 1 без папки.rr Записать время работы архиватора и размер полученного файла.
42578. РАЗНОСТНЫЕ ОПЕРАТОРЫ НЦФ 123.5 KB
  Применение разностных операторов Выделение зашумленных участковв массивах данных Данные массива = Установить после считывания по размеру массива данных. Выделить и проанализировать шумы в каротажных данных разностным оператором 3го порядка. Распределение модуля усиленных шумов: = П оператор НЦФ нормированный к 1 по сумме коэффициентов Нормированное скалярное произведение массивов zd и z в скользящем окне 2M1: Свертка Восстановление пропущенных данных и замена выбросов Сформируйте оператор восстановления пропущенных данных из...
42581. Изучить способы изменения и записи приглашения MS-DOS 42 KB
  Проделав данную лабораторную работу, я познакомился с программной оболочкой MS - DOS. Изучил основные приемы работы с файлами и каталогами.