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

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

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

Содержание

Введение

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

Написано по статье Иринёва Антона и Каширина Виктора [1]

Алгоритм

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

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

Пример

Произведем кодирование слова “ABBACD”

На первом шаге веса всех символов равны единице. Текущий интервал [0,1]. Первым кодируется символ A. Так как символов 4, и их веса одинаковые, то мы берем четверть от исходного отрезка. Получается интервал [0, 1/4]. Символ A обработан, увеличиваем его вес на единицу. Общий вес так же увеличился на 1. Следующим кодируется символ B. Разбиваем текущий интервал соответственно отношениям весов символов к весу всех символов. Выбираем интервал, соответствующий символу B - [1/10, 3/20]. Увеличиваем вес символа B на единицу, и так далее. Все шаги подробно описаны в таблице:

A B C D Общий вес Кодируемая буква Текущая длина промежутка Получившийся интервал
1 1 1 1 4 A 1 [0, 1/4]
2 1 1 1 5 B 1/4 [1/10, 3/20]
2 2 1 1 6 B 1/20 [7/60, 8/60]
2 3 1 1 7 A 1/60 [7/60, 51/420]
3 3 1 1 8 C 1/210 [202/1680, 203/1680]
3 3 2 1 9 D 1/1680 [1826/15120, 1827/15120]



1979/16384 = 1979/214, отсюда получаем, что исходное сообщение можно представить двоичным числом 0.000111101110112 є [1826/15120, 1827/15120]. Таким образом, мы закодировали сообщение с помощью 14 битов. ML = 2.3 бит/сим.

распакуем код 00011110111011, зная множество символов, из которых состояло исходное сообщение. Итак, 000111101110112 = 1979/16384. Результаты расчетов приведены в таблице:

A B C D Число-код и его интервал Декодируемый символ Длина интервала
1 1 1 1 1979/16384 є [0, 1/4] A 1/4
2 1 1 1 1979/4096 є [2/5, 3/5] B 1/5
2 2 1 1 1703/4096 є [1/3, 2/3] B 1/3
2 3 1 1 1013/4096 є [0, 2/7] A 2/7
3 3 1 1 7091/8192 є [6/8, 7/8] C 1/8
3 3 2 1 7576/8192 є [8/9, 1] D 1/9

Реализация кодера

Реализация декодера

Применение

Необходимость применения адаптивного алгоритма возникает в том случае, если вероятностные оценки для символов сообщения неизвестны до начала работы алгоритма:

  • сжатие поточных данных

Литература

  1. Семенюк В. В. Экономное кодирование дискретной информации. – СПб.: СПбГИТМО (ТУ), 2001 (доступна на [2]).

Wikimedia Foundation. 2010.

Нужен реферат?

Полезное


Смотреть что такое "Адаптивное арифметическое кодирование" в других словарях:

  • основанное на контексте адаптивное арифметическое бинарное кодирование — (МСЭ Т Н.264). [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN context based adaptive binary arithmetic codingCABAC …   Справочник технического переводчика

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

  • x264 — Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей …   Википедия

  • X264 — Usage workflow Тип Мультимедийный фреймворк Разработчик x264 team ОС кроссплатформенный …   Википедия

  • CABAC — Запрос «Контекстно адаптивное двоичное арифметическое кодирование» перенаправляется сюда; см. также другие значения. Запрос «КАДАК» перенаправляется сюда; см. также другие значения. Контекстно адаптивное двоичное арифметическое кодирование (КАДАК …   Википедия

  • PAQ — PAQ  серия свободных архиваторов с текстовым интерфейсом, которые общими усилиями разработчиков поднялись в первые места рейтингов многих тестов сжатия данных (хотя и ценой процессорного времени и объёма памяти). Лучший результат в этой… …   Википедия

  • H.264 — Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей. H.264 …   Википедия

  • AVC — H.264, MPEG 4 Part 10 или AVC (Advanced Video Coding)  стандарт сжатия видео, предназначенный для достижения высокой степени сжатия видеопотока при сохранении высокого качества. Содержание 1 О стандарте 2 Возможности 3 Недостатки …   Википедия

  • H.264/MPEG-4 AVC — H.264, MPEG 4 Part 10, или AVC ( Advanced Video Coding ) стандарт сжатия видео, предназначенный для достижения высокой степени сжатия видеопотока при сохранении высокого качества. Он был создан ITU T Video Coding Experts Group (VCEG) совместно с… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»