Мне говорят, что кодирование Хаффмана используется как алгоритм сжатия без потерь, но мне также говорят, что программное обеспечение для сжатия данных не использует кодирование Хаффмана, потому что если ключи не распределены достаточно децентрализованно, сжатый файл может быть еще больше чем файл orignal.
Это оставляет мне интересно, есть ли какое-либо приложение для кодирования Хаффмана в реальном мире?
Huffman широко используется во всех основных форматах сжатия, которые могут возникнуть - от GZIP, PKZIP (winzip и т.д.) и BZIP2 до форматов изображений, таких как JPEG и PNG.
Все схемы сжатия имеют набор патологических данных, которые не могут быть существенно сжаты; в архивных форматах, перечисленных выше, просто "хранить" такие файлы несжатые, когда они встречаются.
Более новые арифметические и диапазонные кодировки часто избегают из-за патентных вопросов, то есть Хаффман остается рабочей лошадкой в индустрии сжатия.
Смотрите статью в Википедии на эту тему:
Сегодня кодирование Хаффмана часто используется в качестве "бэк-энда" для какого-либо другого метода сжатия. DEFLATE (алгоритм PKZIP) и мультимедийные кодеки, такие как JPEG и MP3, имеют внешнюю модель и квантование с последующим кодированием Хаффмана.
Существует довольно много реальных приложений Huffman Encoding. ZIP - это, пожалуй, самый широко используемый инструмент сжатия, который использует Huffman Encoding в качестве основы. Последний из наиболее эффективных алгоритмов сжатия без потерь, Brotli Compression, выпущенный Google в прошлом месяце, также использует кодировку Хаффмана. Кроме того, Бротли также использует LZ77 и несколько других алгоритмов сжатия без потерь. См. Brotli.
Когда рассматриваются алгоритмы сжатия, для каждой из них часто есть преимущества и недостатки. Это характер сжатия, который задает набор входных данных, для этих данных существуют лучшие и худшие алгоритмы сжатия.
Хаффман действительно, действительно хорош в некоторых вещах. Особенно заметно данные, которые многократно повторяют порядок и содержат подмножество пространства символов. Например, текстовые файлы на английском языке. Английский язык имеет те же буквы, что и другие буквы.
Если ваш профессор или книга дали вам впечатление, что Хаффман не используется, они ошибаются. Например, почти все коммуникации с и из Интернета в какой-то момент закодированы Хаффманом. (Для этого используется несколько протоколов связи.) Большинство файлов изображений (jpegs) закодированы в кодировке Хаффмана. Большинство музыкальных файлов (mp3) кодируются Хаффманом. Есть много других примеров.
Одна из причин, по которой Хаффман используется, заключается в том, что ее можно "открыть" с помощью немного другого алгоритма, называемого адаптивным Хаффманом. Когда вы читаете файл, вы узнаете код Хаффмана и "сжимаете, когда идете". Это упрощенный обзор, но вы получаете идею.
Чтобы решить проблему с использованием наилучшего алгоритма для проблемы ситуации, zip файлы позволяют использовать несколько различных сжатий в зависимости от того, какой лучший для данного файла.
Код Хаффмана используется для преобразования кодов фиксированной длины в коды с переменной длиной, что приводит к сжатию без потерь. Коды переменной длины могут быть дополнительно сжаты с использованием методов JPEG и MPEG для получения желаемой степени сжатия.
Очень распространенное приложение - это кодирование строк в HPACK, метод сжатия заголовков http/2.
RFC напрямую предоставляет таблицу кодов Хаффмана, оптимизированную для сжатия заголовков HTTP.