I post this here because I'd enjoy a discussion and have the errors of my naive ways pointed out to me; I've already promised myself I'll not be sucked into implementing a proof of concept! Who knows, maybe in here there's a nugget that will inspire someone else, and that will be nice.
Imagine a hashtable-only-based history for LZ. Imagine it like this:
You pick some order for the key. In this example, I'll pick order 3.
Think of the stream as being in multiples of this key-size, even though you're sliding through it one char at a time.
So, for example, our compressor is mid-stream:
We look up the previous key in the table,
This will point out to a *list* of historic offsets for the
We also look up where we are now,
We take these two lists and slide along them, looking for a continuation:
In the sliding-along we spot that
Here's an augmentory idea, that might be useful elsewhere. We're doing a *greedy* LZ coder. Look up the prefix -