Каковы реальные приложения кодирования методом Хаффмана?
Мне говорят, что Кодирование методом Хаффмана используется в качестве loseless алгоритм сжатия данных, но мне также говорят, что реальное программное обеспечение сжатия данных не использует Кодирование методом Хаффмана, потому что, если ключи не распределяются, децентрализовал достаточно, сжатый файл мог бы быть еще больше, чем orignal файл.
Это оставляет меня, удивление является там каким-либо реальным приложением Кодирования методом Хаффмана?
3 ответа
Huffman широко используется во всех основных форматах сжатия, с которыми вы можете столкнуться - от GZIP, PKZIP (winzip и т.д.) и BZIP2, до форматов изображений, таких как JPEG и PNG.
Все схемы сжатия имеют наборы патологических данных, которые не могут быть существенно сжаты; архивные форматы, которые я перечислил выше, просто "хранят" такие файлы в несжатом виде, когда они встречаются.
Более новые схемы арифметики и кодирования диапазона часто избегаются из-за проблем с патентами , что означает, что Хаффман остается рабочей лошадкой индустрии сжатия.
При рассмотрении алгоритмов сжатия часто встречаются преимущества и недостатки каждого из них. Именно природа сжатия заключается в том, что при заданном наборе входных данных, существуют все лучшие и худшие алгоритмы сжатия для этих данных.
Хаффман действительно, действительно хорош в некоторых вещах. Особенно это касается данных, которые многократно повторяют порядок и содержат поднабор символьного пространства. Например, текстовые файлы на английском языке. В английском языке, как правило, используются одни и те же буквы, за которыми следуют те же другие.
Если ваш профессор или книга создали у вас впечатление, что Хаффман не используется, они ошибаются. Например, почти все коммуникации с Интернетом и из Интернета в какой-то момент закодированы Хаффманом. (Его используют несколько коммуникационных протоколов.) Большинство файлов изображений (jpegs) закодированы Huffman. Большинство музыкальных файлов (mp3) закодированы Huffman. Есть много других примеров.
Одна из причин использования Huffman заключается в том, что его можно "обнаружить" с помощью немного другого алгоритма, называемого адаптивным Huffman. Читая файл, вы изучаете код Huffman и "сжимаете по ходу". Это упрощенный обзор, но вы понимаете идею.
Чтобы решить проблему использования наилучшего алгоритма для данной ситуации, zip-файлы позволяют использовать несколько различных компрессий в зависимости от того, какое из них лучше для данного файла.
См. статью в Википедии на эту тему:
Кодирование Хаффмана сегодня часто используется как «базовая часть» для некоторых других методов сжатия. DEFLATE (алгоритм PKZIP) и мультимедийные кодеки, такие как JPEG и MP3, имеют интерфейсную модель и квантование с последующим кодированием Хаффмана.