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

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

В теории информации энтропийное кодирование (или энтропийное кодирование ) — это любой метод сжатия данных без потерь , который пытается приблизиться к нижней границе, объявленной теоремой Шеннона о кодировании источника , которая гласит, что любой метод сжатия данных без потерь должен иметь ожидаемую длину кода, большую или равную энтропии источника. ^[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 года компрессоры данных начали использовать семейство методов энтропийного кодирования на основе асимметричных систем счисления , что позволяет сочетать коэффициент сжатия арифметического кодирования со стоимостью обработки, аналогичной кодированию Хаффмана .

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

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

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

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

Ссылки

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

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

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