Арифметическое кодирование

Форма энтропийного кодирования, используемая при сжатии данных

Арифметическое кодирование - это форма энтропийного кодирования используется в сжатии данных без потерь. Обычно строка символов, такая как слова «здравствуйте!», Представлена ​​с использованием фиксированного количества бит на символ, как в коде ASCII. Когда строка преобразуется в арифметическое кодирование, часто используемые символы будут храниться с меньшим количеством битов, а не так часто встречающиеся символы будут сохранены с большим количеством битов, что приведет к использованию меньшего количества битов в целом. Арифметическое кодирование отличается от других форм энтропийного кодирования, таких как кодирование Хаффмана, тем, что вместо разделения ввода на составляющие символы и замены каждого кода кодом арифметическое кодирование кодирует все сообщение в одно число, произвольной точности дробь q, где 0,0 ≤ q < 1.0. It represents the current information as a range, defined by two numbers. Recent family of entropy coders called асимметричные системы счисления позволяют ускорить реализацию благодаря непосредственной работе с одним натуральным числом, представляющим текущую информацию.

Пример арифметического кодирования, предполагающий фиксированное распределение вероятностей трех символов «A», «B» и «C». Вероятность «A» составляет 50%, вероятность «B» составляет 33%, а вероятность «C» составляет 17%. Кроме того, мы предполагаем, что глубина рекурсии известна на каждом этапе. На первом этапе мы кодируем «B», который находится внутри интервала [0,5, 0,83): двоичное число «0,10x» - это самый короткий код, который представляет интервал, полностью находящийся внутри [0,5, 0,83). «x» означает произвольную последовательность битов. Есть два крайних случая: наименьший x обозначает ноль, который представляет левую часть представленного интервала. Тогда левая часть интервала равна dec (0,10) = 0,5. С другой стороны, x обозначает конечную последовательность единиц, верхний предел которой dec (0.11) = 0,75. Следовательно, «0,10x» представляет интервал [0,5, 0,75), который находится внутри [0,5, 0,83). Теперь мы можем опустить "0". часть, поскольку все интервалы начинаются с "0". и мы можем игнорировать часть «x», потому что независимо от того, какую битовую последовательность она представляет, мы останемся внутри [0,5, 0,75).

Содержание

• 1 Детали реализации и примеры
  • 1.1 Равные вероятности
  • 1.2 Определение модели
  • 1.3 Кодирование и декодирование: обзор
  • 1.4 Кодирование и декодирование: пример
  • 1.5 Источники неэффективности
• 2 Адаптивное арифметическое кодирование
• 3 Точность и перенормировка
• 4 Арифметическое кодирование как обобщенное изменение системы счисления
  • 4.1 Теоретический предел сжатого сообщения
• 5 Связь с другими методами сжатия
  • 5.1 Кодирование Хаффмана
• 6 История и патенты
• 7 Контрольные показатели и другие технические характеристики
• 8 См. также
• 9 Примечания
• 10 Ссылки
• 11 Внешние ссылки

Детали и примеры реализации

Кодирование сообщения «WIKI» с арифметическим кодированием

1.	Найдены частоты букв.
2.	Интервал [0, 1) разбивается по соотношению частот.
3–5.	Соответствующий интервал итеративно разделяется для каждой буквы в сообщении.
6.	Для представления сообщения выбирается любое значение в последнем интервале.
2 * –6 *.	Разделение и значение, если вместо этого сообщение было "KIWI".

Приведенный выше пример визуализирован в виде круга, значения в красной кодировке «WIKI» и «KIWI» - в изображении SVG наведите указатель мыши на интервал, чтобы выделить его и отобразить его статистику

Равно вероятности

В простейшем случае вероятность появления каждого символа равна. Например, рассмотрим набор из трех символов: A, B и C, вероятность появления каждого из которых одинакова. Простое блочное кодирование потребует 2 бита на символ, что расточительно: один из вариантов битов никогда не используется. То есть A = 00, B = 01 и C = 10, но 11 не используется.

Более эффективное решение состоит в том, чтобы представить последовательность этих трех символов в виде рационального числа с основанием 3, где каждая цифра представляет символ. Например, последовательность «ABBCAB» может стать 0,011201 3 в арифметическом кодировании как значение в интервале [0, 1). Следующим шагом является кодирование этого троичного числа с использованием двоичного числа с фиксированной запятой достаточной точности для его восстановления, например 0,0010110010 2 - это всего лишь 10 бит; 2 бита сохраняются по сравнению с наивным блочным кодированием. Это возможно для длинных последовательностей, потому что существуют эффективные оперативные алгоритмы преобразования базы произвольно точных чисел.

