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

АЛГОРИТМЫ СЖАТИЯ

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

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

Текст, сжатый арифметическим кодером, рассматривается как некоторая двоичная дробь из интервала [0, 1). Результат сжатия можно представить как последовательность двоичных цифр из записи этой дроби. Каждый символ исходного текста представляется отрезком на числовой оси с длиной, равной вероятности его появления и началом, совпадающим с концом отрезка символа, предшествующего ему в алфавите. Сумма всех отрезков, очевидно должна равняться единице. Если рассматривать на каждом шаге текущий интервал как целое, то каждый вновь поступивший входной символ “вырезает” из него подинтервал пропорционально своей длине и положению.

Построение интервала для сообщения «АБВГ. » :

Поясним работу метода на примере:

Пусть алфавит состоит из двух символов: “a” и “b” с вероятностями соответственно 3/4 и 1/4.

Рассмотрим (открытый справа) интервал [0, 1). Разобьем его на части, длина которых пропорциональна вероятностям символов. В нашем случае это [0, 3/4) и [3/4, 1). Суть алгоритма в следующем: каждому слову во входном алфавите соответствует некоторый подинтервал из [0, 1). Пустому слову соответствует весь интервал [0, 1). После получения каждого очередного символа арифметический кодер уменьшает интервал, выбирая ту его часть, которая соответствует вновь поступившему символу. Кодом сообщения является интервал, выделенный после обработки всех его символов, точнее, число минимальной длины, входящее в этот интервал. Длина полученного интервала пропорциональна вероятности появления кодируемого текста.

Выполним алгоритм для цепочки “aaba”:

Шаг	Просмотренная цепочка	Интервал
0	“”	[0, 1) = [0, 1)
1	“a”	[0, 3/4) = [0, 0.11)
2	“aa”	[0, 9/16) = [0, 0.1001)
3	“aab”	[27/64, 36/64) = [0.011011, 0.100100)
4	“aaba”	[108/256, 135/256) = [0.01101100, 0.10000111)

На первом шаге мы берем первые 3/4 интервала, соответствующие символу «а», затем оставляем от него еще только 3/4. После третьего шага от предыдущего интервала останется его правая четверть в соответствии с положением и вероятностью символа «b». И, наконец, на четвертом шаге мы оставляем лишь первые 3/4 от результата. Это и есть интервал, которому принадлежит исходное сообщение.

В качестве кода можно взять любое число из диапазона, полученного на шаге 4. Возникает вопрос: «А где же здесь сжатие? Исходный текст можно было закодировать четырьмя битами, а мы получили восьмибитный интервал». Дело в том, что в качестве кода мы можем выбрать, например, самый короткий код из интервала, равный 0.1 и получить четырехкратное сокращение объема текста. Для сравнения, код Хаффмана не смог бы сжать подобное сообщение, однако, на практике выигрыш обычно невелик и предпочтение отдается более простому и быстрому алгоритму из предыдущего раздела.

Источник

Лекция 6. Арифметическое кодирование.

Алгоритм кодирования Хаффмена, в лучшем случае, не может пе редавать на каждый символ сообщения менее одного бита информации. Предположим, известно, что в сообщении, состоящем из нулей и единиц, единицы встречаются в 10 раз чаще нулей. При кодировании методом Хаффмена и на 0 и на 1 придется тратить не менее одного бита. Но энтропия д. с.в., генерирующей такие сообщения ≈ 0.469 бит/сим. Не блочный метод Хаффмена дает для минимального среднего количества бит на один символ сообщения значение 1 бит. Хотелось бы иметь та кую схему кодирования, которая позволяла бы кодировать некоторые символы менее чем одним битом. Одной из лучших среди таких схем является арифметическое кодирование, разработанное в 70-х годах XX века.

