4551
правка
Арифметическое кодирование для сжатия данных: различия между версиями
Перейти к навигации
Перейти к поиску
Арифметическое кодирование для сжатия данных (посмотреть исходный код)
Версия от 12:46, 7 августа 2023
, 7 августа 2023→Постановка задачи
Irina (обсуждение | вклад) м (→Наборы данных) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Часто возникает необходимость эффективно закодировать последовательность данных, чтобы минимизировать количество бит, необходимых для передачи или хранения этой последовательности. Последовательность может представлять собой файл или сообщение, состоящее из символов ( | Часто возникает необходимость эффективно закодировать последовательность данных, чтобы минимизировать количество бит, необходимых для передачи или хранения этой последовательности. Последовательность может представлять собой файл или сообщение, состоящее из ''символов'' (также ''букв'' или ''знаков''), взятых из фиксированного входного алфавита. В более общем плане последовательность можно представить как состоящую из ''событий'', каждое из которых берется из своего собственного входного набора. Статистическое сжатие данных заключается в кодировании данных таким образом, чтобы использовать вероятностные оценки событий. Сжатие без потерь характеризуется тем свойством, что входная последовательность может быть точно восстановлена из закодированной последовательности. Арифметическое кодирование представляет собой близкой к оптимальному метод статистического кодирования, позволяющий получить кодировку без потерь. | ||
''' Задача (статистическое сжатие данных)''' | ''' Задача (статистическое сжатие данных)''' | ||
Дано: последовательность из m событий | Дано: последовательность из m событий <math>a_1, a_2, ..., a_m</math>. Каждое событие <math>a_i</math> берется из множества n различных возможных событий <math>e_{i, 1}, e_{i, 2}, ..., e_{i, n}</math>, при этом точно оценивается распределение вероятностей <math>P_i</math> этих событий. Распределения <math>P_i</math> не обязательно должны быть одинаковыми для каждого события <math>a_i</math>. Требуется: найти сокращенное кодирование событий, которое может быть декодировано для восстановления точной исходной последовательности событий. | ||
Цель заключается в достижении оптимальной или близкой к оптимальной длины кодирования. Шеннон [ ] доказал, что наименьшим возможным ожидаемым количеством бит, необходимым для кодирования i-го события, является энтропия | Цель заключается в достижении оптимальной или близкой к оптимальной длины кодирования. Шеннон [ ] доказал, что наименьшим возможным ожидаемым количеством бит, необходимым для кодирования i-го события, является ''энтропия'' <math>P_i</math>, обозначаемая как <math>H(P_i) = \sum_{k = 1}^n -p_{i, k} \; log_2 \; p_{i, k}</math> | ||
где | где <math>p_{i, k}</math> – вероятность того, что в качестве i-го события произойдет <math>e_k</math>. Для кодирования события, вероятность наступления которого равна p, оптимальный код выдает <math>- log_2 \; p</math> бит. | ||
Хорошо известные коды Хаффмана [ ] являются оптимальными только среди префиксных (или мгновенных) кодов, т. е. таких, в которых кодировка одного события может быть декодирована до начала кодирования следующего события. Коды Ху-Таккера представляют собой префиксные коды, аналогичные кодам Хаффмана, и производятся согласно аналогичному алгоритму с дополнительным ограничением на сохранение порядка исходных сообщений в коде. | Хорошо известные коды Хаффмана [6] являются оптимальными только среди ''префиксных'' (или ''мгновенных'') кодов, т. е. таких, в которых кодировка одного события может быть декодирована до начала кодирования следующего события. Коды Ху-Таккера представляют собой префиксные коды, аналогичные кодам Хаффмана, и производятся согласно аналогичному алгоритму с дополнительным ограничением на сохранение порядка исходных сообщений в коде. | ||
В часто встречающихся ситуациях, когда мгновенные коды не нужны, арифметическое кодирование дает ряд преимуществ, в первую очередь за счет ослабления ограничения, согласно которому длина кода должна быть целым числом: (1) длина кода оптимальна (- | В часто встречающихся ситуациях, когда мгновенные коды не нужны, арифметическое кодирование дает ряд преимуществ, в первую очередь за счет ослабления ограничения, согласно которому длина кода должна быть целым числом: (1) длина кода оптимальна (<math>- log_2 \; p</math> бит для события с вероятностью p), даже если вероятности не являются целыми степенями <math>\frac{1}{2}</math>; (2) эффективность кодирования не снижается даже для событий с вероятностью, близкой к 1; (3) можно тривиально работать с распределениями вероятностей, которые меняются от события к событию; (4) соответствия порядка следования входных и выходных сообщений в кодировании Ху-Таккера можно достичь с минимальными дополнительными усилиями. | ||