Results 1 to 6 of 6

Thread: Has the ROLZ algorithm hidden superpowers?

  1. #1
    Member
    Join Date
    Sep 2015
    Location
    germany
    Posts
    12
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Cool Has the ROLZ algorithm hidden superpowers?

    After looking a while around all different compression algorithms I thought of taking a closer look at Rolz, because it´s simple, memory friendly, rather fast and can create shorter codes than standard Zip compressors. I thought there´s not much you could improve, because the method is near perfect to result in super short compression code. It seems around 2007-2010 was the time of the last bigger Rolz experiments and range coding has beaten them all so everybody concentrated on special prediction and range coding crunching.

    The disadvantage for this kind of compressors is you need a lot of overhead to get your compression context and so automatically create more literals than other algorithms.
    I wrote a while ago that I found a neat way to prevent signing and length encoding of literals and I also created a test and detection routine for this that works fine, but is a bit slow - I still try to find a way to speed it up a bit.

    So I wanted to test this and some other additions with a working ROLZ compressor and I found this one with the shortest and most simpliest code: http://ezcodesample.com/rolz/rolz_article.html
    The iRolz2 Sourcecode was perfect for my tests. I changed only the main compressor, so decompression is not possible with it. The reason is I only wanted to see what is possible. Adding this and some other ideas for improvements nearly let me fell off my chair after checking it. There are only a few additional lines of code within the compressor and different compression settings and it leads often to better compression than 7zip and sometimes can also get near Nanozip! Don´t forget: Without any changes to the algorithm itself!
    This encourages me now to start my own Rolz implementation suiting to my other ideas for further improvements like dynamic table reoptimizing and additional context compression what is not possible with this.

    You want to see some (test)compression results?
    A10.jpg: 816 kb
    mso97.dll: 1622 kb
    acrord32.exe: 1246 kb
    rafale.bmp: 676 kb
    calgaryfull: 671 kb
    FlashMX.pdf: 3603 kb
    english.dic: 417 kb
    enwik8: 19958 kb
    ohs.doc: 761 kb
    fp: 528 kb
    fp2: 102 kb
    world95: 454kb
    Last edited by Crush; 29th October 2015 at 21:32.

  2. #2
    Member
    Join Date
    Feb 2015
    Location
    United Kingdom
    Posts
    172
    Thanks
    28
    Thanked 73 Times in 43 Posts
    So you've modified irolz2 using some of your own ideas and it supposedly outperforms lzma. I'd like to believe you, if you can get that decompressor working to validate your claims that'd be great.

  3. #3
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    889
    Thanks
    482
    Thanked 279 Times in 119 Posts
    I've always liked ROLZ. It's indeed easy to make something relatively efficient.

    The main issue with it though is the memory needed on both compression and decompression side.
    "Classic" lz77 reduces matches to an offset+length, which can be directly interpreted.
    But for ROLZ, whatever the way you want to organize your offset pointers, it needs to be mimicked on the decoder side.
    It quickly translates into fairly large tables.

    And if there is something I learned these last few years is that it's a poor proposition to embed a compression algorithm within another application if it reserves and use a large chunk of the memory for itself : this will slow down all other tasks the program must also do.

    That being said, for a "compression only" application, such as an archiver, it's a lesser issue.

  4. #4
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,569
    Thanks
    777
    Thanked 687 Times in 372 Posts
    There are only a few additional lines of code within the compressor and different compression settings and it leads often to better compression than 7zip
    i got the same result myrriads of times working on arjz and tornado. and it always meant the same - i made a bug. so make decompressor first, i'm 99% sure that you are wrong

    rolz can beat lzma, as we know, but both implementations that beat lzma are very sophisticated, employing dynamic optimal parsing, and several times slower than lzma both for compression and decompression. it's definitely not the result one can get just by changing a few lines of code. or you are genius, but chances are so small...

  5. #5
    Member
    Join Date
    Sep 2015
    Location
    germany
    Posts
    12
    Thanks
    1
    Thanked 0 Times in 0 Posts
    i got the same result myrriads of times working on arjz and tornado. and it always meant the same - i made a bug. so make decompressor first, i'm 99% sure that you are wrong
    That´s the reason I´ll start my own implementation. I also can´t believe it´s all right, but as you mentioned: Rolz compressors reaching LZMA is possible and I think the same. I´ve seen there´s a lot of other stuff like PPM context mixing from Balz included in iRolz2 source that could show a false behaviour with my changes.

  6. #6
    Member
    Join Date
    Aug 2010
    Location
    Seattle, WA
    Posts
    79
    Thanks
    6
    Thanked 67 Times in 27 Posts
    +1 with that Bulat said. You must implement the decompressor and verify the results. In my experience, 99% of the time you think you've made a breakthrough there's a bug that causes the compressed data to be uncompressible in some way.

    Overall, I agree about ROLZ though. Any alternative to encoding absolute match distances is interesting to me. I have a LZHAM alpha experiment that supports a variant of ROLZ, and it outperforms LZHAM/LZMA on ratio, especially on text. I wasn't happy with the extra costs during decompression, such as the extra RAM needed for the ROLZ tables, and the ROLZ table update cost, that I put the branch on hold.

Similar Threads

  1. ROLZ and Search Trees ?
    By Guzzo in forum Data Compression
    Replies: 5
    Last Post: 1st August 2012, 00:03
  2. xp a rolz compressor
    By pmcontext in forum Data Compression
    Replies: 40
    Last Post: 9th December 2010, 09:04
  3. Researchers warn of malware hidden in .zip files
    By Surfer in forum The Off-Topic Lounge
    Replies: 4
    Last Post: 20th April 2010, 09:19
  4. ROLZ explanation?
    By Trixter in forum Data Compression
    Replies: 5
    Last Post: 10th June 2008, 18:24
  5. Some hidden switches in PackJPG
    By Raymond_NGhM in forum Forum Archive
    Replies: 1
    Last Post: 2nd October 2007, 09:11

Posting Permissions

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