Loading...
Thumbnail Image
Item

Compression by induction of hierarchical grammars

Abstract
This paper describes a technique that develops models of symbol sequences in the form of small, human-readable, hierarchical grammars. The grammars are both semantically plausible and compact. The technique can induce structure from a variety of different kinds of sequence, and examples are given of models derived from English text, C source code and a file of numeric data. This paper explains the grammatical induction technique, demonstrates its application to three very different sequences, evaluates its compression performance, and concludes by briefly discussing its use as method of knowledge acquisition.
Type
Working Paper
Type of thesis
Series
Computer Science Working Papers
Citation
Nevill-Manning, C. G., Witten, I. H., & Maulsby, D. (1993). Compression by induction of hierarchical grammars (Computer Science Working Papers 93/9). Hamilton, New Zealand: Department of Computer Science, University of Waikato.
Date
1993
Publisher
Department of Computer Science, University of Waikato
Degree
Supervisors
Rights
© 1993 by Craig G. Nevill-Manning, Ian H. Witten & David L. Maulsby