A support dump repeats GET /health 200 OK and a newline eight times. 152 bytes. The intern already ran Huffman Coding on the raw bytes — the alphabet is small, codes are short — and still sends on the order of one token per character. Product says gzip is Huffman. The file they wanted is a copy of a phrase they already wrote, then a prefix code on those tokens.
LZ77 replaces a repeated phrase with a (distance, length) back-reference into a sliding window of bytes already emitted; DEFLATE then Huffman-codes those tokens. Frequent substrings collapse. Frequent symbols get short codes afterward. Concatenating Huffman onto the raw dump never finds GET /health.
This post is that pairing. Families and the catalog live on the Algorithms Roadmap. Huffman is already live: it is the entropy stage after the window — not gzip by itself. Sliding Window grew a range on an array for an aggregate; this window is history for copies. Call java.util.zip. Do not hand-roll gzip.
The job is a copy, not a shorter alphabet
Huffman assumes independent symbols and a known frequency table. A log line that repeats is not independent symbols. The second retry: timeout is the first one, some bytes ago.
LZ77 keeps a sliding window of bytes already emitted — the history. At the cursor it searches that window for the longest match of the bytes still to write. Two outcomes:
- No useful match — emit a literal (the next unmatched byte).
- A match — emit a (distance, length) pair: go back
distancebytes in the history, copylengthbytes.
The decoder has already produced that history, so the pair is enough. It does not need the phrase again. The encoder and decoder agree on the window bound (DEFLATE’s common bound is 32 KiB). Bytes that slide out of the window can no longer be cited.
The compressor is the window. Huffman is a code for the tokens the window emitted. Literals, lengths, and distances are the alphabet the tree sees. The raw bytes are not.
Note: DEFLATE-style matchers usually ignore matches shorter than 3 bytes: a (distance, length) token can cost more than the literals. Max match length is 258. Those numbers are the format, not a different algorithm.
A walk: one phrase, then a back-reference
Take a 30-byte line with the same timeout twice. Require length ≥ 3, greedy longest match, no lazy lookahead.
input (30 bytes):
retry: timeout; retry: timeout
0 1 2 3
012345678901234567890123456789
cursor 0, window empty
no match of length ≥ 3
emit 16 literals: "retry: timeout; "
window = those 16 bytes
cursor 16, upcoming = "retry: timeout"
longest match in the window: distance 16, length 14
emit (dist=16, len=14)
tokens:
16 literals + 1 back-reference
not 30 independent symbolsThe second phrase is one pointer. Huffman on the raw 30 bytes would still name about 30 symbols. Huffman on this token stream names sixteen literals and one copy.
Matches may overlap the cursor. aaaa at index 1 can be (dist=1, len=3): the copy reads bytes it just wrote. That is legal LZ77. The walk above does not need it.
Note: Production DEFLATE often lazy-matches: it may skip a match at i if i + 1 starts a longer one. The procedure is still “search the window.” The extra rule is a length heuristic, not a second compressor.
DEFLATE is Huffman after the window
DEFLATE is the pairing used by zip, gzip, and PNG’s usual compressed path:
- LZ77 turns the byte stream into tokens: literals and (length, distance) pairs (plus an end-of-block marker on the wire).
- Huffman (typically canonical, often two trees: literals/lengths, and distances) encodes those tokens.
The prefix code is the second stage. The window is the first. Huffman Coding is that builder: merge lightest nodes, read 0/1 down the paths. Run it on the tokens. Running it on the raw dump is a different, weaker job.
gzip wraps DEFLATE with a header, CRC, and size. zlib wraps DEFLATE with a different header. The algorithm in the middle is the same pairing. PNG’s DEFLATE block layout — BTYPE, stored vs compressed, bit packing — is out of scope here. So is arithmetic coding.
Do not ship a Huffman tree and call the file gzip. Do not treat the Huffman lab as a zip implementation. This page is the window the Huffman post pointed at.
Java: a matcher sketch, then the JDK
A lab matcher is a nested scan: for each cursor, try every window origin, count the shared prefix. It is not a bitstream.
/** Longest match of s[i..] in the last `window` bytes. Length ≥ 3, else none. */
static int[] match(byte[] s, int i, int window) {
int bestLen = 0, bestDist = 0;
int from = Math.max(0, i - window);
for (int j = from; j < i; j++) {
int len = 0;
while (i + len < s.length && s[j + len] == s[i + len]) {
len++;
}
if (len > bestLen) {
bestLen = len;
bestDist = i - j;
}
}
return bestLen >= 3 ? new int[] {bestDist, bestLen} : new int[] {0, 0};
}On the timeout line at i = 16 with window ≥ 16, that returns {16, 14}. Do not bit-pack the result. Do not emit a gzip member from this loop.
What you ship is java.util.zip. Deflater is the zlib/DEFLATE engine. GZIPOutputStream writes a gzip member around it. The hub’s rule stands: do not hand-roll gzip.
static int zlibLen(byte[] raw) {
Deflater d = new Deflater(Deflater.DEFAULT_COMPRESSION);
try {
d.setInput(raw);
d.finish();
byte[] buf = new byte[raw.length + 64];
return d.deflate(buf);
} finally {
d.end();
}
}
static byte[] gzipBytes(byte[] raw) throws IOException {
ByteArrayOutputStream bos = new ByteArrayOutputStream();
try (GZIPOutputStream gz = new GZIPOutputStream(bos)) {
gz.write(raw);
}
return bos.toByteArray();
}Same two payloads, UTF-8, default compression (OpenJDK 21):
A "retry: timeout; retry: timeout"
UTF-8 30 zlib 27 gzip 39 wrapper can lose on a tiny buffer
B eight copies of "GET /health 200 OK\n"
UTF-8 152 zlib 30 gzip 42 the window pays; gzip header is ~constantThirty bytes of “we gzip’d it” can grow. One hundred fifty-two bytes of one repeated line shrink because the history still holds the line. The header cost barely moved.
Note: deflate() may need a loop if the output is larger than buf. The + 64 pad is enough for these tiny inputs. Always end() the Deflater. This post is not the Linux tar/gzip pipeline.
Complexity
Let n be the input length and W the window (≤ 32 KiB on typical DEFLATE).
| What | Cost | Why |
|---|---|---|
| Naive match at one cursor | O(W · L) | Try each origin; compare up to remaining / max match |
| Naive whole stream | O(n · W · L) | Repeat at each cursor |
| Extra space | O(W) | History the decoder must keep |
| Production finders | Hash chains, lazy match | zlib does not nested-scan 32 KiB per byte |
| Huffman stage | Alphabet of tokens | After LZ77; see the Huffman post |
Quoting Huffman O(σ log σ) as “the cost of gzip” hides both the window search and the linear scan of n bytes. The interesting bill for a naive lab is W. The interesting bill in production is the match finder you did not write.
Call Deflater / GZIPOutputStream. Do not ship the nested scan. The sketch is so you can see (16, 14). It is not a product compressor.
When not to use this pairing
Skip a home-grown DEFLATE when the job is not “smaller encoding of repeated phrases on a stream you will decode from the start.”
- You needed a gzip file. Call
GZIPOutputStream(or a zip entry viajava.util.zip). The hub says do not hand-roll gzip. This page does not make an exception. - The buffer is tiny. Headers and trees can beat the copy. Payload A grew under gzip. Measure.
- The bytes are already high entropy. Encrypted or already-compressed input has no phrases. The window emits literals; the wrapper still adds bytes.
- You needed Huffman on a known independent-symbol table. That is the Huffman post. Do not open a sliding window to encode five event types.
- You needed an array sliding window. Sums, distinct counts, longest valid slice — Sliding Window. History-for-copies is a different procedure.
- You needed random access into the blob. DEFLATE is a stream. Seeking means decoding from a sync point you stored, or not compressing that way.
- You wanted PNG block layout or a bit-packer. Out of scope. Canonical codes belong to the wire spec; this post stops at tokens.
Window, then prefix-code the tokens — that is the job. Arithmetic coding is another entropy family. The Linux gzip command line is a different post. Do not open either here.
Cheat sheet
Job: smaller encoding of repeated phrases
LZ77: history window; emit literal or (distance, length)
DEFLATE: those tokens, then Huffman (canonical on the wire)
Window: typically 32 KiB; DEFLATE min match 3, max 258
Cost: naive O(n W L); production uses a match finder
JDK: java.util.zip.Deflater / GZIPOutputStream
Call: do not hand-roll gzip
Not this: Huffman-on-raw-bytes, array sliding-window, tar|gzip CLI,
DEFLATE bit-packer, PNG blocks, arithmetic codingDo:
- Search already-emitted bytes for a phrase you are about to write.
- Huffman-code the tokens. Link the Huffman post; do not re-lecture the heap.
- Call
java.util.zipfor zip/gzip. Measure tiny payloads — headers can win.
Don’t:
- Call Huffman gzip or treat the Huffman lab as DEFLATE.
- Hand-roll a gzip member, a zlib wrapper, or a bit-packer from the matcher sketch.
- Quote Huffman heap cost as the cost of compressing
nbytes. - Teach
tar/gzipon the command line here — this is the algorithm behind them.
Wrap-up
LZ77 keeps a window of bytes already emitted and writes a repeat as a (distance, length) pair, with unmatched bytes as literals. DEFLATE is that token stream plus Huffman on the tokens — the pairing behind zip and gzip, not Huffman on the raw dump. The timeout line became sixteen literals and one pointer. The eight health-check lines shrank under GZIPOutputStream because the history still held the line. Call java.util.zip. Do not ship a tree and name it gzip.
The layout is a byte stream plus a bounded history. The procedure is match-in-window, then entropy-code the tokens. When the next job is picking which named procedure, that is the capstone — still upcoming. The catalog is the hub.