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

Question

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

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

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

Что будет хорошей распаковкой?

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

Последний работает путем добавления обратных ссылок к повторяющимся частям выходного файла. Это, вероятно, потребует очень мало памяти для запуска, за исключением того, что вам потребуется либо использовать файловый ввод / вывод для чтения обратных ссылок, либо сохранить часть недавно прочитанных данных в ОЗУ.

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

Answer 5

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

http://www.zlib.net/

Answer 6

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