Results 1 to 2 of 2

Thread: Is this the same as Lazy-Matching?

  1. #1
    Join Date
    Mar 2010
    Thanked 2 Times in 2 Posts

    Is this the same as Lazy-Matching?

    Working on my own compression software, I developed a simple back-pointer/linear/run-length model. Then I realize I could get rid the RLE mode by a simple lazy match that tested the next byte beyond the present read pointer and if it was the same as the present byte.

    Taking the idea further I wrote a test program for repeating double, triple and quad-byte strings. I found that for my test files that I have a good number of matches.

    However, I am a poor programmer, so I tried to find if there is any info on how others solved this idea in the past. I can not find anything using Google, and what I can find about lazy-matching seems to apply to only one extra byte.

    Am I wrong to call this lazy-matching? Is there another term I should look for on Google?
    Last edited by Earl Colby Pottinger; 23rd December 2010 at 22:20. Reason: grammar

  2. #2
    Join Date
    May 2009
    CA USA
    Thanked 0 Times in 0 Posts
    I don't know what it's called, but this kind of repeat matching is a classic natural feature of a lot of LZ match tools, specifically granddaddy gzip/DEFLATE. The key idea is f you have a match starting N bytes ago and is L bytes long, if N< L, the decoder will naturally start reading its own output and automatically keep copying the same phrase more than once.

    So if you have "abcde" and specify a match of 1 byte previously and length 5, you'd get "abcdeeeeee". If you specify a match of 4 bytes previously and length 11, you'd get abcdebcdebcdebcd.

    So repeat lengths of any period and number of repeats (including a partial repeat of the last copy) are easily and naturally represented, and very efficiently decoded. Since this is a superset of RLE encoding, most LZ77 algorithms (like classic GZIP/DEFLATE) don't need a seperate RLE mode.

Similar Threads

  1. Unaligned bitstring matching experiment
    By Shelwien in forum Data Compression
    Replies: 1
    Last Post: 16th April 2010, 19:59
  2. Advanced Lazy Matching
    By encode in forum Data Compression
    Replies: 15
    Last Post: 8th May 2008, 00:29

Posting Permissions

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