називати дерево з мінімальною довжиною шляхів деревом Хаффмана. p align="justify"> Класичний алгоритм Хаффмана на вході отримує таблицю частот зустрічальності символів у повідомленні. Далі на підставі цієї таблиці будується дерево кодування Гоффмана (Н-дерево). p align="justify"> 1. Символи вхідного алфавіту утворюють список вільних вузлів. Кожен лист має вагу, який може дорівнювати або ймовірності, або кількістю входжень символу в стискаєте повідомлення;
2. Вибираються два вільних вузла дерева з найменшими вагами;
. Створюється їх батько з вагою, рівним їх сумарному вазі;
. Батько додається в список вільних вузлів, а два його нащадка видаляються з цього списку;
. Однією дузі, що виходить з батьків, ставиться у відповідність біт 1, інший - біт 0;
. Кроки, починаючи з другого, повторюються до тих пір, поки в списку вільних вузлів не залишиться тільки один вільний вузол. Він і вважатиметься коренем дерева.
Припустимо, у нас є наступна таблиця частот, яка зображена на рис. 1. br/>
157665АБВГД Рисунок 1 - Таблиця частот
На першому кроці з листя дерева вибираються два з найменшими вагами - Г і Д. Вони приєднуються до нового вузлу-батькові, вага якого встановлюється 5 +6 = 11. Потім вузли Г і Д видаляються зі списку вільних. Вузол Г соответсвует гілки 0 батька, вузол Д-гілки 1. p align="justify"> На наступному кроці те ж відбувається з вузлами Б і В, так як тепер ця пара має найбільший меншу вагу в дереві. Створюється новий вузол з вагою 13, а вузли Б і В видаляються зі списку вільних. Після всього цього дерево кодування виглядає так, як показано на рис. 2. <В
Рисунок 2 - Дерево кодування Хаффмана після другого кроку
На наступному кроці В«найлегшійВ» парою виявляються вузли Б/В і Г/Д.
Для них ще раз створюється батько, тепер вже з вагою 24. Вузол Б/В відповідає гілки 0 батька, Г/Д - гілки 1. p align="justify"> На останньому кроці в списку вільних залишилося тільки 2 вузла - це вузол А і вузол Б (Б/В)/(Г/Д). В черговий раз створюється батько з вагою 39, і колишні вільні вузли приєднуються до різних його гілкам. p align="justify"> Оскільки вільним залишився тільки один вузол, то алгоритм посотроенія дерева кодування Хаффмана завершується. Остаточне дерево представлено на рис. 3. br/>В
Рисунок 3 - Остаточне дерево кодування Хаффмана
Кожен символ, що входить до повідомлення, визначається як конкатенація нулів і одиниць, зіставлених ребрах дерева Хаффмана, на шляху від кореня до відповідного листу.
