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

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

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

Согласно теореме Шеннона о кодировании источника , оптимальная длина кода для символа равна , где - количество символов, используемых для создания выходных кодов, а - вероятность входного символа. ${\ displaystyle -log_ {b} (P)}$${\ displaystyle b}$${\ displaystyle P}$

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

С 2014 года компрессоры данных начали использовать семейство методов энтропийного кодирования Asymmetric Numeral Systems , которое позволяет комбинировать степень сжатия арифметического кодирования со стоимостью обработки, аналогичной кодированию Хаффмана .

Энтропия как мера сходства

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

Смотрите также

• Арифметическое кодирование
• Асимметричные системы счисления (АНС)
• Контекстно-адаптивное двоичное арифметическое кодирование (CABAC)
• Кодирование Хаффмана
• Кодирование диапазона

использованная литература

внешние ссылки

• Теория информации, Умозаключение и алгоритмов обучения , по Дэвид Маккей (2003), дает введение в теорию Шеннона и сжатия данных, включая кодирование Хаффмана и арифметическое кодирование .
• Кодирование источников , Т. Виганд и Х. Шварц (2011).