По исходному распределению вероятностей для выбранной для кодирования д. с. в. строится таблица, состоящая из пересекающихся только в граничных точках отрезков для каждого из значений этой д.с.в.; объединение этих отрезков должно образовывать отрезок [0, 1], а их длины должны быть пропорциональны вероятностям соответству ющих значений д. с. в. Алгоритм кодирования заключается в постро ении отрезка, однозначно определяющего данную последовательность значений д.с.в. Затем для построенного отрезка находится число, при надлежащее его внутренней части и равное целому числу, деленному на минимально возможную положительную целую степень двойки. Это число и будет кодом для рассматриваемой последовательности. Все воз можные конкретные коды — это числа строго большие нуля и строго меньшие одного, поэтому можно отбрасывать лидирующий ноль и де сятичную точку, но нужен еще один специальный код-маркер, сигна лизирующий о конце сообщения.

Отрезки строятся так: если имеется отрезок для сообщения длины n−1, то для построения отрезка для сооб щения длины n, разбиваем его на столько же частей, сколько значений имеет рассматриваемая д.с.в. Это разбиение делается совершенно так- же как и самое первое (с сохранением порядка). Затем выбирается из полученных отрезков тот, который соответствует заданной конкретной последовательности длины n. Принципиальное отличие этого кодирования от рассмотренных ра нее методов в его непрерывности, т.е. в ненужности блокирования. Код здесь строится не для отдельных значений д. с.в. или их групп фикси рованного размера, а для всего предшествующего сообщения в целом. Эффективность арифметического кодирования растет с ростом длины сжимаемого сообщения (для кодирования Хаффмена или Шеннона-Фэно этого не происходит). Хотя арифметическое кодирование дает обычно лучшее сжатие, чем кодирование Хаффмена, оно пока используется на практике сравнительно редко, т.к. оно появилось гораздо позже и тре бует больших вычислительных ресурсов.

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

Пример арифметического кодирования.

Пусть д.с.в. X может при нимать только два значения 0 и 1 с вероятностями 2/3 и 1/3 соответ ственно. Сопоставим значению 0 отрезок [0, 2/3], а 1 — [2/3, 1]. Тогда для д.с.в. X → , dim(X → ) = 3, HX = H X → /3 = log2 3 − 2/3 ≈ 0.9183 бит/сим., таблица построения кодов

ML1(X → ) = 65/81 ≈ 0.8025 бит/сим. (арифметическое),
ML1(X → ) = 76/81 ≈ 0.9383 бит/сим. (блочный Хаффмена),
ML1(X) = ML(X) = 1 бит/сим. (Хаффмена).

Среднее количество бит на единицу сообщения для арифметиче ского кодирования получилось меньше, чем энтропия. Это связано с тем, что в рассмотренной простейшей схеме кодирования, не описан код-маркер конца сообщения, введение которого неминуемо сделает это среднее количество бит большим энтропии.

Получение исходного сообщения из его арифметического кода про исходит по следующему алгоритму:

Шаг 1

В таблице для кодирования значений д.с.в. определяется ин тервал, содержащий текущий код, — по этому интервалу одно значно определяется один символ исходного сообщения. Если этот символ — это маркер конца сообщения, то конец.

Шаг 2

Из текущего кода вычитается нижняя граница содержащего его интервала, полученная разность делится на длину этого же интервала. Полученное число считается новым текущим значением кода. Переход к шагу 1.

Рассмотрим, например, распаковку сообщения 111. Этому сообще нию соответствует число 7/8 ∈ [2/3, 1], что означает, что первый знак декодируемого сообщения — это 1. Далее от 7/8 вычитается 2/3 и ре зультат делится на 1/3, что дает 5/8 ∈ [0, 2/3], что означает, что сле дующий знак — 0. Теперь, вычислив (5/8 − 0) * 3/2 = 15/16 ∈ [2/3, 1], получим следующий знак — 1, т.е. все исходное сообщение 101 деко дировано. Однако, из-за того, что условие остановки не определенно, алгоритм декодирования здесь не остановится и получит “следующий символ” 1 и т.д.

Источник

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

Определение:

