LZ4 search algorithm (fast scan)
I have implemented an LZ77 / LZ4 based compression algorithm (no entropy encoding) based on hash chains of infinite depth. It works well and its speed is acceptable, but its compression ratio is close to LZ4. Reading the documentation and viewing the source code from the LZ4 project I understand that it uses a hash chain with depth 1, but if I fix my implementation depth to 1, LZ4 will surpass it.
I cannot figure out how the LZ4 (quick scan) search algorithm works. Can someone explain this?
Thank.
source to share
The scanning process uses a hash lookup. eg:
- Old bytes -------------- anchor ------------ New bytes ---- current
- h = hash [int4]
- link = hash.get (h)
- hash.put (h, current) for later matching
- Int (link) == int (current)? handle match: retry
- corresponds
The seachMatchNb variable is an overlooked way to quickly match, but maybe wasted minutes or not.
A hash table is a JIT style that only stores offsets. The readIntEquals function searches for keys.
Just ignore it in tutorial mode.
source to share