Принципы арифметического кодирования. Преимущество арифметического кодирования перед кодированием по Хаффману

Как и в алгоритме Хаффмана, все начинается с таблицы элементов и соответствующих вероятностей. Допустим, входной алфавит состоит всего из трех элемен­тов: a ₁, a ₂ и a ₃, и при этом

P(a ₁) = 1/2

P(a ₂) = 1/3

P(a ₃) = 1/6

Предположим также, что нам надо закодировать последовательность a ₁, a ₁, a ₂, a ₃.

Разобьем полуинтервал [0, 1) на три части в соответствии с вероятностями элементов:

Элементу a ₁ будет соответствовать диапазон [0, 1/2); элементу a ₂ диапазон [1/2, 1/2 + 1/3), а элементу a ₃ - диапазон [1/2 +1/3, 1).

Первый элемент сжимаемого файла равен а ₁. Выберем полуинтервал, соответствующий ему [0, 1/2):

Разобьем его таким же образом на три части:

Поскольку второй элемент сжимаемой последовательности тоже равен a ₁, снова выбираем самый нижний диапазон (точнее, теперь уже поддиапазон [0, 1/4)):

Аналогичным образом, продолжая процесс для оставшихся элементов входного файла а ₂ и а ₃, получаем такой рисунок:

Последним полученным диапазоном будет [5/24, 1/4). Теперь -внимание! Любое число из этого диапазона (например, 0,22) однозначно описывает весь входной файл. Зная вероятности появления элементов, декодер может правильно разбить диапазон [0, 1) на три части и определить, что число 0,22 находится в поддиапазоне [0, 1/2). В свою очередь, это означает, что первый элемент декодированного файла равен а ₁. Затем декодер разобьет диапазон [0, 1/2) на три части и определит, что число 0,22 находится в поддиапазоне [0, 1/4), следовательно, следующий элемент выходного файла — снова а ₁ и т. д.

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

Хотя для описания сжимаемого файла годится любое число конечного диапазона (0.22, 0.222, 0.222222222222,...), выбирать надо, разумеется, то, которое содержит меньше цифр, поскольку каждая лишняя цифра увеличивает размер выходного файла.

Формирование одного (длинного) кода для всего потока символов.

Присвоение кода всему передаваемому сообщению, а не отдельным его символам.