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