1.7.1. Детали реализации метода

Описанный выше процесс кодирования невозможно реализовать на практике, так как в нем предполагается, что в переменных Low и High хранятся числа с неограниченной точностью. Процесс декодирования, описанный на стр. 66 («Далее декодер удаляет эффект символа S из кода с помощью вычитания ... и деления ...») по своей сути очень прост, но совершенно не практичен. Код, который является одним числом, обычно будет длинным, очень длинным числом.

Файл объема 1 MB будет сжиматься, скажем, до 500 KB, в котором будет записано всего одно число. Деление чисел в 500 KB делается очень сложно и долго.

Любое практическое применение арифметического кодирования должно основываться на оперировании с целыми числами (арифметика чисел с плавающей запятой работает медленно и при этом происходит потеря точности), которые не могут быть слишком длинными. Мы опишем такую реализацию с помощью двух целых переменных Low и High. В нашем примере они будут иметь длину в 4 десятичные цифры, но на практике будут использоваться целые длиной 16 или 32 бита. Эти переменные будут хранить верхний и нижний концы текущего подынтервала, но мы не будем им позволять неограниченно расти. Взгляд на табл. 1.25 показывает, что как только самые левые цифры переменных Low и High становятся одинаковыми, они уже не меняются в дальнейшем. Поэтому мы будем выдвигать эти числа за пределы переменных Low и High и сохранять их в выходном файле. Таким образом, эти переменные будут хранить не весь код, а только самую последнюю его часть. После сдвига цифр мы будем справа дописывать 0 в переменную Low, а в переменную High цифру 9. Для того, чтобы лучше понять весь процесс, можно представлять себе эти переменные как левый конец бесконечно длинного числа. Число Low имеет вид , а число High= .

Проблема состоит в том, что переменная High в начале должна равняться 1, однако мы интерпретируем Low и High как десятичные дроби меньшие 1. Решение заключается в присвоении переменной High значения 9999..., которое соответствует бесконечной дроби 0.9999..., равной 1.

(Это легко доказать. Если , то среднее число  должно лежать между 0.9999... и 1; однако, его невозможно выразить десятичной дробью. Нельзя добавить ни одной цифры к числу 0.9999..., поскольку в нем бесконечно много цифр. Также ни одну из его цифр нельзя увеличить, так как все они равны 9. Значит, число 0.9999... равно 1. Рассуждая аналогично, легко показать, что число 0.5 имеет два представления в виде двоичной дроби: 0.1000... и 0.0111...).

В табл. 1.34 представлен процесс кодирования строки символов «SWISS_MISS». В первом столбце записаны символы на входе. Столбец 2 содержит новые значения переменных Low и High. В третьем столбце эти числа представлены в измененном масштабе с уменьшением High на 1. Строка 4 показывает следующую цифру, посылаемую на выход, а в пятом столбце записаны Low и High после их сдвига влево на одну цифру. Заметьте, что на последнем шаге в выходной файл было записано четыре цифры 3750. Окончательный выходной файл имеет вид 717533750.

Декодер работает в обратном порядке. В начале сделаны присвоения , , и  (первые четыре цифры сжатого файла). Эти переменные обновляются на каждом шаге процедуры декодирования. Low и High приближаются друг к другу (и к Code) до тех пор, пока их самые значимые цифры не будут совпадать. Тогда они сдвигаются влево, что приводит к их разделению, Code тоже сдвигается. На каждом шаге вычисляется переменная index, которая используется для нахождения столбца CumFreq табл. 1.24, позволяющего определить текущий символ.

Табл. 1.34. Кодирование «SWISS_MISS» сдвигами.

Каждая итерация цикла состоит из следующих шагов:

1. Вычислить число  и округлить его до ближайшего целого (в нашем примере общее CumFreq равно 10).

2. Использовать index для нахождения следующего символа путем сравнения с CumFreq в табл. 1.24. В следующем примере первое значение index равно 7.1759, а после округления – 7. Число 7 находится в таблице между 5 и 10, поэтому выбран символ «S».

3. Изменить Low и High по формулам:

;

;

где LowCumFreq[X] и HighCumFreq[X] накопленные частоты символа X и символа над X в табл. 1.24.

4. Если самые левые цифры в переменных Low и High совпадают, то сдвинуть Low, High и Code на одну позицию влево. В самую правую позицию Low записать 0, в High – 9, а в Code считать следующую цифру из сжатого файла.

Приведем все шаги декодирования для нашего примера.

0. Инициализация ,  и .

1. . Символ «S» выбран.

. .

2. . Символ «W» выбран.

 .

После сдвига и выхода цифры 7 имеем ,  и .

3. . Символ «I» выбран.

, .

После сдвига и выхода цифры 1 имеем ,  и .

4. . Символ «S» выбран.

, .

5. . Символ «S» выбран.

 .

6. . Символ «_» выбран.

 .

После сдвига и выхода цифры 7 имеем ,  и .

7. . Символ «М» выбран.

 .

После сдвига и выхода цифры 5 имеем ,  и .

8. . Символ «I» выбран.

 .

После сдвига и выхода цифры 3 имеем ,  и .

9. . Символ «S» выбран.

, .

10. . Символ «S» выбран.

 .

Теперь ясно, что символ eof следует добавлять в исходную таблицу частот и вероятностей. Этот символ будет кодироваться и декодироваться последним, что будет служить сигналом для остановки процесса.