ROLZ and Search Trees ?

[Guzzo]

Hi Everyone,

Usually I am more interested in lz77 but a recent post on irc has caught my attention
I have pasted it below for viewing

<cyrus>Hi and thanks for reply shelwien
i understand how bt is used in lz77 but i cant see how it works with rolz
for each rolz context suppose we use bt, but the offsets stored in the bt are pointing into the window
how would deduce the reduced offset from the tree ?

Seems to be an interesting question and since the forum has experts in this area who could provide a better idea.
After a bit of searching there was a hint on the forum from the author of RZM.

Click here for hint about tree in rzm

I believe Ilya , osman , sebastien are all very interested in these topics. And Ilya's open source rolz compressors are a very good example of how to do ROLZ.
Has anyone tried to use binary trees with ROLZ .

[encode]

Early versions of LZPM was ROLZ-based and use Hash Chains for searching. You just hash order-1 context plus MIN_MATCH and keep track of context count, assigning this count to each new hash entry. And the match index can be found as
CurrentCount[lastChar] - hashEntry.count
Not the best solution probably, but it works!
Malcolm Taylor was saying he uses some sort of trees/linked lists with his ROLZ implementation, but at that time I've not got his idea...

[Bulat Ziganshin]

on compression, you keep incrementing count on each context, and save its current value in th tree element. so, you store "curindex[context]-tree[nnn].index"

[Guzzo]

Interesting so for something like RZM with 64k offsets per context ,does it mean there are 256 huge trees

@Bulat
what is nnn in your example ?
Does each context have a separate tree ?

[Cyan]

> Interesting so for something like RZM with 64k offsets per context ,does it mean there are 256 huge trees

Yes,
although each one of them is probably not that huge.

Take a single 64K table of pointers as an example.

A binary tree requires 2 pointers per element.

But they are not really pointers, rather, they are "index delta" values, always looking backward
(well, for a self-cleaning tree).
So, on 64K, a delta value needs to be 2 bytes only.
2 values per table = 4 bytes.
64K x 4 = 256KB
And since the table stores pointers, which are 4 bytes in 32 bits mode,
then it's only a doubling.

That being said, nonetheless, 256KB x 256 = 64MB.
Moreover, maybe each table could benefit from a small Hash entry to "speed up" search.
Still manageable, but not for small-specs systems.

[Bulat Ziganshin]

tree[src] is a tree element describing source point of LZ match. tree[] is a largest data structure of compression stage

>does it mean there are 256 huge trees

not necessary. it may be optimized for decompression structures, while on compression you may use lzma-like data structures