Арифметическое кодирование: различия между версиями
w>Ewger (→Принцип действия: перевод примера из материала на англ.) |
w>Ewger |
||
| Строка 10: | Строка 10: | ||
Теперь возьмём символ из потока и найдём для него отрезок, среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока. | Теперь возьмём символ из потока и найдём для него отрезок, среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока. | ||
| + | |||
| + | == Пример работы == | ||
| + | [[Image:Arithmetic encoding.svg|400px|thumb|right|На диаграмме представлено декодирование итогового интервального значения 0.538 согласно модели в приведенном примере. Область интервала разбивается на подинтервальные области согласно вероятностным хараткеристикам появления соотвествующих символов. Затем, очередной выбранный интервал разбивается аналогичным способом.]] | ||
| + | |||
| + | Предположим, что нам необходжимо раскодировать сообщение методом арифметического кодирования согласно описанной выше модели. <!-- модель нужно взять из английского текста --> Сообщение в закодированном виде представленно дробным значением 0.538 (для простоты используется дестятичное представление дроби, вместо двоичного основания). Предполагается, что закодированное сообщение содержит ровно столько знаков в рассматриваемом числе, сколько необходимо для однозначного востановления первоначальных данных. | ||
| + | |||
| + | Начальное состояние процесса декодирования совпадает с процессом кодирования и рассматривается интервал <nowiki>[0,1)</nowiki>. На основании известной вероятностной модели дробным значение 0.538 попадает в интервал <nowiki>[0, 0.6)</nowiki>. Это позволяет определить первый символ, который был выбран кодировщиком, поэтому его значение выводиться как первый символ декодированного сообщения. | ||
<!-- закоментировано под перевод | <!-- закоментировано под перевод | ||
| − | |||
| − | |||
| − | |||
We start, as the encoder did, with the interval <nowiki>[0,1)</nowiki>, and using the same model, we divide it into the same four sub-intervals that the encoder must have. Our fraction 0.538 falls into the sub-interval for NEUTRAL, <nowiki>[0, 0.6)</nowiki>; this indicates to us that the first symbol the encoder read must have been NEUTRAL, so we can write that down as the first symbol of our message. | We start, as the encoder did, with the interval <nowiki>[0,1)</nowiki>, and using the same model, we divide it into the same four sub-intervals that the encoder must have. Our fraction 0.538 falls into the sub-interval for NEUTRAL, <nowiki>[0, 0.6)</nowiki>; this indicates to us that the first symbol the encoder read must have been NEUTRAL, so we can write that down as the first symbol of our message. | ||
Версия от 23:14, 21 сентября 2007
Характеристики
Обеспечивает лучшую степень сжатия чем алгоритм Хаффмана. На каждый символ требуется почти бит, где — информационная энтропия источника.
Принцип действия
Пусть у нас есть некий алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок о 0 до 1.
Назовём этот отрезок рабочим. Расположим на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа и каждый такой отрезок будет соответствовать одному символу.
Теперь возьмём символ из потока и найдём для него отрезок, среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.
Пример работы
Предположим, что нам необходжимо раскодировать сообщение методом арифметического кодирования согласно описанной выше модели. Сообщение в закодированном виде представленно дробным значением 0.538 (для простоты используется дестятичное представление дроби, вместо двоичного основания). Предполагается, что закодированное сообщение содержит ровно столько знаков в рассматриваемом числе, сколько необходимо для однозначного востановления первоначальных данных.
Начальное состояние процесса декодирования совпадает с процессом кодирования и рассматривается интервал [0,1). На основании известной вероятностной модели дробным значение 0.538 попадает в интервал [0, 0.6). Это позволяет определить первый символ, который был выбран кодировщиком, поэтому его значение выводиться как первый символ декодированного сообщения.
Ошибка Lua в Модуль:Navbox на строке 353: attempt to index local 'listText' (a nil value).
de:Arithmetisches Kodieren en:Arithmetic coding ja:算術符号 ko:산술 부호화 nl:Aritmetische codering pl:Kodowanie arytmetyczne pt:Codificação aritmética zh:算术编码