Алгоритм кодирования Хаффмена, в лучшем случае, не может передавать на каждый символ сообщения менее одного бита информации. Предположим, известно, что в сообщении, состоящем из нулей и единиц, единицы встречаются в 10 раз чаще нулей. При кодировании методом Хаффмена и на 0 и на 1 придется тратить не менее одного бита. Но энтропия д. с.в., генерирующей такие сообщения ≈ 0.469 бит/сим. Не блочный метод Хаффмена дает для минимального среднего количества бит на один символ сообщения значение 1 бит. Хотелось бы иметь такую схему кодирования, которая позволяла бы кодировать некоторые символы менее чем одним битом. Одной из лучших среди таких схем является арифметическое кодирование, разработанное в 70-х годах XX века.
По исходному распределению вероятностей для выбранной для кодирования д. с. в. строится таблица, состоящая из пересекающихся только в граничных точках отрезков для каждого из значений этой д.с.в.; объединение этих отрезков должно образовывать отрезок [0, 1], а их длины должны быть пропорциональны вероятностям соответствующих значений д. с. в. Алгоритм кодирования заключается в построении отрезка, однозначно определяющего данную последовательность значений д.с.в. Затем для построенного отрезка находится число, принадлежащее его внутренней части и равное целому числу, деленному на минимально возможную положительную целую степень двойки. Это число и будет кодом для рассматриваемой последовательности. Все возможные конкретные коды — это числа строго большие нуля и строго меньшие одного, поэтому можно отбрасывать лидирующий ноль и десятичную точку, но нужен еще один специальный код-маркер, сигнализирующий о конце сообщения.
Отрезки строятся так: если имеется отрезок для сообщения длины n−1, то для построения отрезка для сообщения длины n, разбиваем его на столько же частей, сколько значений имеет рассматриваемая д.с.в. Это разбиение делается совершенно так-же как и самое первое (с сохранением порядка). Затем выбирается из полученных отрезков тот, который соответствует заданной конкретной последовательности длины n. Принципиальное отличие этого кодирования от рассмотренных ранее методов в его непрерывности, т.е. в ненужности блокирования. Код здесь строится не для отдельных значений д. с.в. или их групп фиксированного размера, а для всего предшествующего сообщения в целом. Эффективность арифметического кодирования растет с ростом длины сжимаемого сообщения (для кодирования Хаффмена или Шеннона-Фэно этого не происходит). Хотя арифметическое кодирование дает обычно лучшее сжатие, чем кодирование Хаффмена, оно пока используется на практике сравнительно редко, т.к. оно появилось гораздо позже и требует больших вычислительных ресурсов.
При сжатии заданных данных, например, из файла все рассмотренные методы требуют двух проходов. Первый для сбора частот символов, используемых как приближенные значения вероятностей символов, и второй для собственно сжатия.
Пример арифметического кодирования.
Пусть д.с.в. X может принимать только два значения 0 и 1 с вероятностями 2/3 и 1/3 соответственно. Сопоставим значению 0 отрезок [0, 2/3], а 1 — [2/3, 1]. Тогда для д.с.в. X→ , dim(X→) = 3, HX = H X→/3 = log2 3 − 2/3 ≈ 0.9183 бит/сим., таблица построения кодов
ML1(X→) = 65/81 ≈ 0.8025 бит/сим. (арифметическое),
ML1(X→) = 76/81 ≈ 0.9383 бит/сим. (блочный Хаффмена),
ML1(X) = ML(X) = 1 бит/сим. (Хаффмена).
Среднее количество бит на единицу сообщения для арифметического кодирования получилось меньше, чем энтропия. Это связано с тем, что в рассмотренной простейшей схеме кодирования, не описан код-маркер конца сообщения, введение которого неминуемо сделает это среднее количество бит большим энтропии.
Получение исходного сообщения из его арифметического кода происходит по следующему алгоритму:
Шаг 1
В таблице для кодирования значений д.с.в. определяется интервал, содержащий текущий код, — по этому интервалу однозначно определяется один символ исходного сообщения. Если этот символ — это маркер конца сообщения, то конец.
Шаг 2
Из текущего кода вычитается нижняя граница содержащего его интервала, полученная разность делится на длину этого же интервала. Полученное число считается новым текущим значением кода. Переход к шагу 1.
Рассмотрим, например, распаковку сообщения 111. Этому сообщению соответствует число 7/8 ∈ [2/3, 1], что означает, что первый знак декодируемого сообщения — это 1. Далее от 7/8 вычитается 2/3 и результат делится на 1/3, что дает 5/8 ∈ [0, 2/3], что означает, что следующий знак — 0. Теперь, вычислив (5/8 − 0) * 3/2 = 15/16 ∈ [2/3, 1], получим следующий знак — 1, т.е. все исходное сообщение 101 декодировано. Однако, из-за того, что условие остановки не определенно, алгоритм декодирования здесь не остановится и получит “следующий символ” 1 и т.д.