Арифметическое кодирование для сжатия данных: различия между версиями

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

Дано: последовательность из 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-го события, является ''энтропия'' <math>P_i</math>, обозначаемая как <math>H(P_i) = \sum_{k = 1}^n -p_{i, k} \; log_2 \; p_{i, k}</math>