Question about LZ77 decode dependencies and parallelization (learning)

[yasha1971-coder]

Hi,

I’m not very experienced with compression, so sorry if this is a naive question.

I’ve been experimenting with an LZ77-like approach and got a result that I don’t fully understand.

I managed to get:

• bit-perfect decoding
• ~10 GB/s decode on a ~1GB file
• while still using a global compression context

The way I structured it is roughly:

• compression is global (matches can reference earlier data across the whole input)
• but I split the output into blocks
• and precompute offsets so each block knows where its literals / offsets / lengths / commands are

So blocks are not independently compressed, but I try to make them independently decodable.

This seems to allow parallel decode, which is where the speed comes from.

But I feel like I’m probably misunderstanding something fundamental, because I don’t see this pattern used much.

My questions:

• Is there a fundamental reason why LZ77 decode is usually strictly sequential?
• Are there known designs that separate compression context from decode dependency like this?
• What are the main pitfalls of this approach in real implementations?

I’m not claiming this is new — I’m just trying to understand what I might be missing.

Happy to share code or more details if that helps.

Thanks

[wqweto]

Is there a fundamental reason why LZ77 decode is usually strictly sequential?

Yes. In your "independently decodable" blocks how do you "reference earlier data across the whole input" in blocks which are not already decoded? For instance while decoding block 8 you reference data at the end of block 1 but this one is not yet fully decoded.

If you can solve this then your algorithm is gold.

Btw, you can ask ChatGPT this kind of questions to get the gist of the topic.

[yasha1971-coder]

Good catch — yes, this is exactly the important distinction.

In my current design, decode-time back-references do not cross block boundaries.

So if the encoder finds a useful cross-block match, it has to resolve it before writing the final representation — for example by turning part of it into literals near the boundary, or by rewriting it into something block-local.

So the more accurate description is probably:

global analysis / preprocessing -> block-local decodeable form

not true global LZ77 dependency at decode time.

What stays global in my format is mainly the entropy side:
the four streams (literals / offsets / lengths / commands) are compressed as single zstd frames across the whole input, instead of compressing each block separately.

So I think the ratio benefit comes from two things:

1. better entropy context across the whole file
2. the encoder can still analyze cross-block structure before converting it into a block-local form

That is also why decode can run independently per block.

So yes — I agree this is not the same thing as preserving true global LZ77 decode dependencies. "Global analysis, local decode" is probably the more accurate description.

Thanks — this helped me phrase the distinction more clearly.