Арифметическое кодирование (англ. Arithmetic coding) — алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка [math][0; 1)[/math] . Данный метод, как и алгоритм Хаффмана, является энтропийным, то есть длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов.

Содержание

Принцип действия [ править ]

При арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически, символу [math]a[/math] с вероятностью появления [math]p(a)[/math] допустимо ставить в соответствие код длины [math]-\log_2 p(a)[/math] , следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки).

Кодирование [ править ]

На вход алгоритму передаются текст для кодирования и список частот встречаемости символов.

1. Рассмотрим отрезок [math][0; 1)[/math] на координатной прямой.
2. Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
3. Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов.
4. Повторим пункт [math](3)[/math] до конца входного потока.
5. Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.

Псевдокод [ править ]

• [math]\mathtt\,[/math] — текст, подаваемый на вход;
• [math]\mathtt\,[/math] — длина исходного текста;
• [math]\mathtt\,[/math] — мощность алфавита исходного текста;
• [math]\mathtt\,[/math] — массив символов, составляющих алфавит исходного текста;
• [math]\mathtt\,[/math] — массив вероятностей обнаружения символа в тексте;
• [math]\mathtt\,[/math] — структура, задающая подотрезок отрезка [math][0; 1)[/math] , соответствующего конкретному символу на основе частотного анализа. Имеет поля:
  • [math]\mathtt\,[/math] — левая граница подотрезка;
  • [math]\mathtt\,[/math] — правая граница подотрезка;
• [math]\mathtt\,[/math] , [math]\mathtt\,[/math] — границы отрезка, содержащего возможный результат арифметического кодирования.

Замечание: для оптимизации размера кода можно выбрать из полученного на последнем шаге диапазона [math][left; right][/math] число, содержащее наименьшее количество знаков в двоичной записи.

Декодирование [ править ]

Алгоритм по вещественному числу восстанавливает исходный текст.

1. Выберем на отрезке [math][0; 1)[/math] , разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ.
2. Нормируем подотрезок и вещественное число.
3. Повторим пункты [math]1[/math] — [math]2[/math] до тех пор, пока не получим ответ.

Псевдокод [ править ]

• [math]\mathtt\,[/math] — вещественное число, подаваемое на вход;
• [math]\mathtt\,[/math] — длина восстанавливаемого текста;
• [math]\mathtt\,[/math] — мощность алфавита исходного текста;
• [math]\mathtt\,[/math] — массив символов, составляющих алфавит исходного текста;
• [math]\mathtt\,[/math] — массив вероятностей обнаружения символа в тексте;
• [math]\mathtt\,[/math] — структура, задающая подотрезок отрезка [math][0; 1)[/math] , соответствующего конкретному символу на основе частотного анализа. Имеет поля:
  • [math]\mathtt\,[/math] — левая граница подотрезка;
  • [math]\mathtt\,[/math] — правая граница подотрезка;
  • [math]\mathtt\,[/math] — значение символа.

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

Замечание: Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера — поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, [math]\dfrac<1><3>[/math] ), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число. В такой реализации вероятность встречи символа представляется в виде рационального числа. Поскольку в каждой итерации будет переход из текущего отрезка в один из его [math]m[/math] подотрезков, кратных по длине [math]n[/math] , а всего итераций [math]n[/math] , в конечном результате знаменатель дроби не превысит [math]n^[/math] , а поскольку сумма всех вероятностей встречи символов равна [math]1[/math] , полученная дробь будет находиться в промежутке [math][0; 1)[/math] .

Пример работы [ править ]

Рассмотрим в качестве примера строку [math]abacaba[/math] :

Источник

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

