Введение
Форма энтропийного кодирования, используемая при сжатии данных. Арифметическое кодирование (AC) — это форма энтропийного кодирования, применяемая при сжатии данных без потерь. Обычно строка символов представляется фиксированным количеством бит на символ, как, например, в коде ASCII. При преобразовании строки в арифметический код часто используемые символы хранятся меньшим количеством бит, а редко встречающиеся — большим, что в итоге приводит к уменьшению общего количества используемых бит. Арифметическое кодирование отличается от других форм энтропийного кодирования, таких как кодирование Хаффмана, тем, что вместо разделения входных данных на отдельные символы и замены каждого кодом, оно кодирует всё сообщение в одно число — дробь произвольной точности q, где 0.0 ≤ q < 1.0. Информация представляется в виде диапазона, определяемого двумя числами. Недавнее семейство энтропийных кодировщиков, называемое асимметричными численными системами, обеспечивает более быструю реализацию благодаря непосредственной работе с одним натуральным числом, представляющим текущую информацию.
Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression. Normally, a string of characters is represented using a fixed number of bits per character, as in the ASCII code. When a string is converted to arithmetic encoding, frequently used characters will be stored with fewer bits and not so frequently occurring characters will be stored with more bits, resulting in fewer bits used in total. Arithmetic coding differs from other forms of entropy encoding, such as Huffman coding, in that rather than separating the input into component symbols and replacing each with a code, arithmetic coding encodes the entire message into a single number, an arbitrary precision fraction q, where 0.0 ≤ q < 1.0. It represents the current information as a range, defined by two numbers. A recent family of entropy coders called asymmetric numeral systems allows for faster implementations thanks to directly operating on a single natural number representing the current information.
Равные вероятности
В самом простом случае вероятность появления каждого символа одинакова. Например, рассмотрим набор из трех символов, A, B и C, каждый из которых равновероятен. Кодирование символов по одному потребует 2 бита на символ, что неэффективно: одна из возможных комбинаций битов не используется. То есть, символы A, B и C могут быть закодированы соответственно как 00, 01 и 10, при этом 11 остаётся неиспользованным. Более эффективное решение – представить последовательность этих трех символов в виде рационального числа в троичной системе счисления, где каждая цифра соответствует символу. Например, последовательность "ABBCAB" может быть представлена как 0.0112013, а в арифметическом кодировании – как значение в интервале [0, 1). Следующий шаг – кодирование этого троичного числа с использованием двоичного числа с фиксированной точкой, обладающего достаточной точностью для его восстановления, например, 0.00101100012 – это всего 10 бит; по сравнению с наивным блочным кодированием экономится 2 бита. Это осуществимо для длинных последовательностей, поскольку существуют эффективные алгоритмы для преобразования основания чисел произвольной точности. Для декодирования значения, зная, что исходная строка имеет длину 6, можно просто преобразовать число обратно в троичную систему счисления, округлить до 6 знаков и восстановить строку.
Адаптированное арифметическое кодирование
Одним из преимуществ арифметического кодирования перед другими подобными методами сжатия данных является простота адаптации. Адаптация заключается в изменении таблиц частот (или вероятностей) в процессе обработки данных. Декодированные данные будут соответствовать исходным, если таблица частот при декодировании обновляется тем же способом и на том же шаге, что и при кодировании. Синхронизация обычно основана на комбинации символов, встречающихся в процессе кодирования и декодирования.
Асимптотическое равноразделение
Мы можем понять это интуитивно. Предположим, что источник эргодичен, тогда он обладает свойством асимптотического равнораспределения (AEP). Согласно AEP, после длинной последовательности символов, интервал почти полностью разбивается на интервалы почти одинакового размера. Точнее, для любого малого ε, для всех достаточно больших n, существуют строки S, такие что каждая строка имеет почти одинаковую вероятность P(S), и их суммарная вероятность равна 1.
For any such string, it is arithmetically encoded by a binary string of length , where is the smallest such that there exists a fraction of form in the interval for Since the interval for has size , we should expect it to contain one fraction of form when
Thus, with high probability, can be arithmetically encoded with a binary string of length .
Для любой такой строки S, она арифметически кодируется двоичной строкой длины n, где n – наименьшее число, такое что существует дробь вида k/2^n в интервале для P(S). Поскольку интервал для P(S) имеет размер ε, мы должны ожидать, что он содержит одну дробь вида k/2^n, когда ε = 1/2^n.
For any such string, it is arithmetically encoded by a binary string of length , where is the smallest such that there exists a fraction of form in the interval for Since the interval for has size , we should expect it to contain one fraction of form when
Thus, with high probability, can be arithmetically encoded with a binary string of length .
Таким образом, с высокой вероятностью, S может быть арифметически закодирован двоичной строкой длины n.
For any such string, it is arithmetically encoded by a binary string of length , where is the smallest such that there exists a fraction of form in the interval for Since the interval for has size , we should expect it to contain one fraction of form when
Thus, with high probability, can be arithmetically encoded with a binary string of length .
Кодирование Хаффмана
Поскольку арифметическое кодирование не сжимает данные по одному, оно может произвольно приближаться к энтропии при сжатии строк IID. В отличие от него, расширение кодирования Хаффмана для строк не достигает энтропии, если только все вероятности символов алфавита не являются степенями двойки, в этом случае как кодирование Хаффмана, так и арифметическое кодирование достигают энтропии. При наивном кодировании двоичных строк кодированием Хаффмана сжатие невозможно, даже если энтропия низкая (например, для ({0, 1}) с вероятностями {0,95, 0,05}). Кодирование Хаффмана присваивает 1 бит каждому значению, в результате чего получается код той же длины, что и входные данные. Напротив, арифметическое кодирование хорошо сжимает биты, приближаясь к оптимальному коэффициенту сжатия. Один из простых способов устранить субоптимальность кодирования Хаффмана — это конкатенация символов ("блокирование") для формирования нового алфавита, в котором каждый новый символ представляет собой последовательность исходных символов — в данном случае битов — из исходного алфавита. В приведенном выше примере, группировка последовательностей из трех символов перед кодированием приведет к новым "суперсимволам" со следующими частотами:
: 85.7%
, , : 4.5% каждый
, , : 0.24% каждый
: 0.0125%
One simple way to address Huffman coding's suboptimality is to concatenate symbols ("blocking") to form a new alphabet in which each new symbol represents a sequence of original symbols – in this case bits – from the original alphabet. In the above example, grouping sequences of three symbols before encoding would produce new "super symbols" with the following frequencies:
: 85.7%
, , : 4.5% each
, , : 0.24% each
: 0.0125%
With this grouping, Huffman coding averages 1.3 bits for every three symbols, or 0.433 bits per symbol, compared with one bit per symbol in the original encoding, i. e., compression. Allowing arbitrarily large sequences gets arbitrarily close to entropy – just like arithmetic coding – but requires huge codes to do so, so is not as practical as arithmetic coding for this purpose. An alternative is encoding run lengths via Huffman based Golomb Rice codes. Such an approach allows simpler and faster encoding/decoding than arithmetic coding or even Huffman coding, since the latter requires a table lookups. In the {0.95, 0.05} example, a Golomb Rice code with a four bit remainder achieves a compression ratio of , far closer to optimum than using three bit blocks. Golomb Rice codes only apply to Bernoulli inputs such as the one in this example, however, so it is not a substitute for blocking in all cases.
При таком группировании кодирование Хаффмана в среднем дает 1.3 бита на каждые три символа, или 0.433 бита на символ, по сравнению с одним битом на символ при исходном кодировании, то есть сжатие. Разрешение произвольно больших последовательностей позволяет произвольно приближаться к энтропии — как и арифметическое кодирование — но требует для этого огромных кодов, поэтому это не так практично, как арифметическое кодирование для этой цели. Альтернативой является кодирование длин серий с использованием кодов Голомба-Райса на основе Хаффмана. Такой подход обеспечивает более простое и быстрое кодирование/декодирование, чем арифметическое кодирование или даже кодирование Хаффмана, поскольку последнее требует поиска в таблице. В примере {0,95, 0,05} код Голомба-Райса с четырехбитным остатком достигает коэффициента сжатия , что намного ближе к оптимальному, чем при использовании трехбитных блоков. Однако коды Голомба-Райса применимы только к входным данным Бернулли, таким как в этом примере, поэтому они не заменяют блокирование во всех случаях.
One simple way to address Huffman coding's suboptimality is to concatenate symbols ("blocking") to form a new alphabet in which each new symbol represents a sequence of original symbols – in this case bits – from the original alphabet. In the above example, grouping sequences of three symbols before encoding would produce new "super symbols" with the following frequencies:
: 85.7%
, , : 4.5% each
, , : 0.24% each
: 0.0125%
With this grouping, Huffman coding averages 1.3 bits for every three symbols, or 0.433 bits per symbol, compared with one bit per symbol in the original encoding, i. e., compression. Allowing arbitrarily large sequences gets arbitrarily close to entropy – just like arithmetic coding – but requires huge codes to do so, so is not as practical as arithmetic coding for this purpose. An alternative is encoding run lengths via Huffman based Golomb Rice codes. Such an approach allows simpler and faster encoding/decoding than arithmetic coding or even Huffman coding, since the latter requires a table lookups. In the {0.95, 0.05} example, a Golomb Rice code with a four bit remainder achieves a compression ratio of , far closer to optimum than using three bit blocks. Golomb Rice codes only apply to Bernoulli inputs such as the one in this example, however, so it is not a substitute for blocking in all cases.
Показатели и другие технические характеристики
Каждая программная реализация арифметического кодирования обладает своим собственным коэффициентом сжатия и производительностью. Хотя коэффициенты сжатия меняются незначительно (обычно менее 1%), время выполнения кода может отличаться в 10 раз. Выбор подходящего кодировщика из списка общедоступных – непростая задача, так как производительность и коэффициент сжатия зависят также от типа данных, в особенности от размера алфавита (количества различных символов). Один из двух конкретных кодировщиков может показывать лучшую производительность для небольших алфавитов, а другой – для больших. Большинство кодировщиков имеют ограничения на размер алфавита, и многие из них специализированы для алфавитов, состоящих ровно из двух символов (0 и 1).