Кодировка арифметическим методом — это кодирование при помощи алгоритма, позволяющего без потерь сжимать информацию, который ставит в соответствие текстовому сообщению вещественное число на отрезке от нуля до единицы.
Введение
Под арифметическим кодированием понимается алгоритм, относящийся к классу алгоритмов сжатия с применением энтропии. Этот алгоритм отличается от алгоритма Хаффмана тем, что в нём отсутствует жёсткое постоянное соответствие входных символов наборам бит выходных потоков. То есть алгоритм арифметического кодирования является более гибким в отображении дробных частот повторяемости символов.Кроме того, он обладает лучшими характеристиками в сравнении с алгоритмом Хаффмана по эффективности сжатия, так как даёт возможность сжатия данных с энтропией менее одного бита на каждый кодируемый знак.
Кодировка арифметическим методом
Кодирование арифметическим методом даёт практически оптимальный уровень сжатия с позиций энтропийной оценки кодировки Шеннона. Для кодирования любого символа необходимо почти Н бит, где Н является информационной энтропией источника. Основным отличием кодирования арифметическим методом от алгоритма Хаффмана является тот факт, что арифметическое кодирование обеспечивает высокий уровень эффективности для дробных неравномерных интервалов распределения вероятностей символов, подлежащих кодированию. Но для варианта распределения символов с равной степенью вероятности, к примеру, для такой строки в двоичном формате 010101…0101, имеющей длину S, методика арифметического кодирования близка к префиксным кодам Хаффмана, а может даже и уступать ему.
Принцип кодирования при помощи арифметического метода заключается в следующем. Предположим есть некоторый алфавит, а также информация о частоте применения некоторых символов. Возьмём на координатной прямой некоторый рабочий отрезок от нуля до единицы. Необходимо расположить на этом отрезке точки в таком порядке, чтобы длины сформированных точками отрезков равнялись частоте применения символа, а каждый данный отрезок соответствует одному символу. Далее следует выбрать из потока символ и найти для него отрезок в наборе сформированных отрезков. Этот отрезок для выбранного символа считается рабочим. Его нужно также разбить на отрезки от нуля до единицы. Следует исполнить данную процедуру для определённого количества очерёдности символов.Далее нужно выбрать какое-нибудь число из рабочего отрезка. Биты данного числа совместно с длиной его двоичного отображения и будут результатом арифметической кодировки выбранных поточных символов.
Применение метода арифметической кодировки позволяет достичь практически оптимального отображения для выбранного символьного набора и их вероятностей. В соответствии с теорией энтропийной кодировки источника Шеннона, оптимальное отображение стремится к значению $−log_2P$ для каждого символа, имеющего вероятность Р.
Алгоритм сжатия информации, применяющий в процессе работы методику арифметической кодировки, перед началом собственно кодирования должен сформировать модель входных информационных данных на базе количественных или статистических параметров, и, кроме того, выявленных в кодируемой символьной очерёдности повторов или паттернов, то есть какой-либо добавочной информации, которая позволяет осуществить уточнение вероятности возникновения символа Р при выполнении кодировки. Естественно, чем более точно определяется или предсказывается вероятность символа, тем будет более высокой эффективность сжатия.
Рассмотрим пример простейшего варианта статической модели при кодировке информации, которая поступает из системы, обрабатывающей сигнал. Виды сигналов и вероятности, которые им соответствуют, распределяются в следующем порядке:
- Вероятность нейтральной величины сигнала, то есть NEUTRAL, равна 60%.
- Вероятность положительной величины сигнала, то есть POSITIVE, равна 20%.
- Вероятность отрицательной величины сигнала, то есть NEGATIVE, равна 10%.
- Вероятность наличия признака окончания последовательности, подлежащей кодированию, то есть END-OF-DATA, равна 10%.
Поступление последнего символа для модуля декодирования является сигналом, что весь символьный набор был успешно декодирован. Как альтернативный может быть использован блочный алгоритм фиксированного размера, но нет гарантии что он окажется более эффективным.
Необходимо заметить, что алфавитом вероятностной модели арифметического метода может быть практически любой символьный набор, соответствующий особенностям решаемой проблемы. Подходы с более эвристическим характером, применяющие главную структуру методики арифметической кодировки, используют динамические или адаптивные модели. Суть этих методов состоит в более точном определении вероятности символа, подлежащего кодировке, путём учёта вероятности уже прошедшего или же будущего набора символов (содержания). Это означает вероятность возникновения символа, подлежащего кодированию, вслед за определённым К-тым числом символов слева или же справа. Здесь К является порядком содержания.
Рассмотрим конкретный пример кодирования арифметическим методом. Имеем следующую символьную последовательность:
NEUTRAL NEGATIVE END-OF-DATA.
Вначале следует разбить отрезок от нуля до единицы в соответствии с частотой сигналов. Разбиение отрезка, как указывалось выше, следует выполнить следующим образом:
- NEUTRAL отводится участок от нуля до 0,6.
- POSITIVE отводится отрезок от 0,6 до 0,8.
- NEGATIVE отводится отрезок от 0,8 до 0,9.
- END-OF-DATAотводится отрезок от 0,8 до единицы.
Процесс кодирования начинается с первого символа NEUTRAL, которому соответствует отрезок от 0 до 0,6. Выполним аналогично разбиение этого отрезка от 0 до 1. Далее кодируется второй символ, то есть NEGATIVE. На отрезке от нуля до 0,6 ему отводится участок от 0,48 до 0,54. Этот отрезок разбивается аналогично отрезку от нуля до единицы. Затем кодируется третий символ, то есть END-OF-DATA. На отрезке от 0,48 до 0,54 ему отводится участок от 0,534 до 0,54.
Прошедшее кодировку сообщение является отрезком от 0,534 до 0,54 или же любое число из этого отрезка, к примеру, 0,538.
