Арифметическое кодирование — различия между версиями
(→Источник) |
Rybak (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
== Характеристики == | == Характеристики == | ||
| − | Обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона. На каждый символ требуется почти < | + | Обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона. На каждый символ требуется почти <tex>H</tex> бит, где <tex>H</tex> — информационная энтропия источника. |
В отличие от [[алгоритм Хаффмана|алгоритма Хаффмана]], метод арифметического кодирования показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов. Однако в случае равновероятного распределения символов, например для строки бит ''010101...0101'' длины ''s'' метод арифметического кодирования приближается к префиксному коду Хаффмана и даже может занимать на один бит больше. | В отличие от [[алгоритм Хаффмана|алгоритма Хаффмана]], метод арифметического кодирования показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов. Однако в случае равновероятного распределения символов, например для строки бит ''010101...0101'' длины ''s'' метод арифметического кодирования приближается к префиксному коду Хаффмана и даже может занимать на один бит больше. | ||
| Строка 17: | Строка 17: | ||
== Источник == | == Источник == | ||
| − | + | [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 Арифметическое кодирование] | |
Версия 06:19, 9 февраля 2011
Один из алгоритмов энтропийного сжатия.
В отличие от алгоритма Хаффмана, не имеет жесткого постоянного соответствия входных символов - группам бит выходного потока. Это дает алгоритму большую гибкость в представлении дробных частот встречаемости символов.
Характеристики
Обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона. На каждый символ требуется почти бит, где — информационная энтропия источника.
В отличие от алгоритма Хаффмана, метод арифметического кодирования показывает высокую эффективность для дробных неравномерных интервалов распределения вероятностей кодируемых символов. Однако в случае равновероятного распределения символов, например для строки бит 010101...0101 длины s метод арифметического кодирования приближается к префиксному коду Хаффмана и даже может занимать на один бит больше.
Принцип действия
Пусть у нас есть некий алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок от 0 до 1.
Назовём этот отрезок рабочим. Расположим на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа и каждый такой отрезок будет соответствовать одному символу.
Теперь возьмём символ из потока и найдём для него отрезок, среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.
