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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Моя лучшая рекомендация – изучить источник 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);