Nevill-Manning, C. G. & Witten, I. H. (1996). Compression and explanation using hierarchical grammars. (Working paper 96/16). Hamilton, New Zealand: University of Waikato, Department of Computer Science.
Abstract
Data compression is an eminently pragmatic pursuit: by removing redundancy, storage can be utilised more efficiently. Identifying redundancy also serves a less prosaic purpose-it provides cues for detecting structure, and the recognition of structure coincides with one of the goals of artificial intelligence: to make sense of the world by algorithmic means. This paper describes an algorithm that excels at both data compression and structural inference. This algorithm is implemented in a system call SEQUITUR that efficiently deals with sequences containing millions of symbols.
