Первый этап в кодировании Хаффмана - подсчитать число вхождений каждого значения во входной файл изображения. Далее соответственно частоте вхождения значениям присваиваются битовые коды. Один метод присвоения битовых кодов переменной длины заключается в построении бинарного дерева с частыми значениями вблизи вершины и редкими значениями в качестве листьев. Начиная с редких значений, снизу вверх формируются поддеревья. Каждому корневому узлу поддерева присваивается числовая метка - сумма частот или меток узлов двух его потомков.

ТАБЛИЦА 15.1. Частота вхождения значения в небольшом файле-примере

После формирования дерева все левые поддеревья помечаются двоичным значением О, а все правые - 1. Далее для каждого значения формируется битовый код путем конкатенации битовых меток ветвей с вершины дерева до положения узла данного значения на дереве.

Для иллюстрации общих этапов построения дерева используем набор шести значений из табл. 15.1. Данный набор представляет короткий файл изображения, содержащий 21 элемент, причем значение 96 встречается 8 раз, значение 177 - 4 раза и так далее для остальных четырех значений файла.

Значения 210 и 43 в данной таблице имеют наименьшую частоту вхождения, поэтому используем эти два значения для создания первого поддерева (рис. 15.3). Корню этого поддерева присваивается метка, равная сумме вхождений двух его потомков: 3 = 2 + 1. Далее удаляем эти два файловых значения (210 и 43) из активного списка. Следующая наименьшая частота вхождения равна 3. Но мы только что создали подде рево, которое также имеет метку узла 3. Следовательно, можно сформировать следующее поддерево, используя любые два из названных трех элементов, которые имеют метку 3. Выберем два значения из файла и сформируем поддерево, изображенное на рис. 15.4, и удалим значения 141 и 85 из активного списка. Следующее поддерево строится из значения 177, частота вхождения которого равна 4, и поддерева, корень которого имеет метку 3 (рис. 15.5). Далее из активного списка удаляем значение 177 и узел дерева с меткой 3; теперь два элемента списка, имеющие наименьшую частоту, представляют поддеревья. Эти два поддерева сливаются, и в результате формируется новое поддерево, показанное на рис. 15.6. Наконец, построение бинарного дерева завершается (рис. 15.7) путем соединения значения 96 с последним сформированным поддеревом. Значение, присвоенное корню дерева, равно общей частоте (21) вхождения всех значений во входном файле.

Теперь, когда на бинарном дереве проставлены все значения, можно пометить левые ветви дерева двоичным значением “0”, а правые - значением “1”, как на рис. 15.8. Начав с корня дерева, проведем конкатенацию меток ветвей до всех листьев. В результате получим набор бинарных кодов переменной длины для всех значений в файле и заполним табл. 15.2, которая будет записана в сжатый файл. В данном примере есть одно значение, с которым сопоставлен однозначный бинарный код, три значения, с которыми соотнесены трехзначные бинарные коды, и два значения, с которым связаны четырехзначные коды. Редкие значения имеют более длинные коды, а частые значения - короткие.

⇐ вернуться назад | | далее ⇒