Изменения
Перейти к навигации
Перейти к поиску
Строка 11:
Строка 11: − + + + + + + + + + + + + + + + + + + + + − +
→Пример работы
Теперь возьмём символ из потока и найдём для него отрезок, среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.
Теперь возьмём символ из потока и найдём для него отрезок, среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.
== Пример работы ==
== Пример работы метода арифитического кодирования ==
=== Вероятностная модель ===
Используя метод арифитического кодирования можно достичь почти оптимального представления для заданного набора символов и их вероятностей (согласно [[source coding theorem|теории энтропийного кодирования источника Шенона]] оптимальное представление будет стремится к числу −log''<sub>2</sub>P'' бит на каждый символ, вероятность которого ''P''). Алгоритмы сжатия данных использующие в своей работе метод арифметического кодирования перед непосредственным кодированием формируют [[модель]] входных данных на основании количественных или статистических характеристик, а также, найденных в кодируемой последовательности повторений или паттернов - любой дополнительной информации позволяющей уточнить вероятность появления символа ''P'' в процессе кодирования. Очевидно, что чем точнее определенна или предсказана вероятность символа, тем выше эффективность сжатия.
Рассмотрим простейший случай [[статической]] модели для кодирования информации поступающей с системы обработки сигнала. Типы сигналов и соотвествующие им вероятности распределены следующим образом:
*60% вероятность нейтрального значения сигнала или NEUTRAL
*20% вероятность положительного значения сигнала или POSITIVE
*10% вероятность отрицательного значения сигнала или NEGATIVE
*10% вероятность признака конца кодируемой последовательности или END-OF-DATA.
Появление последнего символа для декодера означает, что вся последовательность была успешно декодированна. ''(В качестве альтернативного подхода, но необязательно более успешно, можно использователь блочный алгоритм фиксированной длины.)''
Следует также отметить, что в качестве алфавита вероятностной модели метода можно рассматривать любой набор символов, исходя из особенностей решаемой задачи. Более эврестические подходы, использующие основную схему метода арифметического кодирования, работают с исползованием ''[[контекстное моделирование| динамических или адаптивных моделей]]''. Идея данных методв заключается в уточнении веротяности кодируемого символа, за счет учета вероятности предшествующего или будующего контекста (т.е. вероятность появления после определенного k- числа символов слева или справа, где k - это порядок контекста).
=== Кодирование сообщения ===
=== Декодирование сообщения ===
[[Image:Arithmetic encoding.svg|400px|thumb|right|На диаграмме представлено декодирование итогового интервального значения 0.538 согласно модели в приведенном примере. Область интервала разбивается на подинтервальные области согласно вероятностным хараткеристикам появления соотвествующих символов. Затем, очередной выбранный интервал разбивается аналогичным способом.]]
[[Image:Arithmetic encoding.svg|400px|thumb|right|На диаграмме представлено декодирование итогового интервального значения 0.538 согласно модели в приведенном примере. Область интервала разбивается на подинтервальные области согласно вероятностным хараткеристикам появления соотвествующих символов. Затем, очередной выбранный интервал разбивается аналогичным способом.]]
Предположим, что нам необходжимо раскодировать сообщение методом арифметического кодирования согласно описанной выше модели. <!-- модель нужно взять из английского текста --> Сообщение в закодированном виде представленно дробным значением 0.538 (для простоты используется дестятичное представление дроби, вместо двоичного основания). Предполагается, что закодированное сообщение содержит ровно столько знаков в рассматриваемом числе, сколько необходимо для однозначного востановления первоначальных данных.
Предположим, что нам необходжимо раскодировать сообщение методом арифметического кодирования согласно описанной выше модели. <!-- модель нужно взять из английского текста --> Сообщение в закодированном виде представленно дробным значением 0.538 (для простоты используется дестятичное представление дроби, вместо двоичного основания). Предполагается, что закодированное сообщение содержит ровно столько знаков в рассматриваемом числе, сколько необходимо для однозначного востановления первоначальных данных.
Начальное состояние процесса декодирования совпадает с процессом кодирования и рассматривается интервал <nowiki>[0,1)</nowiki>. На основании известной вероятностной модели дробным значение 0.538 попадает в интервал <nowiki>[0, 0.6)</nowiki>. Это позволяет определить первый символ, который был выбран кодировщиком, поэтому его значение выводиться как первый символ декодированного сообщения.
Начальное состояние процесса декодирования совпадает с процессом кодирования и рассматривается интервал <nowiki>[0,1)</nowiki>. На основании известной вероятностной модели дробное значение 0.538 попадает в интервал <nowiki>[0, 0.6)</nowiki>. Это позволяет определить первый символ, который был выбран кодировщиком, поэтому его значение выводиться как первый символ декодированного сообщения.
<!-- закоментировано под перевод
<!-- закоментировано под перевод