Монитор 1.94
Таблица 3
Шаги алгоритма арифметического кодирования при обработке сообщения
ОчереднойСимвол
|
НижняяГраница
|
ВерхняяГраница
|
|
0.0
|
1.0
|
В
|
0.2
|
0.3
|
I
|
0.25
|
0.26
|
L
|
0.256
|
0.258
|
L
|
0.2572
|
0.2576
|
Пробел
|
0.25720
|
0.25724
|
G
|
0.257216
|
0.257220
|
А
|
0.2572164
|
0.2572168
|
Т
|
0.25721676
|
0.2572168
|
Е
|
0.257216772
|
0.257216776
|
S
|
0.2572167752
|
0.2572167756
|
Таким образом, согласно нашей схеме, число 0.2572167752 однозначно кодирует сообщение “BILL GATES”.
Алгоритм арифметического декодирования может быть описан следующим образом:
Число = ПрочитатьЧисло();
Всегда
Символ =
НайтиСимволВинтервалКоторогоПопадаетЧисло
(Число)
Выдать (Символ) Интервал = ВерхняяГраницаИнтервалаДля (Символ) -
НижняяГраницаИнтервалаДля (Символ);
Число = Число - НижняяГраницаИнтервалаДля(Символ); Число = Число / Интервал; Конец Всегда
В приведенном алгоритме не рассматривается вопрос остановки декодера. В листинге приведенной в конце статьи программы декодер останавливается при обнаружении специального символа EOF (конец файла).
Для нашего примера декодер будет работать следующим образом (табл. 4).
Таким образом при обработке числа после определения символа, в интервал которого оно попадает, этот символ выдается как раскодированный, а его влияние на число устраняется действиями, обратными действиям при кодировании.
______Вопросы реализации______
Несмотря на то, что на первый взгляд алгоритм арифметического кодирования может работать толь-
ко на компьютерах с математическим сопроцессором, наилучшим образом он может быть реализован на основе стандартной 16 или 32-битовой целочисленной арифметики.
Ранее было отмечено, что при работе алгоритм отслеживает верхнюю и нижнюю границы возможного выходного кода. Сразу после старта нижняя граница установлена в 0.0, а верхняя — в 1.0. Первое упрощение для работы с целочисленной арифметикой — это заменить 1 на 0.999..., или .111... в двоичном коде. Это упрощает и кодирование, и декодирование.
Будем располагать в целочисленных регистрах дробные части значений границ, выравнивая их влево (старшие биты значения в старших битах регистра). Заполним регистры битами 1 для верхней границы и 0 для нижней соответственно. В нашей реализации будут использованы 16-битовые регистры, и их начальные значения будут равны 0xFFFF для верхней границы и 0x0000 — для нижней. Поскольку известно, что значения в регистрах соответствуют бесконечным дробям, то впоследствии можно будет сдвигать их влево, втягивая дополнительные биты по мере необходимости.
Рассмотрим работу описанного алгоритма на примере воображаемых пятизначных десятичных регистров. (Такие “некомпьютерные” объекты вводятся только для удобства понимания). Как и в предыдущем примере, будем сжимать сообщение “BILL GATES”.
После инициализации регистры будут хранить следующие значения:
ВерхняяГраница: 99999 (99999999...до бесконечности) НижняяГраница: 00000 (00000000...до бесконечности)
На следующем шаге вычислим Интервал. Разница между верхней и нижней границей будет 100000, а не 99999, так как мы подразумеваем бесконечное количество 9 в верхней границе.
Затем вычислим новое значение верхней границы. ВерхняяГраницаИнтервалаДля символа В равна 0.30, что должно привести к установке соответствующего регистра в 30000. Однако перед сохранением нового значения в регистре, принимая во внимание то, что мы моделируем бесконечную дробь, уменьшим это значение на единицу. Таким образом новое значение в регистре верхней границы равно 29999. Вычисление нового значения нижней границы дает 20000 в соответствующем регистре.
В этот момент регистры выглядят так:
ВерхняяГраница : 29999 (999...) НижняяГраница : 20000 (000...)
Так
как наиболее значимые
цифры в обоих регистрах
совпадают, то в силу
природы алгоритма эти
цифры уже никогда не изменятся
и их можно выдать
как первую цифру кода
сообщения. Это можно сделать,
сдвигая регистры влево
на одну цифру и “втягивая”
девятку на место младшей цифры
регистра
верхней границы. Да-лее
по мере работы алго-
Шаги работы алгоритма арифметического декодирования
Число
|
Символ
|
НижняяГраница
|
ВерхняяГраница
|
Интервал
|
0.2572167752
|
В
|
0.2
|
0.3
|
0.1
|
0.572167752
|
I
|
0.5
|
0.6
|
0.1
|
0.72167752
|
L
|
0.6
|
0.8
|
0.2
|
0.6083876
|
L
|
0.6
|
0.8
|
0.2
|
0.041938
|
Пробел
|
0.0
|
0.1
|
0.1
|
0.41938
|
G
|
0.4
|
0.5
|
0.1
|
0.1938
|
А
|
0.2
|
0.3
|
0.1
|
0.938
|
Т
|
0.9
|
1.0
|
0.1
|
0.38
|
Е
|
0.3
|
0.4
|
0.1
|
0.8
|
S
|
0.8
|
0.9
|
0.1
|
0.0
|
|
|
|
|
