Арифметическое кодирование: различия между версиями
w>Solon м (+rewrite) |
|||
| Строка 1: | Строка 1: | ||
{{cleanup-rewrite}} | {{cleanup-rewrite}} | ||
| + | ==Характеристики== | ||
| + | ; Степень сжатия : лучшая > 8, худшая - 1 | ||
| + | |||
| + | Обеспечивает лучшую степень сжатия чем [[алгоритм Хаффмана]]. Т.е. в соответсвии с [[теоремой Шеннона]] - -log<sub>2</sub>(f) бит на цепочку. | ||
| + | |||
| + | ==Принцип действия== | ||
Пусть у нас есть некий алфавит, а так-же данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок о 0 до 1. | Пусть у нас есть некий алфавит, а так-же данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок о 0 до 1. | ||
Версия от 20:10, 30 октября 2005
Характеристики
- Степень сжатия
- лучшая > 8, худшая - 1
Обеспечивает лучшую степень сжатия чем алгоритм Хаффмана. Т.е. в соответсвии с теоремой Шеннона - -log2(f) бит на цепочку.
Принцип действия
Пусть у нас есть некий алфавит, а так-же данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок о 0 до 1.
Назовем этот отрезок рабочим. Расположем на нем точки таким образом, что длины образованных отрезков будут равны частоте использования символа и каждый такой отрезок будет соответсвовать одному символу.
Теперь возьмем символ из потока и найдем для него отрезок, среди только что сформированных, теперь отрезок для этого сомвола стал рабочим. Разобьем его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для следующего символа.
Как только символы закончатся, выберем число из рабочего отрезка - это единственное число, которое требуется, чтобы закодировать последовательность чисел.