Results 1 to 2 of 2

Thread: History tables for LZ compressors

  1. #1
    Member
    Join Date
    Feb 2010
    Location
    Nordic
    Posts
    200
    Thanks
    41
    Thanked 36 Times in 12 Posts

    History tables for LZ compressors

    I was taking apart BALZ - a very nice ROLZ compressor; the more you imagine experimenting with some change, the more you realise the balance already in it - and its strategy for updating the history tables surprised me.

    It is ROLZ, with digraph prefixes so it has a table of last 127 occurrences of the digraph. That would be just as useful for other variants of LZ, I would assume.

    However, its incomplete history. If it actually encodes a match, the digraphs in the middle of that match do not get put into the history.

    This seems deliberate; it certainly helps compression.

    Is this a mainstream thing? Is there a term for this? Is there any theory to explain why its a good thing, or any obvious rationale?

    thx for helping me learn with your feedback!

    And especially thanks to BALZ for being such clean concise code!

  2. #2
    Member Fu Siyuan's Avatar
    Join Date
    Apr 2009
    Location
    Mountain View, CA, US
    Posts
    176
    Thanks
    10
    Thanked 17 Times in 2 Posts
    However, its incomplete history. If it actually encodes a match, the digraphs in the middle of that match do not get put into the history.
    I don't think it helps, it should be just for speed improvement. Imagine if put every digraphs into history, there should be 127 loops per byte.
    At least in LZ77, it will hurts compression much if you don't put the matched bytes into the search history.
    However, ROLZ is a little context-based like. So maybe this is why ROLZ's ratio hurts less though skipping the bytes in matches.

Similar Threads

  1. Non Windows or Linux compressors
    By Earl Colby Pottinger in forum Data Compression
    Replies: 6
    Last Post: 8th April 2010, 17:26
  2. Delta: binary tables preprocessor
    By Bulat Ziganshin in forum Forum Archive
    Replies: 14
    Last Post: 1st April 2008, 10:43
  3. qc & qazar compressors
    By encode in forum Forum Archive
    Replies: 3
    Last Post: 25th August 2007, 04:58
  4. image compressors
    By maadjordan in forum Forum Archive
    Replies: 5
    Last Post: 13th August 2007, 10:28
  5. Fastest Compressors
    By LovePimple in forum Forum Archive
    Replies: 0
    Last Post: 1st November 2006, 06:36

Posting Permissions

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