Unix compress: the LZW and Terses approach
The filing of the Sperry patent by Terry Welsh on LZW was preceded by three weeks by the Victor Miller and Mark Wegman patent filed by IBM on the algorithm they named "terses". The talk describes the basis for the LZW/Terses algorithm, and its origin in the 1978 paper by J. Ziv and A. Lempel, "Compression of Individual Sequences via Variable-Rate Coding" and an incremental parsing algorithm. A symbolwise equivalent of the ZL78 (or LZ78) algorithm was published by Langdon, and is also described. A key component of ZL78 is the use of a "parse tree". We show how the parse tree is a symbol-counting mechanism in disguise.