Чтобы декодировать значение, зная, что исходная строка имеет длину 6, можно просто преобразовать обратно в основание 3, округлить до 6 цифр и восстановить строку.

Определение модели

В общем, арифметические кодеры могут выдавать почти оптимальный результат для любого заданного набора символов и вероятностей (оптимальное значение - -log 2 P битов для каждого символа с вероятностью P см. теорему кодирования источника ). Алгоритмы сжатия, использующие арифметическое кодирование, начинают с определения модели данных - в основном это предсказание того, какие шаблоны будут найдены в символах сообщения. Чем точнее этот прогноз, тем ближе к оптимальному будет результат.

Пример : простая статическая модель для описания выходных данных конкретного инструмента мониторинга с течением времени может быть:

• Вероятность 60% символа НЕЙТРАЛЬНО
• Вероятность 20% символа ПОЛОЖИТЕЛЬНЫЙ
• 10% шанс символа ОТРИЦАТЕЛЬНЫЙ
• 10% шанс символа END-OF-DATA. (Наличие этого символа означает, что поток будет «внутренне завершен», что довольно часто встречается при сжатии данных; когда этот символ появляется в потоке данных, декодер будет знать, что весь поток был декодирован.)

Модели могут также работать с алфавитами, отличными от простого набора из четырех символов, выбранного для этого примера. Также возможны более сложные модели: моделирование более высокого порядка изменяет свою оценку текущей вероятности символа на основе символов, предшествующих ему (контекста), так что в модели для английского текста, например, процентная вероятность " u »будет намного выше, если оно следует за« Q »или« q ». Модели могут быть даже адаптивными, чтобы они постоянно меняли свой прогноз данных в зависимости от того, что фактически содержит поток. Декодер должен иметь ту же модель, что и кодировщик.

Кодирование и декодирование: обзор

В общем, каждый шаг процесса кодирования, за исключением самого последнего, одинаков; кодировщик должен учитывать всего три части данных:

• следующий символ, который необходимо закодировать
• текущий интервал (в самом начале процесса кодирования интервал установлен на [0,1], но это изменится)
• Вероятности, которые модель присваивает каждому из различных символов, которые возможны на этом этапе (как упоминалось ранее, модели более высокого порядка или адаптивные модели означают, что эти вероятности не обязательно одинаковы на каждом шаге.)

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

Пример : для четырехсимвольной модели выше:

• интервал для НЕЙТРАЛЬНОГО будет [0, 0,6)
• интервал для ПОЛОЖИТЕЛЬНОГО будет [0,6, 0,8)
• интервал для ОТРИЦАТЕЛЬНЫХ ДАННЫХ будет [0,8, 0,9)
• интервал для КОНЕЦ-ДАННЫХ будет [0,9, 1).

Когда все символы будут закодированы, полученный интервал однозначно определяет последовательность символов, которые его породили. Любой, кто имеет тот же конечный интервал и модель, которые используются, может восстановить последовательность символов, которая должна была быть введена в кодировщик, чтобы получить этот конечный интервал.

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

Кодирование и декодирование: пример

Диаграмма, показывающая декодирование 0,538 (круговая точка) в модели примера. Область делится на подобласти, пропорциональные частотам символов, затем подобласть, содержащая точку, последовательно подразделяется таким же образом.

Рассмотрим процесс декодирования сообщения, закодированного с помощью данной четырехсимвольной модели. Сообщение закодировано в дробной части 0,538 (для ясности используется десятичная дробь, а не двоичная; также предполагается, что имеется ровно столько цифр, сколько необходимо для декодирования сообщения.)

Процесс начинается с того же интервала, который используется кодировщик: [0,1), и используя ту же модель, разделив его на те же четыре подинтервала, которые должен иметь кодировщик. Доля 0,538 попадает в подинтервал НЕЙТРАЛЬНО, [0, 0,6); это означает, что первый символ, который считал кодировщик, должен быть НЕЙТРАЛЬНЫМ, поэтому это первый символ сообщения.

Затем разделите интервал [0, 0,6) на подинтервалы:

• интервал для НЕЙТРАЛЬНОГО будет [0, 0,36), 60% от [0, 0,6).
• интервал для ПОЛОЖИТЕЛЬНОГО будет [0,36, 0,48), 20% от [0, 0,6).
• интервал для ОТРИЦАТЕЛЬНОГО будет [0,48, 0,54), 10% от [0, 0,6).
• интервал для END-OF-DATA будет [0,54, 0,6), 10% от [0, 0,6).

Поскольку.538 находится в интервале [0,48, 0,54), второй символ сообщение должно быть ОТРИЦАТЕЛЬНЫМ.

Снова разделите наш текущий интервал на подинтервалы:

• интервал для НЕЙТРАЛЬНОГО будет [0,48, 0,516).
• интервал для ПОЛОЖИТЕЛЬНОГО будет [0,516, 0,528).
• интервал для ОТРИЦАТЕЛЬНЫХ ДАННЫХ будет [0,528, 0,534).
• интервал для КОНЕЦ-ДАННЫХ будет [0,534, 0,540).

Теперь 0,538 попадает в интервал Символ КОНЕЦ ДАННЫХ; следовательно, это должен быть следующий символ. Поскольку это также внутренний символ завершения, это означает, что декодирование завершено. Если поток не завершен изнутри, должен быть другой способ указать, где поток останавливается. В противном случае процесс декодирования мог бы продолжаться вечно, ошибочно считывая из дроби больше символов, чем было фактически закодировано в ней.

Источники неэффективности

Сообщение 0,538 в предыдущем примере могло быть закодировано одинаково короткими дробями 0,534, 0,535, 0,536, 0,537 или 0,539. Это говорит о том, что использование десятичного числа вместо двоичного привело к некоторой неэффективности. Это верно; информационное содержание трехзначного десятичного числа: $3\; \ast \; log\; 2\; \; (10)\; \approx \; 9.966\; \{\backslash \; displaystyle\; 3\; *\; \backslash \; log\; \_\; \{2\}\; (10)\; \backslash \; приблизительно\; 9.966\}$бит ; то же сообщение могло быть закодировано в двоичной дроби 0,10001010 (эквивалентно 0,5390625 десятичной дроби) всего за 8 бит. (Конечный ноль должен быть указан в двоичной дроби, иначе сообщение будет неоднозначным без внешней информации, такой как размер сжатого потока.)

Этот 8-битный вывод больше информационного содержимого, или энтропия сообщения, которая равна

$\sum \; -\; log\; 2\; \; (pi)\; =\; -\; log\; 2\; \; (0.6)\; -\; log\; 2\; \; (0.1)\; -\; log\; 2\; \; (0.1)\; =\; 7.381\; бит\; \{\backslash \; displaystyle\; \backslash \; сумма\; -\; \backslash \; log\; \_\; \{2\}\; (p\_\; \{i\})\; =\; -\; \backslash \; log\; \_\; \{2\}\; (0,6)\; -\; \backslash \; log\; \_\; \{2\}\; (0,1)\; -\; \backslash \; log\; \_\; \{2\}\; (0,1)\; =\; 7,381\; \{\backslash \; текст\; \{bits\}\}\}$

Но при двоичном кодировании должно использоваться целое число бит, поэтому кодировщик для этого сообщения будет использовать не менее 8 бит, в результате чего сообщение будет на 8,4% больше, чем содержимое энтропии. Эта неэффективность, равная максимум 1 биту, приводит к относительно меньшим накладным расходам при увеличении размера сообщения.

Кроме того, заявленные вероятности символа были [0,6, 0,2, 0,1, 0,1), но фактические частоты в этом примере равны [0,33, 0, 0,33, 0,33). Если интервалы перенастроить для этих частот, энтропия сообщения будет 4,755 битов, и то же самое сообщение НЕЙТРАЛЬНО ОТРИЦАТЕЛЬНЫЙ КОНЕЦ ДАННЫХ может быть закодировано как интервалы [0, 1/3); [1/9, 2/9); [27.05, 27.06); и двоичный интервал [0,00101111011, 0,00111000111). Это также пример того, как методы статистического кодирования, такие как арифметическое кодирование, могут создавать выходное сообщение, которое больше входного сообщения, особенно если вероятностная модель отключена.

Адаптивное арифметическое кодирование

Одним из преимуществ арифметического кодирования над другими подобными методами сжатия данных является удобство адаптации. Адаптация - это изменение таблиц частот (или вероятностей) при обработке данных. Декодированные данные соответствуют исходным данным до тех пор, пока частотная таблица при декодировании заменяется таким же образом и на том же этапе, что и при кодировании. Синхронизация, как правило, основана на комбинации символов, возникающих в процессе кодирования и декодирования.

Точность и перенормировка

Приведенные выше объяснения арифметического кодирования содержат некоторые упрощения. В частности, они записываются так, как если бы кодировщик сначала вычислил дроби, представляющие конечные точки интервала полностью, используя бесконечную precision, и преобразовал дробь в ее окончательную форму только в конце кодирования. Вместо того, чтобы пытаться имитировать бесконечную точность, большинство арифметических кодеров вместо этого работают с фиксированным пределом точности, который, как они знают, декодер сможет сопоставить, и округляют вычисленные дроби до их ближайших эквивалентов с этой точностью. Пример показывает, как это работало бы, если бы модель требовала деления интервала [0,1) на трети, и это было аппроксимировано с точностью до 8 бит. Обратите внимание, что, поскольку теперь известна точность, мы сможем использовать двоичные диапазоны.

Символ	Вероятность	Интервал, уменьшенный до восьмибитной точности		Диапазон
	(выраженный дробью)	(дробным числом)	(в двоичном формате)	(в двоичном формате)
A	1/3	[0, 85/256)	[0,00000000, 0,01010101)	00000000 - 01010100
B	1/3	[85/256, 171/256)	[0,01010101, 0,10101011)	01010101 - 10101010
C	1/3	[171/256, 1)	[0.10101011, 1.00000000)	10101011 - 11111111

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

Символ	Вероятность	Диапазон	Цифры, которые можно отправить на выход	Диапазон после перенормировки
A	1/3	00000000 - 0 1010100	0	0000000 0 - 1010100 1
B	1/3	01010101 - 10101010	Нет	01010101 - 10101010
C	1/3	10101011 - 1 1111111	1	0101011 0 - 1111111 1

Арифметическое кодирование как обобщенное изменение системы счисления

Напомним, что в В случае, когда символы имеют равные вероятности, арифметическое кодирование может быть реализовано простым изменением основания или системы счисления. В общем, арифметическое (и диапазонное) кодирование можно интерпретировать как обобщенное изменение radix. Например, мы можем рассматривать любую последовательность символов:

$DABDDB\; \{\backslash \; displaystyle\; DABDDB\}$

как число в определенной базе, предполагая, что задействованные символы образуют упорядоченный набор, а каждый символ в упорядоченном наборе обозначает последовательный целое число A = 0, B = 1, C = 2, D = 3 и т. д. В результате получаются следующие частоты и совокупные частоты:

Символ	Частота появления	Накопленная частота
A	1	0
B	2	1
D	3	3

Накопленная частота для элемента - это сумма всех частот, предшествующих элементу. Другими словами, совокупная частота - это промежуточная сумма частот.

В позиционной системе счисления основание или основание численно равно количеству различных символов, используемых для выражения числа. Например, в десятичной системе число символов равно 10, а именно 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9. Система счисления используется для выражения любого конечного целого числа в предполагаемом множителе в полиномиальная форма. Например, число 457 на самом деле равно 4 × 10 + 5 × 10 + 7 × 10, где основание 10 предполагается, но не показано явно.

Сначала мы преобразуем DABDDB в число с основанием 6, потому что 6 - это длина строки. Строка сначала отображается в строку цифр 301331, которая затем преобразуется в целое число с помощью полинома:

$6\; 5\; \times \; 3\; +\; 6\; 4\; \times \; 0\; +\; 6\; 3\; \times \; 1\; +\; 6\; 2\; \times \; 3\; +\; 6\; 1\; \times \; 3\; +\; 6\; 0\; \times \; 1\; =\; 23671\; \{\backslash \; displaystyle\; 6\; ^\; \{5\}\; \backslash \; times\; 3\; +\; 6\; ^\; \{4\}\; \backslash \; times\; 0\; +\; 6\; ^\; \{3\}\; \backslash \; times\; 1\; +\; 6\; ^\; \{2\}\; \backslash \; times\; 3\; +\; 6\; ^\; \{1\}\; \backslash \; times\; 3\; +\; 6\; ^\; \{0\}\; \backslash \; times\; 1\; =\; 23671\}$

