Каковы реальные применения кодирования Хаффмана? - PullRequest
23 голосов
/ 04 февраля 2010

Мне говорят, что кодирование Хаффмана используется в качестве алгоритма сжатия данных без потерь , но мне также говорят, что реальное программное обеспечение сжатия данных не использует кодирование Хаффмана, потому что если ключи Распределенный недостаточно децентрализованно, сжатый файл может быть даже больше оригинального.

Это заставляет меня задуматься, есть ли какое-нибудь реальное применение кодирования Хаффмана?

Ответы [ 6 ]

29 голосов
/ 04 февраля 2010

Хаффман широко используется во всех основных форматах сжатия, с которыми вы можете столкнуться - от GZIP, PKZIP (winzip и т. Д.) И BZIP2 до форматов изображений, таких как JPEG и PNG.

Все схемы сжатия содержат патологические данные-наборы, которые не могут быть содержательно сжаты;форматы архивов, которые я перечислил выше, просто «хранят» такие файлы в несжатом виде при их обнаружении.

Более новые арифметические и диапазонные кодировки схем часто избегают из-за проблем с патентами ,То есть Хаффман остается рабочей лошадкой в ​​индустрии компрессии.

5 голосов
/ 04 февраля 2010

См. Википедию статью на эту тему:

Сегодня кодирование Хаффмана часто используется в качестве "back-end" для некоторого другого метода сжатия.DEFLATE (алгоритм PKZIP) и мультимедийные кодеки, такие как JPEG и MP3, имеют внешнюю модель и квантование с последующим кодированием Хаффмана.

3 голосов
/ 15 октября 2015

Существует довольно много реальных приложений кодирования Хаффмана. ZIP, пожалуй, наиболее широко используемый инструмент сжатия, использующий кодировку Huffman в качестве основы. Последний из самых эффективных алгоритмов сжатия без потерь, Brotli Compression, выпущенный Google в прошлом месяце, также использует кодирование Хаффмана. Кроме того, Brotli также использует LZ77 и несколько других фундаментальных алгоритмов сжатия без потерь. См. Бротли.

2 голосов
/ 04 февраля 2010

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

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

Если ваш профессор или книга создавали у вас впечатление, что Хаффман не используется, они ошибаются. Например, почти все сообщения в Интернете и из Интернета в какой-то момент кодируются Хаффманом. (Несколько протоколов связи используют его.) Большинство файлов изображений (jpegs) имеют кодировку Хаффмана. Большинство музыкальных файлов (mp3s) кодируются Хаффманом. Есть много других примеров.

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

Чтобы решить, как использовать лучший алгоритм для решения проблемной ситуации, zip-файлы позволяют использовать несколько различных сжатий в зависимости от того, какое из них лучше для данного файла.

0 голосов
/ 02 апреля 2019

Очень распространенным приложением является кодирование строк в HPACK, сжатие заголовков метод http / 2 .

RFC действительно обеспечивает Таблица кодов Хаффмана , оптимизированная для сжатия заголовков HTTP.

0 голосов
/ 30 июля 2015

Код Хаффмана используется для преобразования кодов фиксированной длины в коды переменной длины, что приводит к сжатию без потерь. Коды переменной длины могут быть дополнительно сжаты с использованием методов JPEG и MPEG для получения желаемой степени сжатия.

...