1.5.5. Вариант алгоритма

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

Рис. 1.17. Четыре шага алгоритма типа Хаффмана.

Основная структура данных - это таблица размера , в которой три столбца хранят, соответственно, имена  символов, частоты символов и их коды. Таблица все время упорядочена по второму столбцу. Когда счетчики частот во втором столбце изменяются, строки переставляются, но перемещаются только первый и второй столбцы. Коды в третьем столбце не меняются. На рис. 1.17 показаны примеры для четырех символов и поведение метода при сжатии строки «».

На рис. 1.17а изображено начальное состояние. После считывания символа  его счетчик увеличивается, и поскольку он теперь наибольший, строки 1 и 2 меняются местами (рис. 1.17b). Далее считывается второй символ , его счетчик увеличивается, и строки 2 и 4 переставляются (рис. 1.17с). Наконец, после считывания третьего символа , его счетчик становится наибольшим, что приводит к перестановке строк 1 и 2 (рис. 1.17d).

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

Можно, например, считать входные символы, и после  символа делать целочисленное деление счетчиков на 2 (или сдвигать их содержимое на одну позицию влево, что проще).

Другой близкий способ - это проверять каждый счетчик после его увеличения и после достижения максимального значения делать деление на 2 всех счетчиков. Этот подход требует более редкого деления, но более сложных проверок.

В любом случае, все операции должны делаться синхронно кодером и декодером.

Сначала соберите ваши факты, а затем можете
передергивать их по своему усмотрению. (Факты
 упрямая вещь, а статистика более сговорчива.)
- Марк Твен