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

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

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


 

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

78311. НОРМИРОВАНИЕ ТОЧНОСТИ ДЕТАЛЕЙ, СОПРЯГАЕМЫХ С ПОДШИПНИКАМИ КАЧЕНИЯ 406 KB
  В подшипниках качения между поверхностью вращающейся детали и поверхностью опор располагаются шарики или ролики. Внутренний диаметр внутреннего кольца В ширина высота колец подшипника при одинаковой ширине наружного и внутреннего колец. Общий вид подшипника качения роликовый Класс точности подшипника характеризуется целым комплексом точностных требований относящихся к отклонениям размеров формы и расположения...
78312. ОБЕСПЕЧЕНИЕ ТОЧНОСТИ РАЗМЕРНЫХ ЦЕПЕЙ 312 KB
  Размерные цепи при образовании посадок: а для посадки с зазором; для посадки с натягом Если рассмотреть связи между размерами звеньев составляющих размерную цепь и замыкающим звеном можно увидеть особенность этих звеньев по которой все составляющие звенья цепи разделяются на увеличивающие и уменьшающие рис. необходимо решать вопрос о нормировании точности составляющих звеньев и точности замыкающего звена чтобы устройство образующее размерную цепь в виде отдельной детали или сборочной единицы выполняло свое служебное...
78313. Машины для соединения деталей и обработки узлов одежды физико-химическим и электро-физическим способами 19.28 KB
  Существует несколько видов сварки деталей из термопластичных одежных материалов. Разновидностью термоконтактного способа сварки является термоимпульсная сварка которая применяется для ПВХ и полиэтиленовых пленок. Оборудование при термоимпульсном способе сварки применяется в основном в виде прессов например УЗП2500 ДиЭлектро. Установки для ВЧ сварки включают в себя электроды механизм давления генератор ВЧ приборы контроля режима сварки и автоматического управления процессом.
78314. Дополнительные механизмы и устройства швейных машин 22.44 KB
  Приспособления для направления полуфабриката к иглам швейных машин в зависимости от типа шва выполняемого с их применением по классификации ЦНИИШП разбиты на 6 групп. В первую группу объединены приспособления для выполнения соединительных и отделочных швов без подгибания материалов. Во вторую третью и четвертую группы входят приспособления для выполнения таких швов где требуется подгибать один или несколько слоев материала. При этом во вторую группу входят приспособления где подгибание не связано с соединением деталей например...
78315. Классификация машин-полуавтоматов 24.31 KB
  Для пришивания пуговиц применяют полуавтомат с челночным и однониточным цепным переплетением ниток. Пришивание пуговиц с челночным переплетением ниток выполняют на машине 727 827 классов кроме того пришивание металлических крючков и петель на полуавтомате 53 класса и изготовление закрепок на машине 220М и 820 классов. Пришивание пуговиц однониточным цепным стежком выполняют на полуавтоматах...
78316. ПОЗНАВАТЕЛЬНЫЕ ПРОЦЕССЫ 175.5 KB
  Внимание сопровождает процессы восприятия памяти мышления и т. У дочеловеческих организмов есть только два вида памяти: генетическая и механическая. Человеку также присущи эти два вида памяти. Сохранить можно только то что запомнил а воспроизвести то что сохранил в памяти.
78317. ЭМОЦИОНАЛЬНО-ВОЛЕВАЯ СФЕРА ЛИЧНОСТИ 118 KB
  Эмоции и чувства. Он не только познает объективную и субъективную действительность но и как-то относится к предметам событиям другим людям к своей личности. Они образуют единую подструктуру личности ее эмоциональную сферу. Чувства являются ведущими образованиями эмоциональной сферы личности определяющие динамику и содержание эмоций.
78318. МОТИВАЦИЯ И НАПРАВЛЕННОСТЬ ЛИЧНОСТИ 87 KB
  Потребности как источник активности человека. Потребности как источник активности человека Понятие мотивации и потребностей. Многие психологи полагают что главной причиной активности является стремление человека удовлетворить свои потребности. Потребности это состояние индивида создаваемое испытываемой им нужды в объектах необходимых для его существования и развития.
78319. РЕЧЬ И ОБЩЕНИЕ 101 KB
  Понятие речи. Речь это особая и наиболее совершенная форма общения, свойственная только человеку. Она обладает огромными выразительными возможностями, которые передают психические переживания говорящего. С позиции психологии речь – это вынесенная во вне психика человека