LZW

A real LZW encoder writes codes into a bit stream whose width grows as the table does — nine bits, then ten, then eleven — and the saving is measured in bits against the input’s bits. This page emits JavaScript numbers into an array. The only ratio it prints is symbols per code, which is a fact about the dictionary rather than about a file, and calling it compression would be a claim about a thing nobody ships.

A deployed encoder seeds the table from a fixed alphabet decided before anything is read, rather than from the input: TIFF from the 256 byte values, GIF from a code size the image header declares, which is why its first codes depend on the picture’s palette and not on this sentence. An earlier version of this entry said both formats seed with 256 byte values, which is not true of GIF and was corrected after an outside reader caught it. This page seeds the table with the distinct characters of whatever you typed, sorted, so the codes on screen are small enough to follow. That changes every code number from what a real encoder would emit and changes none of the mechanism.

Every deployed LZW has to decide what to do when the dictionary reaches its maximum code: GIF emits a clear code and starts again, and some encoders freeze the table instead. Neither is implemented. The strings this page accepts are far too short to reach any limit, so the case never arises and the page does not pretend to handle it.

Unisys held US patent 4,558,302 on the algorithm and began enforcing it against GIF encoders in 1994, which is why PNG exists. The patent expired in 2003 and 2004 depending on jurisdiction. The page dates the machine 1984-1987 — Welch’s paper, then the patent grant and the compression formats that adopted it — and none of that is a claim about who invented what: LZW is Welch’s refinement of Lempel and Ziv’s 1978 algorithm and is named for all three.