Has the ROLZ algorithm hidden superpowers?

[Crush]

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

[Lucas]

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.

[Cyan]

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.

[Bulat Ziganshin]

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...

[Crush]

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.

[rgeldreich]

+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.