3.1 LZ77

  • Article

With the  Plain LZ77 variant of the algorithm, the uncompressed ASCII string abcdefghijklmnopqrstuvwxyz is compressed as follows, in hexadecimal.

 3f 00 00 00 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f 70 71 72 73 74 75 76 77 78 79 7a

The first 4 bytes encode the first 32 literal or match flags (in this case, 26 zero bits, representing the 26 literals to follow, then 6 one bits, because any extra flag bits are ones). The next 26 bytes are the ASCII representation of the input string.

The uncompressed input is the 300-byte ASCII string:

 abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc

In this case, using Plain LZ77, those 300 bytes are encoded as follows:

 ff ff ff 1f 61 62 63 17 00 0f ff 26 01

This is the encoding of abc[match: distance = 3, length = 297].