Reduced Length LZ (RLLZ): One way to output LZ77 codes

[compgt]

Hi all!

This is my first post, though i have been visiting this site recently every now and then, watching professional and expert programmers exchange lively ideas and suggestions to come up with the most powerful compressors.

Let me share here my one way to output LZ77 codes, which may improve LZ77/LZSS/ or LZW.

LZ77:

LZ77 coding transmits <offset, length> codes. Many times in the compression process, the same matching string is coded with the same <length> code. We can avoid transmitting the <length> code for many strings as well as not outputting a bit to identify a literal (as in LZSS) by the following:

Instead, read the whole input or block (or history buffer) and gather matching strings and encode the <<the whole string>> e.g., <<offset>> plus <<length of the string (n>=2)>> only this one time, <<the number of the same matching strings (ie., number of following offset codes)>>, and its succeeding occurrences in the input block by transmitting only the said <<offset>> codes. This is actually a "Reduced Length LZ (RLLZ)".

The literals are outputted last *without bit flags* since they fall into the block buffers not covered or "not activated" by encoded strings.

During decoding, the strings are written first in the output buffer using the offsets, and the literals "fill in" the unwritten positions in the output buffer.

Thanks,

-- Gerald R. Tamayo

[compgt]

No need to output bit flags for literals or the number of following consecutive literals in some algorithms.

Then the completely filled output buffer is written to file.

That is, e.g. after gathering all distinct repeated strings on a block,

1) no transmission of <length> code for the next occurrences of the same string (but, in the simplest way, you have to output the number of succeeding strings);

2) transmitting the literals last (in the output buffer) means no need to transmit *bit flags* for literals (and matches). This is the novel idea here: deferred literals output;

3) if you know LZT (2008 ) algorithm where it was demonstrated complete exclusion of the length code, this might as well be "LZT2". Should improve LZ77/LZSS/LZW based compressors. Decoding is also straight-forward.

Sorry that only now after a decade of LZT (2008 ) i am releasing this. I stopped coding compression in 2010 or 2011.

My question is: Is this new, or already in some ROLZ implementations?

[Shelwien]

All popular LZ implementations these days seem to use "rep-codes" for match distance.
I think I'd seen also attempts to use rep-codes for match length too, but it didn't show much improvement.
Thus, reusing a whole distance;length pair probably won't be very helpful - well, maybe on logs or some such.

Btw, the further generalization would be secondary LZ compression of LZ tokens.
It was tested before at least in form of bsdiff+lzma, and does show some potential.

[compgt]

Yes, I have similar ideas as "rep-codes" in 2000s. My compression ideas are from the late 90s when i became interested again in data compression.

The ones i call here "holes" they call "gaps" even in LZW. But the idea of deferring transmission of literals for an output buffer avoids bit flags for both literals and matches which is still used in some explanations of ROLZ. Other algorithms still need to output the number of following literals. Deferred, meaning this is not an "online" algorithm.

Yes, i understand LZ recompression for LZ tokens needs well-crafted tokens; this might be a huge algorithm.

Thanks, Shelwien!

[Lucas]

I experimented with this back idea in March 2018 but the problem I encountered was enumerating all subsets of the string since the starting point would end up fixed after a match was found, but optimal parsing requires multiple rotations of the string to be able to find the shortest path.

I never could get my implementation to beat LZ77, it was pretty much on par. I found that the odds of re-using a whole word is as probable as lz77 inserting a new word into the dictionary. By new word I mean a word which is either 1 byte shorter or longer than the next longest matching entry.

I used a 3 symbol flag: literal (no match), lz77 match (insert word), and reuse word via offset code. I guess it'll be worth revisiting but it'll need a global match finder like a suffix array to find the best matches across the whole input unlike the binary tree I was using.

There may be potential with this system for text but it is quite a challenge to get it working well.

[compgt]

...

I never could get my implementation to beat LZ77, it was pretty much on par. I found that the odds of re-using a whole word is as probable as lz77 inserting a new word into the dictionary. By new word I mean a word which is either 1 byte shorter or longer than the next longest matching entry.

