АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Сжатие информации. Алгоритм Хаффмена

Читайте также:
  1. Cпособи опису алгоритмів
  2. Автором опыта выделен алгоритм формирования умения работать с моделями.
  3. Алгоритм sum-product
  4. Алгоритм активного слушания
  5. Алгоритм Беллмана
  6. Алгоритм ва хосиятёои он
  7. Алгоритм використання ІКТ в роботі з дошкільниками
  8. Алгоритм Витерби
  9. Алгоритм выбора антибиотиков при остром бронхите
  10. Алгоритм выбора направления предпринимательской деятельности
  11. АЛГОРИТМ ВЫПОЛНЕНИЯ
  12. Алгоритм выполнения манипуляции

Метод Хаффмена (Huffman) разработан в 1952 г. Он более практичен и никогда по степени сжатия не уступает методу Шеннона-Фэно, более того, он сжимает максимально плотно. Код строится при помощи двоичного (бинарного) дерева. Вероятности (частоты) значений д.с.в. приписываются его листьям; все дерево строится, опираясь на листья. Величина, приписанная к узлу дерева, называется весом узла. Два листа с наименьшими весами создают родительский узел с весом, равным сумме их весов; в дальнейшем этот узел учитывается наравне с оставшимися листьями, а образовавшие его узлы от такого рассмотрения устраняются. После постройки корня нужно приписать каждой из ветвей, исходящих из родительских узлов, значения 0 или 1. Код каждого значения д.с.в. – это число, получаемое при обходе ветвей от корня к листу, соответствующему данному значению.

Замечание: Для методов Хаффмена и Шеннона-Фэно каждый раз вместе с собственно сообщением нужно передавать и таблицу кодов.

Пример: Закодируем с помощью метода Хаффмена фразу «Иванов Иван Иванович»

1. Вычисляем количество символов в сообщении (без учета пробелов) и частоту каждого символа.

L=18.

И В А Н О Ч
           

 

 

2. Упорядочиваем символы по частоте появления в тексте по убыванию: В – И – А – Н – О – Ч.

3. Записываем символы и их частоты в таблицу. Выбирая последовательно пару самых малых частот, строим двоичное дерево. Для каждого полученного узла в качестве частоты записываем сумму частот узлов, его образующих.

 

Символ В   И   А   Н   О   Ч
Частота 5   4     3   2  

0 1 (5)

Шаг 1 3

0 1 (4)

Шаг 2 6

0 1 (3)

Шаг 3 7 0 1 (2)

Шаг 4 11

0 1 (1)

Шаг 5 18

 

4. Каждой из ветвей, выходящей из узла, присваиваем код 0 или 1 слева направо, начиная с нижнего узла (синий цвет на рисунке).

5. Код каждого символа получаем при обходе ветвей от корня (нижнего узла) к листу (самому верхнему узлу), соответствующему данному символу.

 

В – 10 ()

И – 00 ()

А – 01 ()

Н – 110 ()

О – 1110 ()

Ч – 1111 ()

 

- средняя длина кода

 

Задание: Закодировать свою фамилию, имя отчество с помощью метода Хаффмена. Вычислить среднюю длину кода. Вычислить энтропию исходного текста.

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)