Опрос

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

Новички

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

Вариант алгоритма

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

Симв.

Сч-к

Код

Симв.

Сч-к

Код

Симв.

Сч-к

Код

Симв.

Сч-к

Код

a1

0

0

«2

1

0

а2

1

0

U4

2

0

a2

0

10

а\

0

10

U4

1

10

а2

1

10

аз

0

ПО

аз

0

по

аз

0

ПО

аз

0

ПО

a4

0

111

a4

0

111

а\

0

111

а\

0

111

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

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