Что было бы хорошей (де) процедурой сжатия для этого сценария?
Мне нужна процедура распаковки FAST, оптимизированная для среды с ограниченными ресурсами, такой как встроенные системы в двоичной системе (шестнадцатеричные данные), которая имеет следующие характеристики:
- Данные ориентированы на 8 бит (байт) (шина данных имеет ширину 8 бит).
- Значения байтов НЕ находятся в диапазоне от 0 до 0xFF, но имеют распределение Пуассона (кривая колокола) в каждом наборе данных.
- Набор данных фиксируется в расширенном (для записи во Flash), и каждый набор редко> 1 - 2 МБ
Сжатие может занять столько времени, сколько требуется, но декомпрессия байта должна занять 23 мкс в худшем случае с минимальным использованием памяти, поскольку это будет происходить в среде с ограниченными ресурсами, такой как встроенная система (ядро 3 МГц - 12 МГц, 2 КБ ОЗУ),
Что будет хорошей распаковкой?
Базовое кодирование длин серий кажется слишком расточительным - я сразу вижу, что добавление раздела заголовка к сжатым данным, чтобы использовать неиспользуемые значения байтов для представления часто повторяющихся шаблонов, дало бы феноменальную производительность!
Со мной, который потратил всего несколько минут, наверняка уже должны существовать гораздо лучшие алгоритмы от людей, которые любят этот материал?
Я хотел бы иметь несколько готовых примеров для тестирования на ПК, чтобы я мог сравнить производительность с базовым RLE.
6 ответов
Два решения, которые я использую, когда производительность - единственная проблема:
- LZO имеет лицензию GPL.
- liblzf имеет лицензию BSD.
- miniLZO.tar.gz Это
LZO, просто перепакованный в "минимизированную" версию, которая лучше подходит для встроенной разработки.
Оба очень быстро при распаковке. Я нашел это LZO создаст несколько меньшие сжатые данные, чем liblzf в большинстве случаев. Вам нужно будет сделать свои собственные тесты скорости, но я считаю, что они "по существу равны". Оба световых года быстрее, чем zlibхотя ни то, ни другое не сжимает (как и следовало ожидать).
LZO, особенно miniLZO, а также liblzf оба отлично подходят для встроенных целей.
Если у вас есть заранее установленное распределение значений, что означает, что пригодность каждого значения фиксирована во всех наборах данных, вы можете создать кодировку Хаффмана с фиксированными кодами (дерево кодов не должно быть встроено в данные).
В зависимости от данных, я бы попробовал Хаффмана с фиксированными кодами или lz77 (см. Ссылки Брайана).
Ну, два основных алгоритма, которые приходят на ум, - это Хаффман и LZ.
Первый в основном просто создает словарь. Если вы достаточно ограничите размер словаря, он должен быть довольно быстрым... но не ожидайте очень хорошего сжатия.
Последний работает путем добавления обратных ссылок на повторяющиеся части выходного файла. Это, вероятно, потребует очень мало памяти для запуска, за исключением того, что вам потребуется либо использовать файловый ввод / вывод для чтения обратных ссылок, либо сохранить часть недавно прочитанных данных в ОЗУ.
Я подозреваю, что LZ - ваш лучший вариант, если повторяющиеся разделы имеют тенденцию быть близко друг к другу. Хаффман работает, имея словарь часто повторяющихся элементов, как вы упомянули.
Поскольку это похоже на звук, я бы посмотрел либо на дифференциальную PCM, либо на ADPCM, либо на что-то подобное, что уменьшит его до 4 бит / сэмпл без особых потерь в качестве.
В самой базовой реализации дифференциальной PCM вы просто сохраняете 4-битную разность со знаком между текущей выборкой и аккумулятором, добавляете эту разницу к аккумулятору и переходите к следующей выборке. Если разница находится за пределами [-8,7], вам необходимо зафиксировать значение, и аккумулятор может отобрать несколько выборок. Декодирование выполняется очень быстро, практически без памяти, просто добавляя каждое значение в аккумулятор и выводя аккумулятор в качестве следующего образца.
Небольшое улучшение по сравнению с базовым DPCM, чтобы помочь аккумулятору быстрее догонять, когда сигнал становится громче и выше, - использование таблицы поиска для декодирования 4-битных значений в больший нелинейный диапазон, где они все еще находятся на расстоянии 1 от нуля, но увеличиваются с большими приращениями к пределам. И / или вы можете зарезервировать одно из значений для переключения множителя. Решать, когда использовать его до энкодера. С этими улучшениями вы можете либо достичь лучшего качества, либо получить 3 бита на выборку вместо 4.
Если ваше устройство имеет нелинейный АЦП с µ-законом или А-законом, вы можете получить качество, сравнимое с 11-12-битным с 8-битными выборками. Или вы можете сделать это самостоятельно в своем декодере. http://en.wikipedia.org/wiki/M-law_algorithm
Там могут быть недорогие чипы, которые уже делают все это для вас, в зависимости от того, что вы делаете. Я не смотрел ни на что.
Вам следует попробовать разные алгоритмы сжатия либо с помощью программного инструмента сжатия с переключателями командной строки, либо с помощью библиотеки сжатия, где вы можете попробовать разные алгоритмы. Используйте типичные данные для вашего приложения. Тогда вы знаете, какой алгоритм лучше всего подходит для ваших нужд.
Я использовал zlib во встроенных системах для загрузчика, который при запуске распаковывает образ приложения в ОЗУ. Лицензия хороша, без всякой ерунды под GPL. Он делает один вызов malloc, но в моем случае я просто заменил его заглушкой, возвращающей указатель на статический блок, и соответствующей заглушкой free(). Я сделал это, отслеживая использование памяти, чтобы получить правильный размер. Если ваша система может поддерживать динамическое выделение памяти, то это намного проще.