Compression and Explanation using Hierarchical Grammars

1 January 1997

journal article
research article
Published by Oxford University Press (OUP) in The Computer Journal

Vol. 40 (2 and 3) , 103-116
https://doi.org/10.1093/comjnl/40.2_and_3.103

Abstract

This paper describes an algorithm, called SEQUITUR, that identifies hierarchical structure in sequences of discrete symbols and uses that information for compression. On many practical sequences it performs well at both compression and structural inference, producing comprehensible descriptions of sequence structure in the form of grammar rules. The algorithm can be stated concisely in the form of two constraints on a context-free grammar. Inference is performed incrementally, the structure faithfully representing the input at all times. It can be implemented efficiently and operates in a time that is approximately linear in sequence length. Despite its simplicity and efficiency, SEQUITUR succeeds in inferring a range of interesting hierarchical structures from naturally occurring sequences.

Keywords

This publication has 0 references indexed in Scilit: