716 Тем для обсуждения

6,563 Открытых обсуждений

Непростая арифметика: кодирование

Dmitry Serkin (Intel) (24 пост(а)) 20.12.2011 14:47

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

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

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

Существенное отличие арифметического кодирования от других подходов энтропийного сжатия состоит в том, что метод не пытается построить взаимнооднозначное соответствие между символом или группой символов и кодовым словом, подобно тому, как это делают алгоритмы семейства variable length coding. Арифметическое кодирование кодирует всю информацию целиком. Символ за символом метод формирует конечное битовое представление, действительное число в интервале [0, 1). Чтобы понять, нужно разобраться в природе кода.

Код последовательности есть действительное число с дробной частью, которая равна этой последовательность. То есть переход от последовательности к коду есть ничто иное как добавление в начало «0.». В качестве примера, возьмем последовательность выходных бит 01010010110, которые порождает арифметическое кодирование, тогда 01010010110 – есть ничто иное как закодированная последовательность, 0.01010010110 = 0.6898797800010 – кодовое значение, действительное число.

Подобная конструкция создает удобную связь между бесконечной последовательностью символов из D-символьного (в нашем примере 2х или 10-ти) алфавита и реальными числами в полуинтервале [0, 1), где любая последовательность может быть представлена в виде действительного числа и наоборот.

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

Где S – входная последовательность, а α и β действительные числа, такие что:

Для упрощения принято представлять интервалы в иной форме:

Тогда интервалы представляют следующим множеством рекурсивных выражений:

Процесс кодирования необходимо проиллюстрировать примером. Рассмотрим алфавит из 4 элементов со следующим распределением вероятностей p = [0.2, 0.5, 0.2, 0.1]. Входная последовательность: a2a1a0a0a1a3. Разберем шаги алгоритма арифметического кодирования:

1. Сперва задается «текущий интервал» [0,1).
2. Далее повторяем следующие действия до последнего входного элемента: делим текущий интервал на части пропорционально вероятностям каждого символа, выбираем подынтервал, соответствующий текущему входному символу, и назначаем его новым текущим интервалом.
3. Результатом будет любая точка внутри конечного интервала.

Графическая иллюстрация:

Обработав последний входной символ (понять, что он последний можно по специальному маркеру или дополнительно передав информацию о размере входного потока), мы получили интервал [0.7426, 0.7428] внутри которого содержится бесконечное множество действительных чисел. Осталось выбрать одно, тем самым сделав финальный шаг всего процесса. Кодовое значение не может быть передано в форме действительного числа, его необходимо представить в форме выбранной системы счисления. Так как число из интервала может быть абсолютно любым, то естестевенно выбрать наиболее удобный вариант для представления, то есть наиболее короткий. В нашем примере, в случае десятичной системы наиболее короткое число 0.7426, в двоичной 0.10111110001 = 0.74267578125.

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

При написании заметки использовалась замечательная статья в которой вы можете найти информацию для дальнейшего погружения в тему.

Категории: Intel Software Network
Метки: arithmetic coding, entropy coding

Пожалуйста, обратитесь к странице Уведомление об оптимизации для более подробной информации относительно производительности и оптимизации в программных продуктах компании Intel.

Комментарии (8)

Обратная ссылка (4)

• Непростая арифметика: ода индукции – Блоги - ISN
  25.12.2011 23:57
• Непростая арифметика: декодирование – Блоги - ISN
  26.12.2011 05:31
• Непростая арифметика: декодирование – Блоги - ISN
  27.12.2011 00:15
• Интервальное кодирование (Range encoding), как частный случай кодирования арифметического – Блоги - ISN
  27.12.2011 23:11

Оставить комментарий  

Имя (обязательно)*

Электронная почта (обязательно; не будет отображено на этой странице)*

Ваш URL-адрес (необязательно)


Комментарий*