LZ4 match search algorithm (fast scan)

3
votes

I implemented a LZ77/LZ4 (no entropy encoding) based compression algorithm based on hash chains of infinite depth. It works well and its speed is acceptable, but its compression ratio is close to LZ4. Reading documentation and browsing source code from LZ4 project I understand that it uses a hash chain of depth1, but if I fix my implementation's depthto 1, LZ4 outperforms it.

I can't understand how LZ4 match search algorithm (fast scan) works. Can someone explain it?

Thanks.

1
compressionlossless-compressionlz4

1 Answers

0
votes

The scan process employs hash searching. like the following:

  1. Old Bytes--------------anchor------------New bytes----current
  2. h=hash[int4]
  3. reference=hash.get(h)
  4. hash.put(h,current) for later matching
  5. int(reference)==int(current)? handle matches: retry
  6. handle matches

The seachMatchNb variable is a skip way, for fast matching but maybe loss minute matches or not.

The hash table is a JIT style, which only saves offsets. readIntEquals function does key matching.

Just ignore it in study mode.