Interested Article - Энтропийное кодирование

Энтропийное кодирование — кодирование последовательности значений с возможностью однозначного восстановления с целью уменьшения объёма данных (длины последовательности) с помощью усреднения вероятностей появления элементов в закодированной последовательности.

Предполагается, что до кодирования отдельные элементы последовательности имеют различную вероятность появления. После кодирования в результирующей последовательности вероятности появления отдельных символов практически одинаковы ( энтропия на символ максимальна).

Различают несколько вариантов кодов:

Сопоставление каждому элементу исходной последовательности различного числа элементов результирующей последовательности. Чем больше вероятность появления исходного элемента, тем короче соответствующая результирующая последовательность. Примером могут служить код Шеннона — Фано , код Хаффмана ,
Сопоставление нескольким элементам исходной последовательности фиксированного числа элементов конечной последовательности. Примером является .
Другие структурные коды, основанные на операциях с последовательностью символов. Примером является кодирование длин серий .
Если приблизительные характеристики энтропии потока данных предварительно известны, может быть полезен более простой статический код, такой как унарное кодирование , гамма-код Элиаса , код Фибоначчи , код Голомба или кодирование Райса .

Согласно теореме Шеннона , существует предел сжатия без потерь, зависящий от энтропии источника. Чем более предсказуемы получаемые данные, тем лучше их можно сжать. Случайная независимая равновероятная последовательность сжатию без потерь не поддаётся.