Сжатие/распаковка LZW при низких условиях памяти

Библиотека zlib, которую все используют, раздута, помимо других проблем (для embedded). Я уверен, что она не подойдет для вашего случая. У меня было немного больше памяти, может быть, 16K, и я не мог заставить его поместиться. Он выделяет и обнуляет большие куски памяти, хранит копии и т.д. Алгоритм может это сделать, но найти существующий код - это проблема.

Я выбрал http://lzfx.googlecode.com Цикл распаковки крошечный, это старое сжатие типа lz, которое полагается на предыдущие результаты, поэтому вам нужен доступ к несжатым результатам... Следующий байт - 0x5, следующий байт - 0x23, следующие 15 байт - копия 15 200 байт назад, следующие 6 байт - копия 127 назад... более новый алгоритм lz основан на таблицах переменной ширины, которые могут быть большими или увеличиваться в зависимости от того, как реализованы.

Я имел дело с повторяющимися данными и пытался сжать несколько К в несколько сотен, я думаю, что сжатие составило около 50%, не очень хорошо, но справилось с задачей, а процедура распаковки была крошечной. Пакет lzfx выше небольшой, не такой как zlib, как две основные функции, код которых находится прямо там, а не в десятках файлов. Вы можете изменить глубину буфера, возможно, улучшить алгоритм сжатия, если захотите. Мне пришлось изменить код декомпрессии (возможно, 20 или 30 строк кода), он был перегружен указателями, и я переключил его на массивы, потому что в моей встроенной среде указатели были в неправильном месте. Burns может быть дополнительным регистром или нет, в зависимости от того, как вы его реализуете и от вашего компилятора. Я также сделал это, чтобы абстрагироваться от перебора и хранения байтов, так как они были упакованы в память, не имеющую побайтовой адресации.

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

Моя лучшая рекомендация - изучить исходники BusyBox и посмотреть, достаточно ли мала их реализация LZW для работы в вашей среде.

Прошло более 15 лет с тех пор, как я последний раз играл с алгоритмом сжатия LZW, поэтому Отнеситесь к следующему с недоверием.

Учитывая ограниченность памяти, в лучшем случае это будет сложно. Словарь, который вы создаете, будет использовать подавляющее большинство того, что у вас есть. (Предполагая, что код + память <= 2k.)

Выберите небольшой фиксированный размер для вашего словаря. Скажем, 1024 записи.

Пусть каждая словарная статья имеет форму ....

 struct entry {
    intType   prevIdx;
    charType  newChar;
 };

Эта структура делает словарь рекурсивным. Вам нужно, чтобы элемент с предыдущим индексом был действительным, чтобы он работал правильно. Это работоспособно? Я не уверен. Однако давайте на мгновение предположим, что это так, и выясним, к чему это нас приведет ....

Если вы используете стандартные типы для int и char, у вас быстро закончится нехватка памяти. Вам захочется собрать вещи как можно плотнее. Для хранения 1024 записей потребуется 10 бит. Ваш новый персонаж, скорее всего, займет 8 бит. Всего = 18 бит.

18 бит * 1024 записи = 18432 бита или 2304 байта.

На первый взгляд кажется слишком большим. Что мы делаем? Воспользуйтесь тем фактом, что первые 256 записей уже известны - ваш типичный расширенный набор ascii или что-то еще. Это означает, что нам действительно нужно 768 записей.

768 * 18 бит = 13824 бит или 1728 байт.

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

Надеюсь, это поможет.

Я использовал LZSS . Я использовал код от Харухико Окумура в качестве основы. В качестве словаря используется последняя часть несжатых данных (2К). Связанный мной код можно изменить так, чтобы он почти не использовал память, если у вас есть все несжатые данные, доступные в памяти. Немного погуглив, вы обнаружите, что существует множество различных реализаций.

Если выбор алгоритма сжатия не установлен, вы можете попробовать gzip/LZ77. Вот очень простая реализация, которую я использовал и адаптировал однажды:

ftp://quatramaran.ens.fr/pub/madore/misc/myunzip.c

Вам нужно будет почистить способ чтения ввода, обработку ошибок и т.д., но это хорошее начало. Возможно, он также слишком большой, если ваши данные и код должны поместиться в 2k, но, по крайней мере, размер данных уже небольшой.

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

Может ли кто-нибудь подсказать, как я могу реализовать сжатие/декомпрессию lzw в условиях малого объема памяти (< 2k). возможно ли это?

Почему LZW? LZW требует много памяти. Он основан на хэше/словаре, и степень сжатия пропорциональна размеру хэша/словаря. Больше памяти - лучше сжатие. Меньше памяти - выходной файл может быть даже больше входного.

Я не касался кодирования в течение очень долгого времени, но IIRC кодирование Хаффмана немного лучше, когда дело доходит до потребления памяти.

Но все зависит от типа информации, которую вы хотите сжать.