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

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

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


 

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

65552. ПІДВИЩЕННЯ ТОЧНОСТІ ВИМІРЮВАННЯ ТЕМПЕРАТУРИ ТЕРМОПАРАМИ В ПРОЦЕСІ ЕКСПЛУАТАЦІЇ 1.36 MB
  Метою дисертації є розробка методу корекції похибки від набутої в процесі тривалої експлуатації термоелектричної неоднорідності електродів термопар на основі аналізу властивостей цієї похибки.
65553. ОРГАНІЗАЦІЙНО-ПЕДАГОГІЧНІ УМОВИ ПРОФЕСІЙНОЇ ПІДГОТОВКИ ФАХІВЦІВ ПОЖЕЖНО-РЯТУВАЛЬНОЇ СЛУЖБИ 295.64 KB
  Водночас важливим шляхом у процесі трансформування є глибоке осмислення й усвідомлення власного історичного досвіду звернення до національних джерел зародження і розвитку професійної підготовки фахівців пожежнорятувальної служби.
65554. Комплексна оцінка успішності інтродукції видів роду PICEA Dietr. в умовах Сходу України 317 KB
  На Сході України ялини є інтродукованими видами. Уперше для умов Сходу України: визначено особливості росту якісні показники селекційну структуру стан формове різноманіття та репродуктивну спроможність ялин; визначено перспективність застосування видів ялин для створення насаджень...
65555. УДОСКОНАЛЕННЯ АНАЛОГО-ЦИФРОВОЇ СИСТЕМИ СИНХРОННОГО СТЕРЕОФОНІЧНОГО РАДІОМОВЛЕННЯ З ПІЛОТ-ТОНОМ 467.5 KB
  Стереофонічний ефект і його якість є основою системи стереофонічного радіомовлення, тому має місце нагальна необхідність проведення подальших досліджень з встановлення необхідних захисних відношень за радіочастотою, що забезпечували би високу якість стереофонічного радіоприймання.
65556. Експериментально–розрахунковий аналіз деформацій циліндричних оболонок в зоні удару 1.99 MB
  Циліндричні оболонки можуть служити моделлю для ряду елементів конструкцій на які діють ударні навантаження. При розробці математичної моделі напружено–-деформованого стану було використано систему рівнянь коливання оболонки типу С.
65557. СТРУКТУРА ТА РЕЖИМИ ФУНКЦІОНУВАННЯ ТЯГОВОГО ЕЛЕКТРОТЕХНІЧНОГО КОМПЛЕКСУ ПОСТІЙНОГО СТРУМУ ДВОХОСЬОВИХ ЕЛЕКТРОВОЗІВ 646 KB
  Існуючі типи вітчизняних електровозів з зчіпними масами названими вище обладнані тяговими електротехнічними комплексами ТЕТК з неефективними контактно-резисторними системами керування частотою обертання тягових електродвигунів ТЕД постійного струму.
65558. Розробка технології автоматичного зварювання та наплавлення під флюсом конструкційних сталей струмом малої густини 1.02 MB
  Автоматичне дугове зварювання та наплавлення під флюсом один із провідних процесів при виробництві й ремонті сталевих конструкцій та деталей машин. Технологічна собівартість одної тонни наплавленого металу в якій 71 займають...
65559. ЕЛЕКТРОМЕХАНІЧНА СИСТЕМА ПРИВОДА З ЛІНІЙНИМ ДВИГУНОМ ДЛЯ НАХИЛУ КУЗОВІВ ШВИДКІСНОГО РУХОМОГО СКЛАДУ 759.17 KB
  Оскільки найбільші обмеження швидкості наявні у кривих доцільно або прокласти нові швидкісні магістралі позбавлені кривих ділянок малого радіусу або упровадити системи для нахилу кузовів залишити в експлуатації існуючу мережу залізниць...
65560. ПІДВИЩЕННЯ ЕНЕРГОЕФЕКТИВНОСТІ ЕЛЕКТРОДУГОВИХ ПЕЧЕЙ 1.32 MB
  Оптимізація технологічних процесів в дугових печах з метою скорочення енергоспоживання і тривалості плавлення є важливою і актуальною задачею. Процес плавлення металошихти в електродугових печах відбувається на протязі значної долі всієї плавки до 80 від...