В настоящее время я разрабатываю приложение, которое должно хранить большой объем текста на iPad. Мой вопрос: действительно ли алгоритмы, подобные кодированию Хаффмана, используются в производстве? Мне просто нужен очень простой алгоритм сжатия (не будет большого количества текста, и ему нужен только более эффективный метод хранения), поэтому будет ли работать что-то вроде Хаффамна? Должен ли я искать какую-то другую библиотеку сжатия?
Используются ли в производстве такие алгоритмы, как кодирование Хаффмана?
Ответы (7)
Из Википедии по этому вопросу:
Кодирование Хаффмана сегодня часто используется как «внутренняя часть» некоторых других методов сжатия. DEFLATE (алгоритм PKZIP) и мультимедийные кодеки, такие как JPEG и MP3, имеют интерфейсную модель и квантование, за которым следует кодирование Хаффмана (или коды без префиксов переменной длины с аналогичной структурой, хотя, возможно, не обязательно разработанные с использованием алгоритма Хаффмана).
Так что да, кодирование Хаффмана используется в производстве. Даже очень много.
Кодирование Хаффмана (также энтропийное кодирование) используется очень широко. Все, что вы себе представляете, что сжимается, за исключением некоторых очень старых схем, использует их. Сжатие изображений, архивы Zip и RAR, всевозможные кодеки и так далее.
Имейте в виду, что кодирование Хаффмана выполняется без потерь и требует, чтобы вы заранее знали все данные, которые вы сжимаете. Если вы выполняете сжатие с потерями, вам необходимо выполнить некоторые преобразования ваших данных, чтобы сначала уменьшить их энтропию (удаление и квантование коэффициентов DCT при сжатии JPEG). Если вы хотите, чтобы кодирование Хаффнама работало с данными в реальном времени (вы не знаете каждый бит заранее), используется адаптивное кодирование Хаффмана. Вы можете найти много информации по этой теме в литературе по обработке сигналов.
Некоторые из методов сжатия до Хаффмана включают такие схемы, как кодирование длин серий (факсовые аппараты). Кодирование длин серий все еще иногда используется (снова JPEG) в сочетании с кодированием Хаффмана.
Да, они используются в производстве.
Как уже упоминалось, настоящий Хаффман требует, чтобы вы сначала проанализировали весь корпус, чтобы получить наиболее эффективное кодирование, поэтому оно обычно не используется само по себе.
Вероятно, вскоре после того, как вы родились, я применил сжатие Хаффмана на портативном компьютере Psion Series 3 на C, чтобы сжать данные, которые были предварительно загружены в пакеты данных и распаковывались только на портативном компьютере. В те дни места было мало, и не было встроенной библиотеки сжатия.
Как и в большинстве программ, которые хорошо определены, я настоятельно рекомендую использовать любую функцию, встроенную в iOS или стандартные пакеты, доступные в вашей среде разработки.
Это сэкономит много времени на отладку и позволит вам сосредоточиться на наиболее важных частях вашего приложения, которые приносят пользу.
Большие объемы текста поддаются сжатию в стиле zip. И маловероятно, что затраты на улучшение его производительности (либо в пространстве, либо во времени) окупятся в долгосрочной перспективе.
В iOS есть встроенный механизм для поддержки алгоритма zlib (zlib.h в Objective-C).
Вы можете реализовать свои собственные функции сжатия и использовать встроенные в iOS функции zlib. И сравните производительность.
Я думаю, что встроенная функциональность zlib будет быстрее и даст более высокую степень сжатия.
Коды Хаффмана являются основой многих производственных алгоритмов «реального мира». Современные алгоритмы сжатия улучшают коды Хаффмана, преобразуя их данные для улучшения степени сжатия. Конечно, для этого используется множество специальных методов.
Что касается того, следует ли вам использовать коды Хаффмана, мой вопрос: зачем вам это, если вы можете добиться лучшего сжатия и простоты кода, используя уже реализованную стороннюю библиотеку?
Да, я использую сжатие Хаффмана в своем веб-приложении для хранения полного снимка моего двигателя в скрытом поле ввода. Во-первых, это было просто любопытство, но оно разгружало мою память SESSION, перемещая ее в память клиентского браузера, и я использовал ее для сохранения в файле для резервного копирования и обмена этим снимком с моим коллегой. Чувак, ты должен видеть их лица, когда ты можешь просто загрузить файл в админке, чтобы загрузить движок в вебе!!! Это в основном сериализованный сжатый и закодированный в base64 массив. Это помогает мне сэкономить около 15% полосы пропускания, но я думаю, что теперь я могу сделать это лучше.
Да, вы используете кодирование (декодирование) Хаффмана для чтения этой страницы, поскольку веб-страницы сжаты в формат gzip. Таким образом, веб-браузеры по всей планете используют его практически каждую наносекунду.
Кодирование Хаффмана почти никогда не используется само по себе, а скорее всегда с некоторым моделированием данных более высокого порядка, чтобы дать алгоритму Хаффмана то, с чем ему нужно работать. Таким образом, LZ77 моделирует текст и другие байт-ориентированные данные как повторяющиеся строки, закодированные как литералы и пары длины/расстояния, которые затем передаются для кодирования Хаффмана, например. в формате deflate с использованием zlib. Или с разностным или другим прогнозирующим кодированием пикселей для PNG с последующим кодированием Хаффмана.
Что касается того, что вы должны использовать, посмотрите lz4, zlib и zstd.