2015-09-07
546
Альтернативой методу сжатия по Хаффмену является арифметическое кодирование. При его применении код присваивается всему передаваемому файлу, вместо кодирования отдельных символов. Кодер читает входной файл символ за символом и добавляет биты к сжатому файлу. Получающийся код представляет собой дробную часть числа из полуинтервала [0, 1). В общем виде алгоритм арифметического кодирования имеет следующие шаги.
1. Задать текущий интервал [0, 1).
2. Повторить следующие действия для каждого символа s входного файла.
2.1. Разделить текущий интервал на части пропорционально частотам каждого символа.
2.2. Выбрать подынтервал, соответствующий символу s, и назначить его новым текущим интервалом.
3. Когда весь входной файл будет обработан, выходом алгоритма объявляется любая внутренняя точка текущего интервала.
Для восстановления сжатых данных последовательно определяются интервалы, в которые попадает анализируемое значение (входной код из сжатого файла), и соответствующие им символы, которые и будут выдаваться на выход декодера.
В качестве примера выполним сжатие той же последовательности, что рассматривалась при изучении методов сжатия по Хаффмену. Процесс образования интервалов показан в таблице 6.4. При этом используются частоты из таблицы 7.1. На последнем (восьмом) шаге выбирается подынтервал
[0.097481728, 0.097507477),
соответствующий символу EOF. В качестве результата можно взять любую точку из этого подынтервала. Выберем такое значение, которое имеет наименьшее число цифр в двоичной форме:
0.09748172810 = 0.000110001111010010012.
Таким образом, арифметическим кодом исходной последовательности будет
00011000111101001001.
Таблицы 6.4
Образование интервалов при арифметическом кодировании
| № | Интервалы | Символ |
| s 1: [0, 0.25) s 2: [0.025, 0.625) s 3: [0.625, 0.875) EOF: [0.875, 1) | s 1 | |
| s 1: [0, 0.0625) s 2: [0.0625, 0.15625) s 3: [0.15625, 0.21875) EOF: [0.21875, 0.25) | s 2 | |
| s 1: [0.0625, 0.0859375) s 2: [0.0859375, 0.12109375) s 3: [0.12109375, 0.14453125) EOF: [0.14453125, 0.15625) | s 2 | |
| s 1: [0.0859375, 0.094726563) s 2: [0.094726563, 0.107910156) s 3: [0.107910156, 0.116699219) EOF: [0.116699219, 0.12109375) | s 2 | |
| s 1: [0.094726563, 0.098022461) s 2: [0.098022461, 0.102966309) s 3: [0.102966309, 0.106262207) EOF: [0.106262207, 0.107910156) | s 1 | |
| s 1: [0.094726563, 0.095550538) s 2: [0.095550538, 0.096786499) s 3: [0.096786499, 0.097610474) EOF: [0.097610474, 0.098022461) | s 3 | |
| s 1: [0.096786499, 0.096992493) s 2: [0.096992493, 0.097301483) s 3: [0.097301483, 0.097507477) EOF: [0.097507477, 0.097610474) | s 3 | |
| s 1: [0.097301483, 0.097352982) s 2: [0.097352982, 0.097430229) s 3: [0.097430229, 0.097481728) EOF: [0.097481728, 0.097507477) | EOF |
Приведенный пример соответствует полуадаптивному методу. Существует также адаптивное арифметическое кодирование, основанное на модели, которая была рассмотрена при описании первого адаптивного метода сжатия по Хаффмену.
