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

Question

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

Answer 1

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

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

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

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

Answer 2

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

Выберите небольшой фиксированный размер для своего словаря.Скажем 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 байтов для игры для кода.Естественно, вы можете поиграть с размером словаря и посмотреть, что хорошо для вас, но у вас не останется слишком много места для вашего кода.Поскольку вы смотрите на так мало места для кода, я ожидаю, что вы в конечном итоге будете кодировать в ассемблере.

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

Answer 6

Самый низкий словарь для lzw - trie в связанном списке .См. Оригинальную реализацию в LZW AB .Я переписал его в форк LZWS .Вилка совместима с ncompress.Подробная документация здесь .

n бит словарь требует (2 ** n) * sizeof(code) + ((2 ** n) - 257) * sizeof(code) + (2 ** n) - 257.

Итак:

1. 9 бит код - 1789 байтов.
2. 12 бит код - 19709 байтов.
3. 16 бит code - 326909 bytes.

Обратите внимание, что это требования к словарю.Вам нужно около 100-150 байт для состояния или переменных в стеке.

Декомпрессор будет использовать меньше памяти, чем компрессор.

Поэтому я думаю, что вы можете попытаться сжать ваши данные с помощью 9 bit версия.Но это не обеспечит хорошую степень сжатия.Чем больше битов, тем лучше.

Answer 7

typedef   unsigned int     UINT;
typedef   unsigned char    BYTE;

BYTE *lzw_encode(BYTE *input ,BYTE *output, long filesize, long &totalsize);
BYTE *lzw_decode(BYTE *input ,BYTE *output, long filesize, long &totalsize);

Answer 8

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