Concept of the day1 / 3
LZ77
The conceptHow zipping a long text file shrinks it to a fraction of its size
Text repeats itself: words, phrases and spacing come back again and again. LZ77 compresses by replacing each repeat with a short pointer to where the same bytes appeared before.
The pointer is a pair (distance, length): go back this many characters and copy this many. Take 'abcabcabc': the compressor writes 'abc' as plain letters, then one pointer (3, 6) instead of the remaining six letters.
The decoder needs no separate dictionary. Its dictionary is simply the text it has already rebuilt, so it copies from its own output.
What it’s forRebuilds the original text from one back-reference while decompressing.
out[p + k] = out[p − d + k], for k = 0 … L − 1
- p
- the position in the output where the copy starts
- d
- distance: how far back the earlier copy begins
- L
- length: how many characters to copy
- k
- which character of the copy is being written, counting from 0
What it givesThe repeated characters, written again at the current position.
- Output so far 'abc', so p = 3. Pointer: d = 3, L = 6.
- k = 0, 1, 2 copy out[0..2] → 'abc'; k = 3, 4, 5 copy out[3..5], just written → 'abc'.
- Result: 'abcabcabc', nine letters from three letters and one pointer.