LZW сжатие / декомпрессия в условиях низкой памяти
Кто-нибудь может дать указания, как я могу реализовать сжатие / распаковку lzw в условиях низкой памяти (< 2k). это возможно?
8 ответов
Библиотека zlib, которую используют все, раздута среди других проблем (для встраиваемых). Я уверен, что это не сработает для вашего случая. У меня было немного больше памяти, может быть, 16K, и я не мог заставить его соответствовать. Он распределяет и обнуляет большие фрагменты памяти и сохраняет копии содержимого и т. Д. Алгоритм может сделать это, но найти существующий код - непростая задача.
Я пошел с http://lzfx.googlecode.com/ Цикл декомпрессии крошечный, это старое сжатие типа lz, которое опирается на предыдущие результаты, поэтому вам нужно иметь доступ к несжатым результатам... Следующий байт 0x5 следующий байт - 0x23, следующие 15 байтов - копия 15 200 байт назад, следующие 6 байтов - копия 127 назад... более новый алгоритм lz основан на таблице переменной ширины, которая может быть большой или увеличиваться в зависимости от того, как реализовано.
Я имел дело с повторяющимися данными и пытался сжать несколько K до нескольких сотен, я думаю, что сжатие составило около 50%, не очень хорошее, но выполнило свою работу, и процедура распаковки была крошечной. Вышеупомянутый пакет lzfx небольшой, не похожий на zlib, как две основные функции, у которых есть код, а не десятки файлов. Скорее всего, вы можете изменить глубину буфера, возможно, улучшить алгоритм сжатия, если хотите. Мне пришлось изменить код декомпрессии (например, 20 или 30 строк кода), он был тяжелым по указателю, и я переключил его на массивы, потому что в моей встроенной среде указатели были в неправильном месте. Burns может быть дополнительный регистр или нет в зависимости от того, как вы реализуете его и ваш компилятор. Я также сделал это, чтобы можно было абстрагировать выборки и хранилища байтов, так как я упаковал их в память, которая не была адресуемой байтом.
Если вы найдете что-то лучшее, пожалуйста, опубликуйте это здесь или отправьте мне запрос через stackru, я также очень заинтересован в других встроенных решениях. Я искал довольно много, и вышеизложенное было единственным полезным, которое я нашел, и мне повезло, что мои данные были такими, что они сжимались достаточно хорошо, используя этот алгоритм... пока.
Я использовал LZSS. Я использовал код от Харухико Окумура в качестве базы. Он использует последнюю часть несжатых данных (2K) в качестве словаря. Код, который я связал, может быть изменен так, чтобы почти не использовать память, если в памяти есть все несжатые данные. Немного погуглив, вы обнаружите, что множество разных реализаций.
Кто-нибудь может дать указания, как я могу реализовать сжатие / распаковку lzw в условиях низкой памяти (< 2k). это возможно?
Почему LZW? LZW требует много памяти. Он основан на хеше / словаре, а степень сжатия пропорциональна размеру хеша / словаря. Больше памяти - лучше сжатие. Меньше памяти - вывод может быть даже больше, чем ввод.
Я не касался кодирования очень долгое время, но кодирование IIRC Хаффмана немного лучше, когда речь идет о потреблении памяти.
Но все зависит от типа информации, которую вы хотите сжать.
Если выбор алгоритма сжатия не установлен в камне, вы можете вместо этого попробовать gzip/LZ77. Вот очень простая реализация, которую я использовал и адаптировал один раз:
ftp://quatramaran.ens.fr/pub/madore/misc/myunzip.c
Вам нужно будет очистить способ чтения ввода, обработки ошибок и т. Д., Но это хорошее начало. Вероятно, он слишком велик, если ваши данные и код должны умещаться в 2К, но по крайней мере размер данных уже мал.
Большой плюс в том, что это общественное достояние, так что вы можете использовать его так, как вам нравится!
Прошло более 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 байтов для игры для кода. Естественно, вы можете поиграть с размером словаря и посмотреть, что хорошо для вас, но у вас не останется слишком много места для вашего кода. Так как вы смотрите на так мало места для кода, я ожидаю, что вы в конечном итоге будете писать код на ассемблере.
Надеюсь, это поможет.
Самый низкий словарь для lzw это trie в связанном списке. Смотрите оригинальную реализацию в LZW AB. Я переписал это в вилке LZWS. Подробная документация здесь.
n бит словарь требует (2 ** n) * sizeof(code) + ((2 ** n) - 257) * sizeof(code) + (2 ** n) - 257,
Так:
- 9-битный код - 1789 байт.
- 12-битный код - 19709 байт.
- 16-битный код - 326909 байт.
Помните, что это требования к словарю. У вас должно быть около 100-150 байт для состояния или переменных в стеке.
Декомпрессор будет использовать меньше памяти, чем компрессор.
Поэтому я думаю, что вы можете попробовать сжать ваши данные с 9 bit версия. Но это не обеспечит хорошую степень сжатия. Чем больше битов, тем лучше.
Моя лучшая рекомендация - изучить источник BusyBox и посмотреть, достаточно ли малая их реализация LZW для работы в вашей среде.
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);