Изменения

=== Вероятностная модель ===

=== Вероятностная модель ===

Используя метод арифметического кодирования можно достичь почти оптимального представления для заданного набора символов и их вероятностей (согласно [[source coding theorem|теории энтропийного кодирования источника Шеннона]] оптимальное представление будет стремится к числу −log''₂P''  бит на каждый символ, вероятность которого ''P''). Алгоритмы сжатия данных использующие в своей работе метод арифметического кодирования перед непосредственным кодированием формируют [[модель]] входных данных на основании количественных  или статистических характеристик, а также, найденных в кодируемой последовательности повторений или паттернов - любой дополнительной информации позволяющей уточнить вероятность появления символа ''P'' в процессе кодирования. Очевидно, что чем точнее определена или предсказана вероятность символа, тем выше эффективность сжатия.  

Используя метод арифметического кодирования можно достичь почти оптимального представления для заданного набора символов и их вероятностей (согласно [[source coding theorem|теории энтропийного кодирования источника Шеннона]] оптимальное представление будет стремится к числу −log''₂P''  бит на каждый символ, вероятность которого ''P''). Алгоритмы сжатия данных использующие в своей работе метод арифметического кодирования перед непосредственным кодированием формируют [[модель]] входных данных на основании количественных  или статистических характеристик, а также, найденных в кодируемой последовательности повторений или паттернов - любой дополнительной информации позволяющей уточнить вероятность появления символа ''P'' в процессе кодирования. Очевидно, что чем точнее определена или предсказана вероятность символа, тем выше эффективность сжатия.  

Рассмотрим простейший случай [[статической]] модели для кодирования информации поступающей с системы обработки сигнала. Типы сигналов и соответствующие им вероятности распределены следующим образом:

Рассмотрим простейший случай [[статической]] модели для кодирования информации поступающей с системы обработки сигнала. Типы сигналов и соответствующие им вероятности распределены следующим образом:

Появление последнего символа для декодера означает, что вся последовательность была успешно декодирована. ''(В качестве альтернативного подхода, но необязательно более успешно, можно использовать блочный алгоритм фиксированной длины.)''

Появление последнего символа для декодера означает, что вся последовательность была успешно декодирована. ''(В качестве альтернативного подхода, но необязательно более успешно, можно использовать блочный алгоритм фиксированной длины.)''

Следует также отметить, что в качестве алфавита вероятностной модели метода можно рассматривать любой  набор символов, исходя из особенностей решаемой задачи. Более [[эвристика|эвристические]] подходы, использующие основную схему метода арифметического кодирования, применяют ''[[контекстное моделирование| динамические или адаптивные модели]]''. Идея данных методов заключается в уточнении вероятности кодируемого символа, за счет учёта вероятности предшествующего или будущего контекста (т.е. вероятность появления кодируемого символа после определённого k-го числа символов слева или справа, где k - это порядок контекста).

Следует также отметить, что в качестве алфавита вероятностной модели метода можно рассматривать любой  набор символов, исходя из особенностей решаемой задачи. Более [[эвристика|эвристические]] подходы, использующие основную схему метода арифметического кодирования, применяют '' [[контекстное моделирование|динамические или адаптивные модели]]''. Идея данных методов заключается в уточнении вероятности кодируемого символа, за счет учёта вероятности предшествующего или будущего контекста (т.е. вероятность появления кодируемого символа после определённого k-го числа символов слева или справа, где k - это порядок контекста).

=== Кодирование сообщения. ===

=== Кодирование сообщения. ===

=== Декодирование сообщения ===

=== Декодирование сообщения ===

[[Изображение:Arithmetic encoding.svg|400px|thumb|right|На диаграмме представлено декодирование итогового интервального значения 0.538 согласно модели в приведённом примере. Область интервала разбивается на подинтервальные области согласно вероятностным характеристикам появления соответствующих символов. Затем, очередной выбранный интервал разбивается аналогичным способом.]]

[[Файл:Arithmetic encoding.svg|400px|thumb|right|На диаграмме представлено декодирование итогового интервального значения 0.538 согласно модели в приведённом примере. Область интервала разбивается на подинтервальные области согласно вероятностным характеристикам появления соответствующих символов. Затем, очередной выбранный интервал разбивается аналогичным способом.]]

Предположим, что нам необходимо раскодировать сообщение методом арифметического кодирования  согласно описанной выше модели. <!-- модель нужно взять из английского текста --> Сообщение в закодированном виде представлено дробным значением 0.538 (для простоты используется десятичное представление дроби, вместо двоичного основания). Предполагается, что закодированное сообщение содержит ровно столько знаков в рассматриваемом числе, сколько необходимо для однозначного восстановления первоначальных данных.

Предположим, что нам необходимо раскодировать сообщение методом арифметического кодирования  согласно описанной выше модели. <!-- модель нужно взять из английского текста --> Сообщение в закодированном виде представлено дробным значением 0.538 (для простоты используется десятичное представление дроби, вместо двоичного основания). Предполагается, что закодированное сообщение содержит ровно столько знаков в рассматриваемом числе, сколько необходимо для однозначного восстановления первоначальных данных.

[[Категория:Алгоритмы сжатия без потерь]]

[[Категория:Алгоритмы сжатия без потерь]]

[[de:Arithmetisches Kodieren]]

[[de:Arithmetisches Kodieren]]

[[en:Arithmetic coding]]

[[en:Arithmetic coding]]