1.5.4. Кодовое переполнение

Более серьезную проблему может создать кодовое переполнение. Это случится, если на дерево поступит слишком много символов и оно станет слишком высоким. Сами коды не хранятся на дереве, так как они меняются все время, и компрессор должен вычислять код символа  каждый раз заново при его появлении. Вот что при этом происходит:

Рис. 1.16. Адаптивный код Хаффмана, пример: часть I.

1. Кодер должен обнаружить символ на дереве. Дерево следует реализовать в виде массива структур, состоящих из узлов. Поиск в этом массиве будет линейным.

2. Если  не найден, то вырабатывается код esc, за которым следует несжатый код символа. Затем символ  добавляется на дерево.

Рис. 1.16. Адаптивный код Хаффмана, пример: часть II.

3. Если  найден, то компрессор движется от узла  назад к корню, выстраивая его код бит за битом. На каждом шаге, двигаясь влево от потомка к родителю он добавляет к коду «1», а двигаясь вправо, добавляет «0» (или наоборот, но это должно быть четко определено, поскольку декодер будет делать то же самое). Эту последовательность битов надо где-то хранить, поскольку она будет записываться в обратном порядке. Когда дерево станет высоким, коды тоже удлинятся. Если они накапливаются в виде 16-ти разрядного целого, то коды длиннее 16 бит вызовут сбой программы.

Рис. 1.16. Адаптивный код Хаффмана, пример: часть III.

Правильное решение может заключаться в накоплении битов кода в связанном списке, к которому можно добавлять новые узлы. Тогда ограничением будет служить лишь объем доступной памяти. Это общее решение, но медленное. Другое решение состоит в накапливании кода в длинной целой переменной (например из 50 разрядов). При этом следует документировать программу ограничением в 50 бит для максимальной длины кодов.

Рис. 1.16. Адаптивный код Хаффмана, пример: часть IV.

К счастью, эта проблема не оказывает влияние на процесс декодирования. Декодер читает сжатый код бит за битом и использует каждый бит, чтобы идти шаг за шагом влево или вправо вниз по дереву, пока он не достигнет листа с символом. Если листом служит esc код, декодер прочтет несжатый символ из сжатого файла (и добавит этот символ на дерево). В противном случае несжатый символ будет на этом листе дерева.

Пример: Применим адаптивное кодирование Хаффмана к строке «sir_sid_is». Для каждого входного символа найдены код на выходе, дерево после добавления этого символа, дерево после модификации (если необходимо), а также пройденные узлы слева направо снизу вверх.

Рис. 1.16 показывает начальное дерево и как оно изменялось за 11 шагов от (a) до (k). Обратите внимание на то, как символ esc получает все время разные коды, и как разные символы перемещаются по дереву, меняя свои коды. Код 10, например, кодирует символ «i» на шагах (f) и (i), этот же код присваивается символу «s» на шагах (е) и (j). Пустой символ имеет код 011 на шаге (h), но он же имеет код 00 на шаге (k).

На выходе кодера будет строка «s0i00r100_1010000d011101000». Общее число битов равно . Коэффициент сжатия равен .