Is this the same as Lazy-Matching?

[Earl Colby Pottinger]

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?

[GerryB]

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.