Используются ли в производстве алгоритмы, подобные кодированию Хаффмана?

Question

В настоящее время я занимаюсь разработкой приложения, которое должно хранить большое количество текста на iPad.Мой вопрос: действительно ли алгоритмы, подобные кодированию Хаффмана, используются в производстве?Мне просто нужен очень простой алгоритм сжатия (не будет большого количества текста, а нужен только более эффективный метод хранения), так будет ли работать что-то вроде Хаффамна?Стоит ли искать какую-нибудь другую библиотеку сжатия?

Answer 1

Из Википедии по теме :

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

Так что да, кодирование Хаффмана используется в производстве.Довольно даже.

Answer 2

Да, они используются в производстве.

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

Вероятно, вскоре после вашего рождения я реализовал сжатие Хаффмана на КПК Psion Series 3 в C, чтобы сжимать данные, которые были предварительно загружены в пакеты данных и распакованы только на КПК. В те дни было мало места и не было встроенной библиотеки сжатия.

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

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

Большие объемы текста поддаются сжатию в стиле zip. И маловероятно, что затраты на улучшение производительности (в пространстве или времени) окупятся в долгосрочной перспективе.

Answer 3

Кодирование Хаффмана (также энтропийное кодирование) используется очень широко.Все, что вы представляете себе сжатым, за исключением некоторых очень старых схем, использует их.Сжатие изображений, архивы Zip и RAR, все мыслимые кодеки и т. Д.

Имейте в виду, что кодирование Хаффмана без потерь и требует, чтобы вы знали все данные, которые вы сжимаете заранее.Если вы выполняете сжатие с потерями, вам необходимо выполнить некоторые преобразования ваших данных, чтобы сначала уменьшить их энтропию (удаление и квантование коэффициентов DCT при сжатии JPEG).Если вы хотите, чтобы кодирование Хаффнама работало с данными в реальном времени (вы не знаете каждый бит заранее), используется адаптивное кодирование Хаффмана.Вы можете найти много информации по этой теме в литературе по обработке сигналов.

Некоторые из методов сжатия до Хаффмана включают такие схемы, как кодирование по длине прогона (факсимильные аппараты).Кодирование по длине прогона все еще иногда используется (опять JPEG) в сочетании с кодированием Хаффмана.

Answer 4

Существует встроенный механизм iOS для поддержки алгоритма zlib (zlib.h в Objective-C).

Вы можете реализовать свои собственные функции сжатия, а использовать встроенные функции iOS zlib . И сравните производительность.

Я думаю, что встроенная функциональность zlib будет быстрее и даст более высокую степень сжатия.

Answer 5

Да, вы используете кодирование (декодирование) Хаффмана для чтения этой страницы, поскольку веб-страницы сжимаются в формат gzip. Так что он используется почти каждую наносекунду веб-браузерами по всей планете.

Кодирование Хаффмана почти никогда не используется само по себе, а всегда с некоторым моделированием данных более высокого порядка, чтобы дать алгоритму Хаффмана то, с чем ему нужно работать. Таким образом, LZ77 моделирует текст и другие байтовые данные как повторяющиеся строки, закодированные как литералы и пары длина / расстояние, которые затем передаются в кодирование Хаффмана, например в сжать сжатый формат , используя zlib . Или с разностным или другим кодированием с предсказанием пикселей для PNG с последующим кодированием Хаффмана.

Что касается того, что вы должны использовать, посмотрите на lz4 , zlib и zstd .

Answer 6

Да, я использую сжатие Хаффмана в своем веб-приложении для хранения полного снимка моего движка в скрытом поле ввода. Во-первых, это было просто любопытство, но оно разгрузило мою память SESSION, перенеся ее в память браузера клиента, и я использовал ее, чтобы сохранить ее в файле для резервного копирования и обмена этим снимком с моим коллегой. Человек, вы должны видеть их лица, когда вы можете просто загрузить файл в панели администратора, чтобы загрузить движок в Интернете! Это в основном сериализованный сжатый и закодированный в base64 массив. Это помогает мне сэкономить около 15% полосы пропускания, но я думаю, что теперь могу сделать это лучше.

Answer 7

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

Что касается того, следует ли вам использовать коды Хаффмана, мой вопрос: зачем вам, когда вы можете добиться лучшего сжатия и простоты кода, используяуже внедрена сторонняя библиотека?