Сейчас существует множество алгоритмов сжатия информации. Большинство из них широко известны, но есть и некоторые весьма эффективные, но, тем не менее, малоизвестные алгоритмы. Эта статья рассказывает о методе арифметического кодирования, который является лучшим из энтропийных, но тем не менее мало кто о нём знает.
Прежде чем рассказывать об арифметическом кодировании, надо сказать пару слов об алгоритме Хаффмана. Этот метод эффективен, когда частоты появления символов пропорциональны 1/2 n (где n – натуральное положительное число). Это утверждение становится очевидным, если вспомнить, что коды Хаффмана для каждого символа всегда состоят из целого числа бит. Рассмотрим ситуацию, когда частота появление символа равна 0,2, тогда оптимальный код для кодирования это символа должен иметь длину –log₂(0,2)=2,3 бита. Понятно, что префиксный код Хаффмана не может иметь такую длину, т.е. в конечном итоге это приводит к ухудшению сжатия данных.
Арифметическое кодирование предназначено для того, чтобы решить эту проблему. Основная идея заключается в том, чтобы присваивать коды не отдельным символам, а их последовательностям.
Вначале рассмотрим идею, лежащую в основе алгоритма, затем рассмотрим небольшой практический пример.
Как и во всех энтропийных алгоритмах мы обладаем информацией о частоте использования каждого символа алфавита. Эта информация является исходной для рассматриваемого метода. Теперь введём понятие рабочего отрезка. Рабочим называется полуинтервал [a;b) с расположенными на нём точками. Причём точки расположены т.о., что длины образованных ими отрезков равны частоте использования символов. При инициализации алгоритма a=0 b=1.
Один шаг кодирования заключается в простой операции: берётся кодируемый символ, для него ищется соответствующий участок на рабочем отрезке. Найденный участок становится новым рабочим отрезком (т.е. его тоже необходимо разбить с помощью точек).
Эта операция выполняется для некоторого количества символов исходного потока. Результатом кодирования цепочки символов является любое число (а также длина его битовой записи) с итогового рабочего отрезка (чаще всего берётся левая граница отрезка).
Звучит это довольно сложно. Давайте попробуем разобраться с помощью небольшого примера. Закодируем сообщение «ЭТОТ_МЕТОД_ЛУЧШЕ_ХАФФМАНА» с помощью описанного метода.

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

Берём первый символ из потока, это символ «Э». Соответствующий ему отрезок – отрезок [0,96;1). Если бы мы хотели закодировать один символ, то результатом кодирования было бы любое число из этого отрезка. Но мы не остановимся на одном символе, а добавим ещё один. Символ «Т». Для этого составим новый рабочий отрезок с a=0,96 и b=1. Разбиваем этот отрезок точками точно так же как мы сделали это для исходного отрезка и считываем новый символ «Т». Символу «Т» соответствует диапазон [0,24;0,36), но наш рабочий отрезок уже сократился до отрезка [0,96;1). Т.е. границы нам необходимо пересчитать. Сделать это можно с помощью двух следующих формул: High=Low_old+(High_old-Low_old)*Range_High(x), Low=Low_old+(High_old-Low_old)*Range_Low(x), где Low_old – нижняя граница интервала, High_old – верхняя граница интервала Range_High и Range_Low – верхняя и нижняя границы кодируемого символа.
Пользуясь этими формулами, закодируем первое слово сообщения целиком:

Результатом кодирования будет любое число из полуинтервала [0,97218816; 0,97223424).
Предположим, что результатом кодирования была выбрана левая граница полуинтервала, т.е. число 0,97218816.
Рассмотрим процесс декодирования. Код лежит в полуинтервале [0,96;1). Т.е. первый символ сообщения «Э». Чтобы декодировать второй символ (который кодировался в полуинтервале [0,96;1)) полуинтервал нужно нормализовать, т.е. привести к виду [0;1). Это делается с помощью следующей формулы: code=(code-Range_Low(x))/(Range_High(x)-Range_Low(x)), где code – текущее значение кода.
Применяя эту формулу, получаем новое значение code=(0,97218816-0,96)/(1-0,96)= 0,304704. Т.е. второй символ последовательности «Т».
Снова применим формулу: code=(0,304704-0,24)/(0,36-0,24)= 0,5392. Третий символ последовательности – «О».
Продолжая декодирование, по описанной схеме мы можем полностью восстановить исходный текст.

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

Источник