Этот вариант адаптивного кодирования Хаффмана очень прост, но менее эффективен. Его идея заключается в построении множества из п кодов переменной длины на основе равных вероятностей и случайном присвоении этих кодов п символам. После чего смена кодов делается «на лету» по мере считывания и сжатия символов. Метод не слишком производителен, поскольку коды не основаны на реальных вероятностях символов входного файла. Однако его проще реализовать, и он будет работать быстрее описанного выше алгоритма, поскольку переставляет строки таблицы быстрее, чем первый алгоритм перестраивает дерево при изменении частот символов.
Симв. |
Сч-к |
Код |
Симв. |
Сч-к |
Код |
Симв. |
Сч-к |
Код |
Симв. |
Сч-к |
Код |
a1 |
0 |
0 |
«2 |
1 |
0 |
а2 |
1 |
0 |
U4 |
2 |
0 |
a2 |
0 |
10 |
а\ |
0 |
10 |
U4 |
1 |
10 |
а2 |
1 |
10 |
аз |
0 |
ПО |
аз |
0 |
по |
аз |
0 |
ПО |
аз |
0 |
ПО |
a4 |
0 |
111 |
a4 |
0 |
111 |
а\ |
0 |
111 |
а\ |
0 |
111 |
(а) (Ь) (с) (d)
Рис. 1.17. Четыре шага алгоритма типа Хаффмана.
Основная структура данных - это таблица размера п х 3, в
которой три столбца хранят, соответственно, имена п символов,
частоты символов и их коды. Таблица все время упорядочена по второму
столбцу. Когда счетчики частот во втором столбце изменяются, строки
переставляются, но перемещаются только первый и второй столбцы. Коды в
третьем столбце не меняются. На рис. 1.17 показаны примеры для четырех
символов и поведение метода при сжатии строки.
На рис. 1.17а изображено начальное состояние. После считывания символа а,2 его счетчик увеличивается, и поскольку он теперь наибольший, строки 1 и 2 меняются местами (рис. 1.17Ь). Далее счи-тывается второй символ ец, его счетчик увеличивается, и строки 2 и 4 переставляются (рис. 1.17с). Наконец, после считывания третьего символа ец, его счетчик становится наибольшим, что приводит к перестановке строк 1 и 2 (рис. 1.17d).
В этом алгоритме только одно место может вызвать проблему - это переполнение счетчиков. Если переменные счетчиков имеют разрядность к бит, их максимальное значение равно 2* — 1. Поэтому наступит переполнение после 2^-го увеличения. Это может случиться, если размер сжимаемого файла заранее не известен, что бывает часто. К счастью, нам не надо знать точные значения счетчиков. Нам нужен лишь их порядок, поэтому эту проблему переполнения легко разрешить.
Можно, например, считать входные символы, и после 2^ — 1 символа делать целочисленное деление счетчиков на 2 (или сдвигать их содержимое на одну позицию влево, что проще).
Другой близкий способ - это проверять каждый счетчик после его увеличения и после достижения максимального значения делать деление на 2 всех счетчиков. Этот подход требует более редкого деления, но более сложных проверок.
В любом случае, все операции должны делаться синхронно кодером и декодером.