| Science Forum Index » Compression Forum » ROLZ compression |
|
Page 1 of 2 Goto page 1, 2 Next |
|
| Author |
Message |
| encode |
 Posted: Sun Oct 01, 2006 12:08 pm |
|
|
|
Guest
|
Hi all!
I wrote a simple and fast ROLZ (Reduced Offset Lempel Ziv) like
compressor:
http://www.encode.ru/downloads/tc-5.1dev1.zip (26 KB)
It's something similar to ROLZ codecs by Malcolm Taylor. Brief
description:
Literals encoded with order-1-0 PPM. Offset set reduced with order-2
context (AFAIK, in Malcolm's implementations ROLZ uses order-1
context). TC uses 16 MB dictionary.
Compression is good, at least better than Deflate, plus the algorithm
is asymetric (with fast decompression). But in my opinion compression
power is not too high and must be improved. I won't add the fully
featured PPM literal coder (order-2 or higher), since in this case the
decompression speed will be affected. Note, current decompression speed
is about 16 MB/sec on modern PCs.
Does anyone know details/papers/points on original ROLZ by Malcolm
Taylor? I consider his ROLZ is pretty good (I'm talking about ROLZ2
from mcomp testbed) in both terms - compression ratio and decompression
speed. Also any suggestions/ideas about TC improvements are welcomed! |
|
|
| Back to top |
|
|
|
| michael |
| Posted: Sun Oct 01, 2006 2:37 pm |
|
|
|
Guest
|
encode wrote:
[quote:5ba2d01042]Hi all!
I wrote a simple and fast ROLZ (Reduced Offset Lempel Ziv) like
compressor:
http://www.encode.ru/downloads/tc-5.1dev1.zip (26 KB)
It's something similar to ROLZ codecs by Malcolm Taylor. Brief
description:
Literals encoded with order-1-0 PPM. Offset set reduced with order-2
context (AFAIK, in Malcolm's implementations ROLZ uses order-1
context). TC uses 16 MB dictionary.
Compression is good, at least better than Deflate, plus the algorithm
is asymetric (with fast decompression). But in my opinion compression
power is not too high and must be improved. I won't add the fully
featured PPM literal coder (order-2 or higher), since in this case the
decompression speed will be affected. Note, current decompression speed
is about 16 MB/sec on modern PCs.
Does anyone know details/papers/points on original ROLZ by Malcolm
Taylor? I consider his ROLZ is pretty good (I'm talking about ROLZ2
from mcomp testbed) in both terms - compression ratio and decompression
speed. Also any suggestions/ideas about TC improvements are welcomed!
[/quote:5ba2d01042]
I don't know where you would find papers on ROLZ but I have a few
suggestions for
encoding literals. These are just ideas but they might lead to
stronger encoding
of literals while maintaining speed.
1. Maintain a hash table which is accessed using the current context at
orders higher
than 1 or 2. Each entry in the hash could contain 4 or more literals
previously seen
at that hash value. Use a simple MTF or perhaps even add a primitive
form of weighting
to the symbols in the hashed context.
2. This idea losses streaming capacity but might well be strong. When
a non-match
is encoded do not encode the literal but instead add it to a list of
higher order contexts
and the literal to encode. When enough literals have been found which
are pending
encoding (or the end of the stream is reached) sort the contexts using
a stable sort
and then do a MTF or similar and encode the results. So, say you have
5 literals and maintain order 4 context preceding each ....
literal 1: context = abcc literal = x
literal 2: context = abcd literal = y
literal 3: context = abcc literal = x
literal 4: context = abcc literal = z
literal 5: context = abcc literal = y
stable sort:
abcc(x)
abcc(x)
abcc(z)
abcc(y)
abcd(y)
MTF on xxzyy (or alternative modeling of stream similar to MTF)
then encode that stream.
This idea, looses streaming encoding but should be fast and effective
for encoding
literals. It's sort of like adding a BWT for encoding literals but by
sorting only
the contexts before the literals. And for a limited order so it would
be as fast as a
simple quicksort for modeling.
Actually, quicksort isn't stable, but then it doesn't need to be a
stable sort so long as
the encoder and decoder use the exact same sort to do the sorting.
Just a few ideas ....
- Michael Maniscalco |
|
|
| Back to top |
|
|
|
| encode |
| Posted: Sun Oct 01, 2006 3:32 pm |
|
|
|
Guest
|
Thank you! But I prefer to keep decoder as simple as it possible. So in
next version I replace the encoder's greedy parsing to flexible parsing
- as a result TC will have a higher compression, but the compression
speed will be slightly affected. Note, in this case, decoder stays
untouched.
- Ilia Muraviev |
|
|
| Back to top |
|
|
|
| Matt Mahoney |
| Posted: Sun Oct 01, 2006 10:24 pm |
|
|
|
Guest
|
encode wrote:
[quote:d9c3352c65]Thank you! But I prefer to keep decoder as simple as it possible. So in
next version I replace the encoder's greedy parsing to flexible parsing
- as a result TC will have a higher compression, but the compression
speed will be slightly affected. Note, in this case, decoder stays
untouched.
- Ilia Muraviev
[/quote:d9c3352c65]
Test results on large text benchmark.
http://cs.fit.edu/~mmahoney/compression/text.html#2422
tc 5.1 does not compress as well as 5.0, although it is faster. Keep
in mind I tested 5.1 on a slower computer (2.2 GHz vs. 3 GHz).
-- Matt Mahoney |
|
|
| Back to top |
|
|
|
| encode |
| Posted: Mon Oct 02, 2006 7:33 am |
|
|
|
Guest
|
Okay, and here are the new version with flexible parsing, for
comparison. This version is fully compatible with previous one. (This
is the power side of LZ77 - higher compression without any decoder
modifications)
http://www.encode.ru/downloads/tc-5.1dev2.zip (25 KB) |
|
|
| Back to top |
|
|
|
| Matt Mahoney |
| Posted: Mon Oct 02, 2006 5:44 pm |
|
|
|
Guest
|
|
| Back to top |
|
|
|
| encode |
| Posted: Tue Oct 03, 2006 12:40 pm |
|
|
|
Guest
|
Thank you Matt!
It's sad, but looks like no one knows about ROLZ algorithm. Also I
think Malcolm Taylor will not provide any information about this
algorithm, since this algorithm is used in commercial program and data
compression library - i.e. he's making money from this...
:( |
|
|
| Back to top |
|
|
|
| Malcolm Taylor |
| Posted: Tue Oct 03, 2006 5:20 pm |
|
|
|
Guest
|
Hi Ilia,
Not quite right, I just don't have the time these days for a useful
reply... :(
ROLZ2 and ROLZ3 use optimal parsing, which is where they get a lot of
compression from (similar to the technique used in 7zip).
ROLZ uses an order-1 context for matches, I have tried many times to use
various other contexts, but this turns out to always be the best.
ROLZ2 uses an order-1 (and a bit) fast literal coder. ROLZ3 uses a PAQ
inspired order-2 literal encoder.
Match flags are encoded using a state-machine model.
Overall, ROLZ2 is quite similar to 7zip in algorithm choices, except for
the reduced offset matching.
Hope this helps,
Malcolm
encode wrote:
[quote:d9a2e8eed4]Thank you Matt!
It's sad, but looks like no one knows about ROLZ algorithm. Also I
think Malcolm Taylor will not provide any information about this
algorithm, since this algorithm is used in commercial program and data
compression library - i.e. he's making money from this...
:(
[/quote:d9a2e8eed4] |
|
|
| Back to top |
|
|
|
| encode |
| Posted: Wed Oct 04, 2006 5:38 am |
|
|
|
Guest
|
Thank you very much Malcolm!
I will continue experimenting. To be honest, currently TC uses a lazy
evaluation - like in Deflate
- i.e. this parsing is not optimal. Also, my newest experiments shows
that order-1 context for offset reduction have great potential (but
here we must use more position slots: 512...>1024 instead of 32).
Anyway, here I must continue experimenting. Also I probably must change
the (flags)/literals/match lengths/offsets models, avoiding using of
extended alphabet for literals and match lengths as in Deflate. Also I
will carefully look at LZMA source code. And finally, I can replace
current order-1-0 PPM to order-2 PAQ like encoder...
-- Ilia Muraviev |
|
|
| Back to top |
|
|
|
| Malcolm Taylor |
| Posted: Wed Oct 04, 2006 6:44 am |
|
|
|
Guest
|
Hi again,
With order 1 context, you will find you want at least 1024 offsets. The
earlier ROLZ implementations called this the table size (since the
offsets were stored in a circular table). Without optimal parsing, you
will probably find that a larger table size can sometimes hurt
compression, but this problem dissappears with optimal parsing.
The ROLZ2 and ROLZ3 algorithms both are able to use table sizes of 32000
(older versions were restricted to 32k) and more, in fact if you ask for
a 64MB model size you'll be using a table size of 64000 (IIRC). This
means it can efficiently encode very large files.
Malcolm
encode wrote:
[quote:f6db3d3fd5]Thank you very much Malcolm!
I will continue experimenting. To be honest, currently TC uses a lazy
evaluation - like in Deflate
- i.e. this parsing is not optimal. Also, my newest experiments shows
that order-1 context for offset reduction have great potential (but
here we must use more position slots: 512...>1024 instead of 32).
Anyway, here I must continue experimenting. Also I probably must change
the (flags)/literals/match lengths/offsets models, avoiding using of
extended alphabet for literals and match lengths as in Deflate. Also I
will carefully look at LZMA source code. And finally, I can replace
current order-1-0 PPM to order-2 PAQ like encoder...
-- Ilia Muraviev
[/quote:f6db3d3fd5] |
|
|
| Back to top |
|
|
|
| encode |
| Posted: Wed Oct 04, 2006 7:21 am |
|
|
|
Guest
|
Hi!
Circular table? Is this means:
tab[context][cur_tabsize++ & (TABSIZE - 1)] = cur_pos;
Currently I use a MRU list:
memmove(&tab[context][1], &tab[context][0], ((TABSIZE - 1) *
sizeof(int)));
tab[context][0] = cur_pos;
In my opinion, this list helps with 'offsets' coding. Since recent
offsets are the most frequently used and can be efficiently encoded
with arithmetic coder. - i.e. #0 - the most probably, #(TABSIZE - 1) -
the least probably (longest distance). At least it works with order-2
context.
And how do you code such large number (32k) of offsets? With arithmetic
coder? Or special table? AFAIK, with such large alphabets arithmetic
encoder is unefficient.
Thanks in advance! |
|
|
| Back to top |
|
|
|
| Malcolm Taylor |
| Posted: Wed Oct 04, 2006 5:25 pm |
|
|
|
Guest
|
Hi,
[quote:0a7d22b652]Circular table? Is this means:
tab[context][cur_tabsize++ & (TABSIZE - 1)] = cur_pos;
[/quote:0a7d22b652]
Yep, and you find offset as:
offset = cur_tabsize - match_index;
where tab[context][match_index & (TABSIZE - 1)] is the actual offset
into your history buffer of the best match.
These offsets can be encoded in much the same way as with most lz77,
with an exponential type encoding - encode a bucket number, and then
encode the position in the bucket. Bucket sizes increase for each bucket
number (not necessarily linearly). Check out CAB offset encoding,
deflate and 7zip which all use variations on this.
[quote:0a7d22b652]Currently I use a MRU list:
memmove(&tab[context][1], &tab[context][0], ((TABSIZE - 1) *
sizeof(int)));
tab[context][0] = cur_pos;
[/quote:0a7d22b652]
Comes out the same in the end, but here you do a memmove per match
encoded, which is costly.
Malcolm |
|
|
| Back to top |
|
|
|
| encode |
| Posted: Thu Oct 05, 2006 9:22 am |
|
|
|
Guest
|
Thank you very much Malcolm!
It's time for big experiments!
-- Ilia Muraviev |
|
|
| Back to top |
|
|
|
| encode |
| Posted: Sun Oct 08, 2006 6:40 am |
|
|
|
Guest
|
Okay, here are the new version of TC. It uses a fast PAQ inspired
encoder instead of small PPM. Note, this is a DRAFT version - i.e. the
most of code must be improved/optimized. Also, if you compare this
version against other compressors (LZPXJ, for example) note this TC
have no filters/preprocessors.
http://www.encode.ru/downloads/tc-5.1dev4.zip (25 KB) |
|
|
| Back to top |
|
|
|
| nec556 |
| Posted: Wed Oct 11, 2006 7:23 am |
|
|
|
Guest
|
[quote:148114d8ed]Does anyone know details/papers/points on original ROLZ by Malcolm
Taylor? I consider his ROLZ is pretty good (I'm talking about ROLZ2
from mcomp testbed) in both terms - compression ratio and decompression
speed. Also any suggestions/ideas about TC improvements are welcomed!
[/quote:148114d8ed]
Well you can try to use dLZ77 (it's what i'm playing with now). The
idea is work with literals the same way you do with LZ matches, when
you have a literal longer enough (3-4 bytes) you search in the lz77
buffer not a real macth, but one that maximizes the number of 0's (or
the most similar literal with other metric). Of course, very long
literals make more difficult the searching of a good matches, so you
can define a top limit (i use 32) and divide the literal on several
parts.
Output length/offset as you want (LZ77,LZSS,LZP or anyother) and then
encode differential literals as you wish, but a bit oriented encoder,
as fpaq0, works great. This idea comes from video compresion were a 2D
differential-LZ77is used on motion estimation/compensation.
HTH
P.S. I don't know anyone using or thinking about this on text. Perhaps
i may write a paper about it. |
|
|
| Back to top |
|
|
|
|
