|
|
| Строка 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], следовательно при кодировании Хаффманом это достигается только с вероятностями, равными обратным степеням двойки).
