1.5.3. Переполнение счетчика

Счетчики частот символов сохраняются на дереве в виде чисел с фиксированной разрядностью. Поля разрядов могут переполниться. Число без знака из 16 двоичных разрядов может накапливать счетчик до числа . Простейшее решение этой проблемы заключается в наблюдении за ростом счетчика в корне дерева, и, когда он достигает максимального значения, следует сделать изменение масштаба всех счетчиков путем их целочисленного деления на 2. На практике это обычно делается делением счетчиков листьев с последующим вычислением счетчиков всех внутренних узлов дерева. Каждый внутренний узел равен сумме своих потомков. Однако при таком методе целочисленного деления понижается точность вычислений, что может привести к нарушению свойства соперничества узлов дерева.

Простейший пример приведен на рис. 1.15h. После уполовинивания счетчиков листьев, три внутренних узла пересчитаны, как показано на рис. 1.15i. Полученное дерево, однако, не удовлетворяет свойству Хаффмана, поскольку счетчики перестали быть упорядоченными. Поэтому после каждой смены масштаба требуется перестройка дерева, которая, по счастью, будет делаться не слишком часто. Поэтому компьютерные программы общего назначения, использующие метод сжатия Хаффмана должны иметь многоразрядные счетчики, чтобы их переполнение случалось не слишком часто. Счетчики разрядности в 4 байта будут переполняться при значении равном .

Стоит отметить, что после смены масштаба счетчиков, новые поступившие для сжатия символы будут влиять на счетчики сильнее, чем сжатые ранее до смены масштаба (примерно с весом 2). Это не критично, поскольку из опыта известно, что вероятность появления символа сильнее зависит от непосредственно предшествующих символов, чем от тех, которые поступили в более отдаленном прошлом.