Results 1 to 6 of 6

Thread: ROLZ and Search Trees ?

  1. #1
    Member
    Join Date
    Aug 2011
    Location
    US
    Posts
    8
    Thanks
    1
    Thanked 0 Times in 0 Posts

    ROLZ and Search Trees ?

    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 .

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

  3. #3
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,497
    Thanks
    733
    Thanked 659 Times in 354 Posts
    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"

  4. #4
    Member
    Join Date
    Aug 2011
    Location
    US
    Posts
    8
    Thanks
    1
    Thanked 0 Times in 0 Posts
    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 ?

  5. #5
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    856
    Thanks
    447
    Thanked 254 Times in 103 Posts
    > 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.

  6. #6
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,497
    Thanks
    733
    Thanked 659 Times in 354 Posts
    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

Similar Threads

  1. Suffix Trees, Suffix Arrays, or What?
    By incblitz in forum Data Compression
    Replies: 47
    Last Post: 12th July 2011, 21:54
  2. xp a rolz compressor
    By pmcontext in forum Data Compression
    Replies: 40
    Last Post: 9th December 2010, 10:04
  3. ROLZ explanation?
    By Trixter in forum Data Compression
    Replies: 5
    Last Post: 10th June 2008, 18:24
  4. RZM - a dull ROLZ compression engine
    By Christian in forum Forum Archive
    Replies: 178
    Last Post: 1st May 2008, 21:26
  5. A small article on ROLZ (Russian)
    By encode in forum Forum Archive
    Replies: 21
    Last Post: 29th April 2007, 15:18

Tags for this Thread

Posting Permissions

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