Читайте также:
|
Исходные символы:
A (частота встречаемости 50)
B (частота встречаемости 39)
C (частота встречаемости 18)
D (частота встречаемости 49)
E (частота встречаемости 35)
F (частота встречаемости 24) 
Алгоритм Хаффамана
Алгоритм Хаффамана - адаптивный жадный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году аспирантом Массачусетского технологического института Д.Хаффаманом при написании им курсовой работы.
В отличие от алгоритма Шеннона-Фано, алгоритм Хаффмана остается всегда оптимальным и для вторичных алфавитов с более чем двумя символами.
Этот метод кодирования состоит из двух основных этапов:
1. Построение оптимального кодового дерева.
2. Построение отображения код-символов на основе построенного дерева.
Идея алгоритма состоит в следующем; зная вероятности символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символами с большей вероятностью ставятся в соответственно более короткие коды.
Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево)
1. 1.Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в снижаемое сообщение.
2. Выбираются два свободных узла дерева с наименьшими весами.
3. Создается их родитель с весом, равным их суммарному весу.
4. Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка.
5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой - бит 0.
6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.
A B C D E
10 5 8 13 10
B C A E D
5 8 10 10 13
A E BC D
10 10 13 13
BC D AE
13 13 20
AE BCD
20 26
AEBCD
Дата добавления: 2014-12-20; просмотров: 105 | Поможем написать вашу работу | Нарушение авторских прав |