Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

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

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

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

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

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

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

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

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

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

На выходе кодера будет строка «s0i00rl00_1010000d011101000». Общее число битов равно 5 х 8 + 22 = 62. Коэффициент сжатия равен 62/88 « 0.7.