ZXNet эхоконференция «code.zx»

───────────────────────────────────────────────────────────────
* Forwarded by Oleg Grigoriev (500:812/5.2)
* Area : RU.ALGORITHMS
* From : Maxim Lopatkin, 2:5054/34.28 (12 Mar 99, 22:12:20)
* To : Artem Igorevich
* Subj : Hafman
───────────────────────────────────────────────────────────────
Привет, Artem !!!

[это проходило в эхе, я немного подкорявил]

Хаффман.

Прежде всего, давай определим - за счет чего происходит сжатие.
Сжатие происходит за счет кодирования более часто повторяющтхся символов
в файле более короткими кодами.
Пример:
AAABCCD - 7 Byte
A - '0'
C - '10'
D - '110'
B - '111'
Получаем: AAABCCD = '0001111010110' = 1 байт и 5 бит.
Далее пояснения. Hе трудно видеть, что обязательным условием является
уникальность двоичных кодов, кот. достигается посредством дерева Хаффмана.

Кодирование.

1. Статистика
Читаешь файл который ты хочешь заархивировать при этом подсчитывая
количество символов. Т.е состовляешь таблицу, в которй каждому коду ASCII
ставится в соответствие количествр этого символа в файле,
Пример.
Так, пусть у нас 5 буквенный алфавит. ABCDE
И архивируемый следующий файл: AABCABDCAB
Таблица будет выглядеть:
A - 4
B - 3
C - 2
D - 1
E - 0
2. Формирование кодов Хаффмана.
Это пожалуй, самый важный этап метода. Здесь формируются двоичные коды
Хафмана. Для этого используется дерево Хаффмана.
Опять же на нашем примере (для удобства я все наши сиволы по порядку
возростания частот поподания) Сбоку приписан бит, х-ий эту дугу.

E 0──1──┐
├─0+1=1──1─┐
│ │
D 1──0──┘ ├──1+2=3───1──┐
│ │
│ │
C 2──────────────0─┘ ├────3+3=6───1──┐
│ │
│ │
B 3────────────────────────────0─┘ ├───6+4=10──root
│
│
A 4──0───────────────────────────────────────────┘


Фактически мы делаем следующее - находим два кода с минимальным вхождением
в файл, затем их обьединяем в вершину, у которй частота попадания будет
равна сумме частот этих двух выбранных вершин. Получившаяся вершина - вновь
участвует в поиске на следующем шаге, а две, из котрых получилась данная
вершина - не участвуют. биты 1, 0 расставляются следующим образом - дуге с
первым минимумом присваивается '1' (как на рисунке), дуге со вторым - '0'
или наоборот. Гланое, чтобы из одной вершины не вели две одинаково помеченные
дуги. Случай или
──0────┐ ────1───┐
│ │ недопустимы.
──0────┘ ────1───┘
Т.е
шаг1 шаг2 шаг3 шаг4 шаг5
A - 4 A - 4 A - 4 A - 4 ABCDE=10
B - 3 B - 3 B - 3 min BCDE=6
C - 2 C - 2 min CDE - DE+C = 3 min
D - 1 min DE = D+E=1 min
E - 0 min
Итак, теперь есть дерево, формируем коды перекодировки. (причем обрати
внимание - такое построение дерева гарантирует, что более редким кодам
будет ставиться в соответствие более короткая последовательность бит.)
Итак.
A - '0'
B - '10'
C - '110'
D - '1110'
E - '1111'

Теперь проведем наше кодирование.
A A B C A B D C A B
AABCABDCAB - 0 0 10 110 0 10 1110 110 0 10
10 Байт 00101100 10111011 0010
2 байта 4 бита.
Было 10 Байт - стало 2 Байта 4 бита. Вот тебе и сжатие.

!! нужно хранить таблицу частот в файле, который ты архивируешь.
Разорхивирование - очевидно. Читаешь - затем по _ДЕРЕВУ_ перкодируешь,
Легко видеть, что идя от корня, по ветвям - ты дойдешь до листа,
который и есть твой символ.
> С уважением, MAX.

-+- GoldED 2.50.Beta4+
+ Origin: Чем дальше в лес, тем третий лишний. (2:5054/34.28)
─────────────────[ end of forwarded message ]──────────────────

WBR, Oleg.