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

(а) (Ь) (с) (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 всех счетчиков. Этот подход требует более редкого деления, но более сложных проверок.

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