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

Кодирование энтропии — это схема кодирования которая присваивает коды символам таким образом, чтобы сопоставить длины кодов с вероятностями появления этих символов. Обычно энтропийные кодировщики используют для сжатия данных длины кодов, которые пропорциональны отрицательному логарифму вероятности. Таким образом, наиболее вероятные символы используют кратчайшие коды.

Следуя теореме Шеннона оптимальная длина кода для символа — это -log_bP, где b — это количество символов, использованных для изготовления выходного кода и P — это вероятность входного символа.

Три самых распространённых техники кодирования энтропиии — это кодирование Хаффмана, кодирование расстояний и арифметическое кодирование. Если приблизительные характеристики энтропии потока данных предварительно известны (в особенности для компрессии сигнала), то может быть полезен более простой статический код, такой как унарное кодирование, гамма-кодирование Элиаса, кодирование Фибоначчи, кодирование Голомба или кодирование Райса.

См. также

• Универсальный код

---

Ранняя версия этой статьи была опубликована на PlanetMath (англ.).