|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 22 May 2001 23:00:00
To : All
Subject : Re: Сжатие по Хаффману
--------------------------------------------------------------------------------
Gleb Belyakov wrote:
> слева и спpава pавны) и всем символам левее медианы пишешь '1', пpавее -- '0'.
> Затем находишь медиану в каждой из половинок, и так далее.
>
Это ты описал метод Шенона-Фано, а не Хаффмана.
Хаффман строится по другому:
1. Отсортировали символы по частоте.
2. Берем два символа A, B с минимальной частотой FA и FB,
и заносим в 2 узла дерева (это будут терминальные узлы для
этих символов). Это два символа удаляем из исходного массива.
Потом создаем псевдосимвол X с частотой
FX = FA + FB. Этот символ помещаем 3-й узел, который
прописываем как корень для A, B; этот псевдосимвол опять
заносим в исходный массив с егонной виртуальной частотой.
3. Делаем [2] до тех пор, пока в исходном массиве ничего не останется.
Все, дерево Хаффмана готово! Путь до терминального узла по дереву
и есть битовая цепочка, кодирующая символ, лежаший в терминальном узле.
Проведу пример:
Допустим, есть алфавит из пяти символов с вероятностями:
A=35
B=35
C=30
D=15
E=10
Строим:
1---
берем два символа с мин. вероятностию. Это будут
D=15, E=10.
Построили.
X=25
D=15
E=10
Вх. массив стал:
A=35
B=35
C=30
X=25
2---
берем два символа с мин. вероятностию. Это будут
C=30, X=25.
Построили.
X=55
C=30
X=25
D=15
E=10
Вх. массив стал:
A=35
B=35
X=55
3---
берем два символа с мин. вероятностию. Это будут
A=35,B=35
Построили.
X=70
A=35
B=35
X=55
C=30
X=25
D=15
E=10
Вх. массив стал:
X=70
X=55
4---
берем два оставшихся символа.
Это будут
X=70
X=55
Построили.
X=125
X=70
A=35
B=35
X=55
C=30
X=25
D=15
E=10
Вот и все - дерево Хаффмана готово.
Коды символов получились:
A=00
B=01
C=10
D=110
E=111
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center for Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
