Grades 9–12 · Computing
How can a file describe a repeated phrase without writing it again?
Repeated text contains opportunities to reuse information. LZ77-style compression can send literal data for a first occurrence, then describe a later repeat using a backward distance and a length. The decoder uses output it already has; the reference does not point to an unknown future passage.
In the diagramDescribe a repeat with a backward referenceAlready decoded: A B CGo back 3 charactersCopy 6 characters, one at a timeNewly appendedABCABCResult: ABCABCABCThe source can grow as copying proceeds.Conceptual LZ77 copy; not a compressed-file size estimate.
Suppose ABC has already been decoded. “Go back 3 characters and copy 6” appends ABCABC, giving ABCABCABC. Copying happens one character at a time. After the first three copied characters, the source for the next three lies in the newly extended output. Such overlap is allowed; the source is not frozen before the copy starts.
Distance and length have different jobs. From ABC, distance 2 and length 6 append BCBCBC. Distance 1 and length 3 append CCC. The instructions are exact, so the reconstruction loses no characters. In these ASCII examples, each shown character is one byte.
DEFLATE, used by formats such as gzip, combines this kind of reuse with Huffman coding. Real files also carry structure and coding overhead. A short reference is useful only when its encoded cost beats an alternative representation. The diagram demonstrates reconstruction, not a promise that every file becomes smaller.
About this explanation
Starting knowledge: Understands ordered character strings and step-by-step algorithms.
Sources
- RFC Editor / L. Peter Deutsch — RFC 1951 — DEFLATE Compressed Data Format Specification