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

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

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

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

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

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

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

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

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

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

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

^ «Образование - Энтропийное кодирование» . www.pcs-ip.eu . Проверено 13 октября 2020 .
^ «Что такое энтропийное кодирование | IGI Global» . www.igi-global.com . Проверено 13 октября 2020 .
^ Хаффман, Дэвид (1952). «Метод построения кодов с минимальной избыточностью». Труды ИРЭ . Институт инженеров по электротехнике и радиоэлектронике (IEEE). 40 (9): 1098–1101. DOI : 10,1109 / jrproc.1952.273898 . ISSN 0096-8390 .

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

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

[1] «Образование - Энтропийное кодирование» . www.pcs-ip.eu . Проверено 13 октября 2020 .

[2] «Что такое энтропийное кодирование | IGI Global» . www.igi-global.com . Проверено 13 октября 2020 .

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

[1]