1.5.5. Вариант алгоритма
Этот вариант адаптивного кодирования Хаффмана очень прост, но менее эффективен. Его идея заключается в построении множества из
кодов переменной длины на основе равных вероятностей и случайном присвоении этих кодов
символам. После чего смена кодов делается «на лету» по мере считывания и сжатия символов. Метод не слишком производителен, поскольку коды не основаны на реальных вероятностях символов входного файла. Однако его проще реализовать, и он будет работать быстрее описанного выше алгоритма, поскольку переставляет строки таблицы быстрее, чем первый алгоритм перестраивает дерево при изменении частот символов.

Рис. 1.17. Четыре шага алгоритма типа Хаффмана.
Основная структура данных - это таблица размера
, в которой три столбца хранят, соответственно, имена
символов, частоты символов и их коды. Таблица все время упорядочена по второму столбцу. Когда счетчики частот во втором столбце изменяются, строки переставляются, но перемещаются только первый и второй столбцы. Коды в третьем столбце не меняются. На рис. 1.17 показаны примеры для четырех символов и поведение метода при сжатии строки «
».
На рис. 1.17а изображено начальное состояние. После считывания символа
его счетчик увеличивается, и поскольку он теперь наибольший, строки 1 и 2 меняются местами (рис. 1.17b). Далее считывается второй символ
, его счетчик увеличивается, и строки 2 и 4 переставляются (рис. 1.17с). Наконец, после считывания третьего символа
, его счетчик становится наибольшим, что приводит к перестановке строк 1 и 2 (рис. 1.17d).
В этом алгоритме только одно место может вызвать проблему - это переполнение счетчиков. Если переменные счетчиков имеют разрядность
бит, их максимальное значение равно
. Поэтому наступит переполнение после
-го увеличения. Это может случиться, если размер сжимаемого файла заранее не известен, что бывает часто. К счастью, нам не надо знать точные значения счетчиков. Нам нужен лишь их порядок, поэтому эту проблему переполнения легко разрешить.
Можно, например, считать входные символы, и после
символа делать целочисленное деление счетчиков на 2 (или сдвигать их содержимое на одну позицию влево, что проще).
Другой близкий способ - это проверять каждый счетчик после его увеличения и после достижения максимального значения делать деление на 2 всех счетчиков. Этот подход требует более редкого деления, но более сложных проверок.
В любом случае, все операции должны делаться синхронно кодером и декодером.
Сначала соберите ваши факты, а затем можете
передергивать их по своему усмотрению. (Факты
упрямая вещь, а статистика более сговорчива.)
- Марк Твен