Results 1 to 12 of 12

Thread: Sugestion compression scheme

  1. #1
    Member
    Join Date
    Jan 2009
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question Sugestion compression scheme

    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

  2. #2
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    I think you need something LZ77-based - a la LZSS...
    Or maybe some modification of LZW/LZMW.

  3. #3
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,497
    Thanks
    733
    Thanked 659 Times in 354 Posts
    >To be used with random data.


  4. #4
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,954
    Thanks
    359
    Thanked 332 Times in 131 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    >To be used with random data.

    Different block types as with Deflate - Store/LZ.

  5. #5
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,497
    Thanks
    733
    Thanked 659 Times in 354 Posts
    i guess it's just one more absolute archiver

  6. #6
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,134
    Thanks
    179
    Thanked 921 Times in 469 Posts
    Matt already made one (uiq2).
    One just has to wait until it generates the requested data.

  7. #7
    Programmer osmanturan's Avatar
    Join Date
    May 2008
    Location
    Mersin, Turkiye
    Posts
    651
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by KammutierSpule View Post
    . 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.
    BIT Archiver homepage: www.osmanturan.com

  8. #8
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  9. #9
    Member chornobyl's Avatar
    Join Date
    May 2008
    Location
    ua/kiev
    Posts
    153
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  10. #10
    Member biject.bwts's Avatar
    Join Date
    Jun 2008
    Location
    texas
    Posts
    449
    Thanks
    23
    Thanked 14 Times in 10 Posts
    For very small files its hard to beat arb255.exe its a bijective arithmetic 256 symbol coder.

  11. #11
    Member biject.bwts's Avatar
    Join Date
    Jun 2008
    Location
    texas
    Posts
    449
    Thanks
    23
    Thanked 14 Times in 10 Posts
    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?

  12. #12
    Member
    Join Date
    Jan 2009
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •