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 в начале должна равняться 1, однако мы интерпретируем Low и High как десятичные дроби меньшие 1. Решение заключается в присвоении переменной High значения 9999..., которое соответствует бесконечной дроби 0.9999..., равной 1. (Это легко доказать. Если В табл. 1.34 представлен процесс кодирования строки символов «SWISS_MISS». В первом столбце записаны символы на входе. Столбец 2 содержит новые значения переменных Low и High. В третьем столбце эти числа представлены в измененном масштабе с уменьшением High на 1. Строка 4 показывает следующую цифру, посылаемую на выход, а в пятом столбце записаны Low и High после их сдвига влево на одну цифру. Заметьте, что на последнем шаге в выходной файл было записано четыре цифры 3750. Окончательный выходной файл имеет вид 717533750. Декодер работает в обратном порядке. В начале сделаны присвоения
Табл. 1.34. Кодирование «SWISS_MISS» сдвигами. Каждая итерация цикла состоит из следующих шагов: 1. Вычислить число 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.
2.
После сдвига и выхода цифры 7 имеем 3.
После сдвига и выхода цифры 1 имеем 4.
5.
6.
После сдвига и выхода цифры 7 имеем 7.
После сдвига и выхода цифры 5 имеем 8.
После сдвига и выхода цифры 3 имеем 9.
10.
Теперь ясно, что символ eof следует добавлять в исходную таблицу частот и вероятностей. Этот символ будет кодироваться и декодироваться последним, что будет служить сигналом для остановки процесса.
|