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