184 CHAPTER 8: CONCLUSIONS
algorithm to the sequence first, and then produce an automaton from the higher-
level non-terminals. This is a compelling symbiosis: SEQUITUR identifies the
significant segments of the sequences, and the automaton captures the branching
and looping relationships between them. The combination is analogous to the
lexical analyser and parsing passes of a compiler, where the first pass groups
individual characters into meaningful tokens for the second pass. The main problem
with this approach is the ease with which SEQUITUR can be misled to recognise
segments that include more than a single token. Investigating solutions to this
problem is also a direction for future work.
Another technique for generalising grammars involves recognising self-similarity in
the hierarchical structure of a sequence (?recognising self-similarity? in Figure?8.1).
Recursive grammars such as the fractal L-system grammars for producing snowflake
and tree-like figures give rise to similar patterns at different levels of detail. With
the improved inference achieved by retrospective reparsing, this self-similarity is
clearly exhibited in SEQUITUR?s hierarchies. Automatically recognising this
recursive structure consists of finding a unification of two rules that produces a
concise recursive grammar capable of reproducing the original sequence. Again, the
algorithm is simple: it consists of only six Prolog clauses.
The final major technique introduced is a way of encoding a grammar to achieve
data compression (?encoding scheme? in Figure?8.1). This transforms the SEQUITUR
algorithm into a compression scheme that can be evaluated alongside a large cohort
of similar schemes. It outperforms all other techniques in its class, and in several
instances achieves results better than any current compressor. Simply recoding the
final grammar for the sequence does not result in the best performance. Instead,
SEQUITUR operates at both the encoding and decoding ends, and enough
information is transmitted to trigger the two constraints operating at the decoder.
8.2 The applications
The problem of inferring concise and correct grammars from sequences precludes
optimal solutions. It is known from data compression that the problem of finding
the smallest hierarchy for a sequence is NP-complete (Storer, 1982). It is also
known from grammatical inference that no algorithm can guarantee to infer a
grammar from the sequences that it produces (Gold, 1967). Furthermore, in many