| p> | | p> | + - + | p> + ---- | 25 + - + = 10 + 15
+ - +
Розглядаємо таблицю знову для наступних двох символів (B і E). Ми продовжуємо в цей режим поки все "дерево" не сформоване, тобто поки все не зведеться до одного вузлу.
Частота 30 10 5 10 20 25
Символу C A D F B E
| | | | | | p> | | | | | | p> | | + - + | | | | p> | + - | 15 + + | | |
| + + - + | | | p> | | | | | p> | | + - + | | + - + | p> | + ---- | 25 + - + + - | 45 + - +
| + + - + + + - + p> | + - + | | p> + ---- | 55 + ------ + | p> + - + + | p> | + ------------ + | p> + --- | Root (100) + ---- +
+ ------------ +
Тепер коли наше дерево створено, ми можемо кодувати файл. Ми повинні завжди починати з кореня (Root). Кодуючи перший символ (лист дерева С) Ми простежуємо вгору по дереву всі повороти гілок і якщо ми робимо лівий поворот, то запам'ятовуємо 0-й біт, і аналогічно 1-й біт для правого повороту. Так для C, ми будемо йти вліво до 55 (і запам'ятаємо 0), потім знову вліво (0) до самого символу. Код Хаффмана для нашого символу C - 00. Для наступного символу (А) у нас виходить - ліво, право, ліво, ліво, що виливається в послідовність 0100. Виконавши вище сказане для всіх символів отримаємо
C = 00 (2 біти)
A = 0100 (4 біти)
D = 0101 (4 біти)
F = 011 (3 біта)
B = 10 (2 біти)
E = 11 (2 біти)
Кожен символ спочатку представлявся 8-у бітами (один байт), і так як ми зменшили число бітів необхідних для подання кожного символу, ми отже зменшили розмір вихідного файлу. Стиснення складивется наступним чином:
+ ---------- + ---------------- + ------------------ - + -------------- +
| Частота | спочатку | ущільнені біти | зменшено на |
+ ---------- + ---------------- + ------------------ - + -------------- |
| C 30 | 30 x 8 = 240 | 30 x 2 = 60 | 180 |
| A 10 | 10 x 8 = 80 | 10 x 3 = 30 | 50 |
| D 5 | 5 x 8 = 40 | 5 x 4 = 20 | 20 |
| F 10 | 10 x 8 = 80 | 10 x 4 = 40 | 40 |
| B 20 | 20 x 8 = 160 | 20 x 2 = 40 | 120 |
| E 25 | 25 x 8 = 200 | 25 x 2 = 50 | 150 |
+ ---------- + ---------------- + ------------------ - + -------------- +
Початковий розмір файлу: 100 байт - 800 біт;
Розмір стисненого файлу: 30 байт - 240 біт;
240 - 30% з 800, так що ми стиснули цей файл на 70%. p> Всі це досить добре, але неприємність знаходиться в тому факті, що для відновлення первісного файлу, ми повинні мати декодирующее дерево, так як дерева будуть різні для різних файлів. Отже ми повинні зберігати дерево разом з файлом. Це перетворюється в підсумку у збільшення розмірів вихідного файлу.
У нашою методикою стиснення і кожному вузлі знаходяться 4 байти покажчика, з цього, повна таблиця для 256 байт буде приблизно 1 Кбайт довгою. Таблиця в нашому прикладі має 5 вузлів плюс 6 вершин (де і знаходяться наші символи), всього 11. 4 байти...
