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

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

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


 

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

43493. Информационная система Оценка оплаты отгруженного товара 2.45 MB
  В справочнике заказчиков хранятся данные о заказчиках: их наименованиях кодах адресах и датах заключения договоров. Условно постоянная информация Форма. Справочник готовой продукции Наименование изделия Код изделия Единица измерения Код единицы измерения Цена за единицу руб. 1 18 Форма 2 Данные о заказчиках взяты из договоров Наименование заказчика Код заказчика Адрес Дата заключения договора Магазин В школу 501 Ул.2010 Оперативно учетная информация Форма 3 Данные об отгрузке товаров из ТТН № ТТН Дата отгрузки Код заказчика...
43494. КРИМИНАЛИСТИКА. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ И ЗАДАНИЯ 51.5 KB
  Расследование преступных нарушений правил безопасности и охраны труда . Расследование преступных нарушений правил дорожного движения. Расследование преступлений скрытых инсценировками. Расследование преступлений совершенных в условиях неочевидности.
43495. Процесс управления организацией на основе анализа деятельности фирмы ЗАО «Комфорт» 338 KB
  Миссия организации и стратегическое видение Цели организации SWOTанализ Оценка и анализ внешней среды Управленческое обследование внутренних сильных и слабых сторон организации Анализ стратегических альтернатив и выбор стратегии Реализация стратегического плана Организация взаимодействия и полномочия Мотивация Контроль Выводы и рекомендации Далее описывается основное содержание глав курсовой работы. Рекомендации по выполнению курсовой работы Характеристика организации В настоящем разделе кратко излагаются основные характеристики...
43496. Исследование и программная реализация методов алгоритмов теории графов 115 KB
  Реализовать выбранный алгоритм на языке Pscl желательно использовать представление графа списками. Пояснительная записка включает в себя 23 страницы текста рисунок исходного графа рисунок МОД схему алгоритма 2 использованных источника. Данная программа позволяет: Ввести граф используя матрицу длин дуг; Получить матрицу задающую минимальное остовное дерево; Провести тестирование алгоритма; Введение Во многих прикладных задачах теории графов важно иметь возможность сопоставить ребрам графа определенные числа которые соответствуют...
43497. МУНИЦИПАЛЬНОЕ ПРАВО РОССИИ. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ И ЗАДАНИЯ 85.5 KB
  Развитие законодательства о местном самоуправлении в РФ. Государственный контроль и надзор за законностью местного самоуправления. Закон РФ Об общих принципах организации местного самоуправления в РФ от 6 октября 2003 г. Закон РФ О милиции от 18 апреля 1991 г.
43498. Проектирование ленточного конвейера 781 KB
  Наиболее трудоемкими в пищевой промышленности являются погрузочно-разгрузочные работы, которые занимают существенный объем в производственной деятельности предприятий. Погрузочно-разгрузочные работы выполняются на всех этапах основных производственных процессов. Для механизации этих операций используется подъемно-транспортное оборудование.
43499. Состояние рынка ценных бумаг в Казахстане 528 KB
  При купонных платежах государство устанавливает фиксированную годовую процентную ставку (купон), который выплачивается кредиторам либо раз в год, либо раз в полгода. В этом случае та сумма, которую государство заимствует в начале периода, будет равняться той сумме, которую оно выплатит в конце периода. Этот метод используете правительствами для большинства государственных облигаций.
43500. ТЕОРИЯ ГОСУДАРСТВА И ПРАВА. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ И ЗАДАНИЯ 63 KB
  Объем курсовой работы устанавливается в пределах 30 машинописных страниц Темы курсовых работ по Теории государства и права Предмет и методология теории государства и права Развитие и современное состояние теории государства и права Происхождение государства и права Общая характеристика теорий происхождения государства и права Понятие и сущность государства Государственная власть: характерные признаки и формы осуществления Соотношение государства права и экономики Типология государства Социалистический тип государства:...
43501. Разработка технологического процесса изготовления детали зубчатого колеса цилиндрического горизонтального двухступенчатого с раздвоенной быстроходной ступенью редуктора 9.25 MB
  Целью данной курсовой работы является разработка технологического процесса изготовления детали заданного качества, вытекающего из служебного назначения изделия, типом производства и оптимальной производительности труда, в нашем случае зубчатого колеса цилиндрического горизонтального двухступенчатого с раздвоенной быстроходной ступенью редуктора.