Inducing Codes from Examples (Extended Abstract)
Wai-Hong Leung, Steven Skiena · 1991
We propose a data compression algorithm which automatically analyzes a collection of examples to identify the set of strings which would be most useful to encode the examples. There is considerable subtlety in identifying the most useful strings, since the problem is NP-complete, but we have developed analysis and encoding/decoding heuristics which construct excellent codes. In this paper, we describe our algorithm and experimental results on four different special domains: mailing addresses, Fortran programs, weather radar images, and UNIX manual pages. In each of these domains, our method significantly outperformed such standard compression algorithms as Huffman codes and LZW.