Skip to content
KinPilot™Learn & Explore
Menu

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.

D38 visual explanationAfter the literal ASCII letters ABC, a backward reference copies 6 characters from a distance of 3, one character at a time. The decoded result is ABCABCABC. References can overlap their growing output. This demonstrates decoding, not match search, Huffman coding or byte savings.Describe 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.

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.

After ABC, a distance-3, length-6 reference appends ABCABC. Sequential copying allows the reference to overlap its output.

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
← Grades 9–12 topics