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

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

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

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

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

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

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

См. также [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

[1] Дуда, Ярек; Тахбуб, Халид; Гаджил, Нирадж Дж.; Дельп, Эдвард Дж. (май 2015 г.). «Использование асимметричных систем счисления как точная замена кодирования Хаффмана» . Симпозиум по кодированию изображений (PCS) 2015 . стр. 65–69. дои : 10.1109/PCS.2015.7170048 . ISBN 978-1-4799-7783-3 . S2CID 20260346 .

[Huffman_1952_pp._1098–1101-2] Хаффман, Дэвид (1952). «Метод построения кодов с минимальной избыточностью». Труды ИРЭ . 40 (9). Институт инженеров по электротехнике и электронике (IEEE): 1098–1101. дои : 10.1109/jrproc.1952.273898 . ISSN 0096-8390 .

[1]

[2]