Провееренные алгоритмы компрессии., Что можете посоветовать непрожорливого до памяти? Опции

[Velund]

Периодически вылезает нужда утоптать кое какие данные чтобы во флеше меньше места занимали. И каждый раз на что то натыкаешься - чаще всего на недостаток оперативки...

Вот и сейчас, с 1К оставшегося RAM пытаюсь понять, что бы такое использовать чтобы пожать своеобразный массив данных с блоками переменной длины, состоящий из текстовых строчек (в основном цифры и небольшой субсет латинских букв) в конце добитых нулями до нужной ширины поля.

Может кто нибудь посоветует что то непрожорливое до ресурсов? Есть обкатанная реализация LZW, но там с килобайтом оперативки доить как я понимаю нечего особо.

[apic]

Вот например очень простой - "Unbuffered RLE" не сравнить с LZW , но все же..

[Velund]

Вот например очень простой - "Unbuffered RLE" не сравнить с LZW , но все же..

Это уж как то совсем до примитива доведено. ;-)

[AndrewKirs]

Для LZW места не хватит (под словарь), а RLE в вашем случае будет эффективен только в конце поля, где одни нули. Если увеличить размер памяти никак нельзя, попробуйте какой-нибудь усеченный вариант LZ77 (с маленькой хэш-таблицей) или сжатие по Хаффману.

[Romario]

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

Вот Вы говорите что данные это в основном цифирьки, вот и упакуйте их 2 цифры в 1 байт.
честно говорю недавно была аналогичная проблема упаковывать данные - перепробовал кучу реализаций - ресурсов много жрут а сжимают не очень. В итоге дешево и сердито получилось
использовать банальный rle + разницу между значениями (благо данные у меня такие были)

p.s.
>>в основном цифры и _небольшой_ субсет латинских букв
например можно сделать таблицу перекодировки используемого словаря в непрерывну последовательность,
например, от 0 до 31 - уже можно жать 5 битами. ну и т.д.

Сообщение отредактировал Romario - Jun 22 2006, 15:06

[Velund]

Тут на самом деле ключевое слово "проверенный". ;-) Потому как нагораживая на коленке что то свое и уникальное, надо его тщательно тестить (либо сильно думать над математикой процесса), чтобы не получилось например так, что при определенном сочетании байт во входном потоке оно встает раком или начинает генерить лажу. ;-)

Один раз знакомые в такое вступили, на уже запущенном в серию устройстве. Спасло их только то, что повторялось редко и апдейт был возможен достаточно несложным образом. ;-) Просто выкинули компрессию в апдейте.

[Romario]

Как же без этого свой "доморощенный" алгоритм я доолго тестил на "тест векторах" но все равно
в реальной работе через месяцок он сглючил на реальных данных. Сейчас вроде, тьфу тьфу стабильно все.

Удачи!