Какой была бы хорошая процедура (де)сжатия для этого сценария?

Question

Мне нужна процедура распаковки FAST, оптимизированная для среды с ограниченными ресурсами, например встроенных систем, в двоичных (шестнадцатеричных данных) и имеющая следующие характеристики:

1. Данные ориентированы на 8 бит (байт) (ширина шины данных 8 бит).
2. Значения байтов НЕ находятся в диапазоне от 0 до 0xFF, но имеют распределение Пуассона (колокольчатую кривую) в каждом наборе данных.
3. Набор данных фиксируется в расширенном режиме (для записи во Flash), и каждый набор редко превышает 1–2 МБ.

Сжатие может занять столько времени, сколько необходимо, но распаковка байта в худшем случае должна занять 23 мкс с минимальным объемом памяти, поскольку это будет выполняться в среде с ограниченными ресурсами, такой как встроенная система (ядро 3–12 МГц, 2 КБ ОЗУ). .

Какой должна быть хорошая процедура декомпрессии?

Базовое кодирование по длине кажется слишком расточительным — я сразу вижу, что добавление заголовка к сжатым данным для использования неиспользуемых байтовых значений для представления часто повторяющихся шаблонов даст феноменальную производительность!

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

Я хотел бы иметь несколько «готовых» примеров, которые можно было бы опробовать на ПК, чтобы я мог сравнить производительность с базовым RLE.

Answer 1

Два решения, которые я использую, когда производительность является единственной проблемой:

• ЛЗО Имеет лицензию GPL.
• liblzf Имеет лицензию BSD.
• miniLZO.tar.gz Это LZO, только что перепакованный в «минимизированную» версию, которая лучше подходит для разработки встраиваемых систем.

Оба очень сильно быстро при распаковке.Я нашел это LZO создаст сжатые данные немного меньшего размера, чем liblzf в большинстве случаев.Вам нужно будет провести собственные тесты скорости, но я считаю, что они «по сути равны».Оба на световые годы быстрее, чем zlib, хотя ни один из них не сжимается так же хорошо (как и следовало ожидать).

LZO, в частности miniLZO, и liblzf оба отлично подходят для встроенных целей.

Answer 2

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

В зависимости от данных я бы попробовал Huffman с фиксированными кодами или lz77 (см. ссылки Брайана).

Answer 3

Ну, основные два алгоритма, которые приходят на ум: Хаффман и ЛЗ.

Первый в основном просто создает словарь.Если вы достаточно ограничите размер словаря, он должен работать довольно быстро... но не ждите очень хорошего сжатия.

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

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

Answer 4

Поскольку это похоже на звук, я бы посмотрел либо на дифференциальный PCM, либо на ADPCM, либо на что-то подобное, что уменьшит его до 4 бит на выборку без особой потери качества.

В самой базовой реализации дифференциальной PCM вы просто сохраняете 4-битную разницу со знаком между текущей выборкой и аккумулятором, добавляете эту разницу в аккумулятор и переходите к следующей выборке.Если разница выходит за пределы [-8,7], вам придется зафиксировать значение, и аккумулятору может потребоваться несколько выборок, чтобы его догнать.Декодирование происходит очень быстро, практически не используя память: просто добавляется каждое значение в аккумулятор и выводится аккумулятор в качестве следующей выборки.

Небольшое улучшение по сравнению с базовым DPCM, помогающее аккумулятору быстрее наверстывать упущенное, когда сигнал становится громче и выше, заключается в использовании справочной таблицы для декодирования 4-битных значений в больший нелинейный диапазон, где они все еще находятся на расстоянии 1 около нуля. , но увеличиваются с большими приращениями по направлению к пределам.И/или вы можете зарезервировать одно из значений для переключения множителя.Решение о том, когда его использовать, принимается кодировщиком.Благодаря этим улучшениям вы можете либо добиться лучшего качества, либо обойтись 3 битами на выборку вместо 4.

Если ваше устройство имеет нелинейный АЦП с мю-характеристикой или АЦП с А-характеристикой, вы можете получить качество, сравнимое с 11-12 битами, с 8-битными выборками.Или вы, вероятно, можете сделать это самостоятельно в своем декодере. http://en.wikipedia.org/wiki/M-law_algorithm

Могут быть недорогие чипы, которые уже делают все это за вас, в зависимости от того, что вы делаете.Я ничего не рассматривал.

Answer 5

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

Answer 6

Я использовал zlib во встроенных системах в качестве загрузчика, который при запуске распаковывает образ приложения в оперативную память.Лицензия вполне разрешительная, никакой чепухи GPL.Он выполняет один вызов malloc, но в моем случае я просто заменил его заглушкой, возвращающей указатель на статический блок, и соответствующей заглушкой free().Я сделал это, отслеживая использование выделенной памяти, чтобы правильно определить размер.Если ваша система поддерживает динамическое распределение памяти, то все гораздо проще.

http://www.zlib.net/