Результат 23671 имеет длину 15 бит, что не очень близко к теоретическому пределу (энтропия сообщения), что составляет примерно 9 бит.

Чтобы закодировать сообщение с длиной, близкой к теоретическому пределу, налагаемому теорией информации, нам нужно немного обобщить классическую формулу для изменения системы счисления. Мы вычислим нижнюю и верхнюю границы L и U и выберем число между ними. Для вычисления L мы умножаем каждый член в приведенном выше выражении на произведение частот всех ранее встречающихся символов:

$L\; =\; (6\; 5\; \times \; 3)\; +\; 3\; \times \; (6\; 4\; \times \; 0)\; +\; (3\; \times \; 1)\; \times \; (6\; 3\; \times \; 1)\; +\; (3\; \times \; 1\; \times \; 2)\; \times \; (6\; 2\; \times \; 3)\; +\; (3\; \times \; 1\; \times \; 2\; \times \; 3)\; \times \; (6\; 1\; \times \; 3)\; +\; (3\; \times \; 1\; \times \; 2\; \times \; 3\; \times \; 3)\; \times \; (6\; 0\; \times \; 1)\; =\; 25002\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; mathrm\; \{L\}\; =\; \{\}\; (6\; ^\; \{5\}\; \backslash \; times\; 3)\; +\; \{\}\; \backslash \backslash \; 3\; \backslash \; times\; (6\; ^\; \{4\}\; \backslash \; times\; 0)\; +\; \{\}\; \backslash \backslash \; (3\; \backslash \; times\; 1)\; \backslash \; times\; (6\; ^\; \{3\}\; \backslash \; times\; 1)\; +\; \{\}\; \backslash \backslash \; (3\; \backslash \; times\; 1\; \backslash \; times\; 2)\; \backslash \; times\; (6\; ^\; \{2\}\; \backslash \; times\; 3)\; +\; \{\}\; \backslash \backslash \; (3\; \backslash \; times\; 1\; \backslash \; times\; 2\; \backslash \; times\; 3)\; \backslash \; times\; (6\; ^\; \{1\}\; \backslash \; times\; 3)\; +\; \{\}\; \backslash \backslash \; (3\; \backslash \; times\; 1\; \backslash \; times\; 2\; \backslash \; times\; 3\; \backslash \; times\; 3)\; \backslash \; times\; (6\; ^\; \{0\}\; \backslash \; times\; 1)\; \{\}\; \backslash \backslash \; =\; \{\}\; 25002\; \backslash \; end\; \{align\}\}\}$

Разница между этим многочленом и указанным выше многочленом заключается в том, что каждый член умножается на произведение частот всех ранее встречающихся символов. В более общем смысле L можно вычислить как:

$L\; =\; \sum \; i\; =\; 1\; nnn\; -\; i\; C\; i\; \prod \; k\; =\; 1\; i\; -\; 1\; fk\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{L\}\; =\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{\; n\}\; n\; ^\; \{ni\}\; C\_\; \{i\}\; \{\backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{i-1\}\; f\_\; \{k\}\}\}$

где $C\; i\; \{\backslash \; displaystyle\; \backslash \; scriptstyle\; C\_\; \{i\}\; \}$- совокупные частоты, а $fk\; \{\backslash \; displaystyle\; \backslash \; scriptstyle\; f\_\; \{k\}\}$- частоты появления. Индексы обозначают положение символа в сообщении. В особом случае, когда все частоты $f\; k\; \{\backslash \; displaystyle\; \backslash \; scriptstyle\; f\_\; \{k\}\}$равны 1, это формула замены базы.

Верхняя граница U будет равна L плюс произведение всех частот; в данном случае U = L + (3 × 1 × 2 × 3 × 3 × 2) = 25002 + 108 = 25110. В общем случае U определяется по формуле:

$U\; =\; L\; +\; \prod \; k\; =\; 1\; nfk\; \{\backslash \; displaystyle\; \backslash \; mathrm\; \{U\}\; =\; \backslash \; mathrm\; \{L\}\; +\; \backslash \; prod\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; f\_\; \{k\}\}$

Теперь мы можем выбрать любое число из интервала [L, U)