Sugestion compression scheme

[KammutierSpule]

I'm searching for a compression scheme sugestion for the following limitation:

. A small footprint(prog + ram) algorithm;
. very few amount of data to compress <<1Kbyte


For example, for some amount of data that I have at some moment, if it feats in less than 32 byte compressed ... its OK, else, doesnt matter...

so the final data size compressed should be less than 32byte

To be used with random data.

Any sugestion, link that can I read about diferent schemes.

I'm just try find something better than LRE...

Thanks,
KS

[encode]

I think you need something LZ77-based - a la LZSS...
Or maybe some modification of LZW/LZMW.

[Bulat Ziganshin]

>To be used with random data.

[encode]

>To be used with random data.

Different block types as with Deflate - Store/LZ.

[Bulat Ziganshin]

i guess it's just one more absolute archiver

[Shelwien]

Matt already made one (uiq2).
One just has to wait until it generates the requested data.

[osmanturan]

. A small footprint(prog + ram) algorithm;
. very few amount of data to compress <<1Kbyte

Why doesn't anyone take into account that list? It's not a good idea to use LZ or statistical methods (PPM/CM) in such a small data. I think a transformation is needed (BWT like). Of course, someone would say LZ is a transformation in a way. But, it's not suitable in here. Also, what's the amount of "randomness". I think, this is the key question. BTW, I guessed that compressor will be used in an embedded system at a communication system.

[toffer]

Why not use arithmetic coding with a static model (based on a larger amount of training data). Anyway - you need to make your request more preciese, especially more information about the data and maybe some samples.

[chornobyl]

Arithmetical coding is good idea, taking in account small requirements i suggest huffman with smaller alphabet, and maybe some LZ-like literals for random data.

[biject.bwts]

For very small files its hard to beat arb255.exe its a bijective arithmetic 256 symbol coder.

[biject.bwts]

I thought of two more options. I do have a 2 root bijective LZW compressor at my site. As well as code for a bit level binary BWT bijective compressor that would work on strings. But this is one time when BIJECTIVE is best. One question do you want strings of 32 bytes or less. Then would you have to store the byte length separately or would you want the data in 32 byte strings only? And then some where in program you state if the compressed string for the data exists or not? The details make a difference?

[KammutierSpule]

Sorry take long to reply.

I don't have any real examples, I'm just surfing arround subject....

I think, this is the key question. BTW, I guessed that compressor will be used in an embedded system at a communication system.

Yes, thats a subject that it is beeing studied in "Wireless sensor network" area.. http://en.wikipedia.org/wiki/Sensor_network

I found some articles and thesis in web about compression in that particular embedded systems.
I found one using examples of <1K...<3K data... for some testing propouses...

I think that something like this could be subject os studing in this particular systems...
http://en.wikipedia.org/wiki/Burrows-Wheeler_transform
http://en.wikipedia.org/wiki/Golomb_code

I once found some algorithm based in rice code (I have it somewhere.. i need to check it)

The deal with this is that in this systems, transmitting a (bit or..)byte have a great order of magnitude in power consuming related to CPU processing... (and this devices are battery powered)
Not only power but the time (ocuppancy?) transmitting.

So.. transmitting a byte less in a (less than) 32byte message could represent more than days?months? of battery life!

Then would you have to store the byte length separately or would you want the data in 32 byte strings only? And then some where in program you state if the compressed string for the data exists or not?

Yes, could have a fixed byte header, telling the size of message and if compressed or not.. or in what means its compressed...

About systems resources:
There are systems, where a huge (and heavy cost) processor is available (ARMs... >10K ram... etc... ) and others that have very small resources (4K rom, 256bytes ram, .. I've worked with one of these!) ..

Thanks for your sugestions!
KS