I used a 3 symbol flag: literal (no match), lz77 match (insert word), and reuse word via offset code. I guess it'll be worth revisiting but it'll need a global match finder like a suffix array to find the best matches across the whole input unlike the binary tree I was using.

There may be potential with this system for text but it is quite a challenge to get it working well.

I guess, you're thinking about lz77's history buffer as "dictionary"?

> a global match finder like a suffix array to find the best matches

Indeed. Matt Mahoney did something like this in analyzing enwik9 strings...

[Lucas]

Yes I used the LZ history buffer as my dictionary, except I used the most recent 1MB of history to reference words, it was implemented as a 1MB array of uint32_t's to store the length which was referenced in the history, while the rest of the history buffer could grow to 512MB, this was done mainly to constrain decode memory requirements to 1N + 4MB

You've got me wondering if we were both onto something with this encode technique because in theory it can flip between traditional LZ77 and an LZ78 style compressor almost freely, at least I haven't seen it ever compress worse than LZ77, it might just be a matter of determining proper switching between the 2 methods.

[Dresdenboy]

What is the state of implementing this idea?

I had some thoughts and played it through in my mind (knowing my match/literal statistics of compressing binaries, no text though) in different variants (for example: not storing the matched string literal bytes with the offset list, but referencing it from the literals block, avoiding the first explicit copying from the string list to some first position (code bits!) and leaving that to the literal filler instead).

So far I think that saving the literal/match flags isn't enough to offset the needed pointers to either the first occurence or the literal block, even with some kind of delta coding, either going sequentially forward through referenced literals or target positions will cause more randomized referenced on the other side.

But for text compression it might actually work due to more frequent reuse of matched strings. In my files I mostly see single time matches (bytes at same absolute position only copied once for a match). There is surely a way to calculate the benefits based on reuse probabilities for strings.

[compgt]

> What is the state of implementing this idea?

Not implemented yet. I stopped coding in 2010. I just know this makes very compact LZ.

If i recall correctly that James Storer and Jennifer Chayes of Microsoft went to me in my high school (Philippines) in the early 1990s, then it was at that time that i mentioned to Storer the idea of transmitting the literals last, in LZ77. I didn't elaborate though, as i hadn't been programming anymore that time. I didn't have access to an own computer in the 1980s. Mostly theoretical.

I had no achievement in high school except when Hollywood people (and Jennifer Chayes!) went to me in school to sing or maybe re-record the official songs for Bread and America bands, maybe Nirvana too, etc. I didn't get some million$ for my Hollywood music and movies that time, not even thousand$. See, the lead singer in Bread is a "Gates" though it's my voice in the band's modern "official" songs. Others called me "David Gates" or "Bill Gates". To some, i was the real Bill Gates.

[JamesWasil]

> What is the state of implementing this idea?

Not implemented yet. I stopped coding in 2010. I just know this makes very compact LZ.

If i recall correctly that James Storer and Jennifer Chayes of Microsoft went to me in my high school (Philippines) in the early 1990s, then it was at that time that i mentioned to Storer the idea of transmitting the literals last, in LZ77. I didn't elaborate though, as i hadn't been programming anymore that time. I didn't have access to an own computer in the 1980s. Mostly theoretical.

I had no achievement in high school except when Hollywood people (and Jennifer Chayes!) went to me in school to sing or maybe re-record the official songs for Bread and America bands, maybe Nirvana too, etc. I didn't get some million$ for my Hollywood music and movies that time, not even thousand$. See, the lead singer in Bread is a "Gates" but it's my voice in the band's modern "official" songs.

Did you invent KITT for David Hasselhoff to play on Knight Rider as Michael Knight? Or did Wilton Knight come to you to get the design ideas and understand how the molecular bonded shell works?

[Dresdenboy]

> What is the state of implementing this idea?

Not implemented yet. I stopped coding in 2010. I just know this makes very compact LZ.

It looks like LZ77 wants to give RLLZ a try.

Did you invent KITT for David Hasselhoff to play on Knight Rider as Michael Knight? Or did Wilton Knight come to you to get the design ideas and understand how the molecular bonded shell works?

I think we can't help him here.

[danlock]

I wonder if it relates to the new Knight Rider series I heard was coming?