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

Схема сжатия данных без потерь

В теории информации энтропийное кодирование (или энтропийное кодирование ) — это любой метод сжатия данных без потерь , который пытается приблизиться к нижней границе, объявленной теоремой исходного кодирования Шеннона , которая гласит, что любой метод сжатия данных без потерь должен иметь ожидаемую длину кода, большую или равную энтропии источника. ^[1]

Точнее, теорема исходного кодирования утверждает, что для любого исходного распределения ожидаемая длина кода удовлетворяет , где – количество символов в кодовом слове, – функция кодирования, – количество символов, используемых для создания выходных кодов, и – вероятность исходного символа. Энтропийное кодирование пытается приблизиться к этой нижней границе. ${\displaystyle \operatorname {E} _{x\sim P}[\ell (d(x))]\geq \operatorname {E} _{x\sim P}[-\log _{b}(P(x))]}$ ${\displaystyle \ell }$ ${\displaystyle d}$ ${\displaystyle b}$ ${\displaystyle P}$

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

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

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

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

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

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

Рекомендации

1. Дуда, Ярек; Тахбуб, Халид; Гаджил, Нирадж Дж.; Дельп, Эдвард Дж. (май 2015 г.). «Использование асимметричных систем счисления как точная замена кодирования Хаффмана». Симпозиум по кодированию изображений (PCS) 2015 . стр. 65–69. дои :10.1109/PCS.2015.7170048. ISBN 978-1-4799-7783-3. S2CID  20260346.
2. Хаффман, Дэвид (1952). «Метод построения кодов с минимальной избыточностью». Труды ИРЭ . Институт инженеров по электротехнике и электронике (IEEE). 40 (9): 1098–1101. дои : 10.1109/jrproc.1952.273898. ISSN  0096-8390.

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

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