Арифметическое кодирование — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
Один из алгоритмов энтропийного сжатия.
+
== Определение ==
 
+
{{Определение|definition= '''Арифметическое кодирование (Arithmetic coding) ''' {{---}} алгоритм сжатия информации без потерь.
В отличие от [[алгоритм Хаффмана|алгоритма Хаффмана]], не имеет жесткого постоянного соответствия входных символов - группам бит выходного потока. Это дает алгоритму большую гибкость в представлении дробных частот встречаемости символов.
+
}}
 
+
Данный метод (как и алгоритм Хаффмана) является энтропийным т.е. длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. Кроме того, при арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>–log_2(p(a))</tex>, следовательно при кодировании Хаффманом это достигается только с вероятностями, равными обратным степеням двойки).
== Характеристики ==
 
Обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона. На каждый символ требуется почти <tex>H</tex> бит, где <tex>H</tex> — информационная энтропия источника.
 
 
 
В отличие от [[алгоритм Хаффмана|алгоритма Хаффмана]], метод арифметического кодирования показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов. Однако в случае равновероятного распределения символов, например для строки бит ''010101...0101'' длины ''s''  метод арифметического кодирования приближается к префиксному коду Хаффмана и даже может занимать на один бит больше.
 
 
 
== Принцип действия ==
 
Пусть у нас есть некий алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок от 0 до 1.
 
 
 
Назовём этот отрезок рабочим. Расположим на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа и каждый такой отрезок будет соответствовать одному символу.
 
 
 
Теперь возьмём символ из потока и найдём для него отрезок, среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.
 
 
 
 
 
== Источник ==
 
[http://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Арифметическое кодирование]
 

Версия 08:28, 23 декабря 2011

Определение

Определение:
Арифметическое кодирование (Arithmetic coding) — алгоритм сжатия информации без потерь.

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