Арифметическое кодирование: различия между версиями
w>JaroslavleffBot м (Robot: Автозамены v1.20) |
w>Halyavin |
||
| Строка 2: | Строка 2: | ||
== Характеристики == | == Характеристики == | ||
| − | + | Обеспечивает лучшую степень сжатия чем [[алгоритм Хаффмана]]. На каждый символ требуется почти <math>H</math> бит, где <math>H</math> — [[информационная энтропия]] источника. | |
| − | |||
| − | Обеспечивает лучшую степень сжатия чем [[алгоритм Хаффмана]]. | ||
== Принцип действия == | == Принцип действия == | ||
| − | Пусть у нас есть некий алфавит, а | + | Пусть у нас есть некий алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок о 0 до 1. |
Назовём этот отрезок рабочим. Расположем на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа и каждый такой отрезок будет соответсвовать одному символу. | Назовём этот отрезок рабочим. Расположем на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа и каждый такой отрезок будет соответсвовать одному символу. | ||
| − | Теперь возьмём символ из потока и найдём для него отрезок, среди только что сформированных, теперь отрезок для этого сомвола стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для | + | Теперь возьмём символ из потока и найдём для него отрезок, среди только что сформированных, теперь отрезок для этого сомвола стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока. |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Версия от 15:58, 3 января 2006
Характеристики
Обеспечивает лучшую степень сжатия чем алгоритм Хаффмана. На каждый символ требуется почти бит, где — информационная энтропия источника.
Принцип действия
Пусть у нас есть некий алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок о 0 до 1.
Назовём этот отрезок рабочим. Расположем на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа и каждый такой отрезок будет соответсвовать одному символу.
Теперь возьмём символ из потока и найдём для него отрезок, среди только что сформированных, теперь отрезок для этого сомвола стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.