- SEQUITUR algorithm
Sequitur (or "Nevill-Manning algorithm") is an recursive algorithm that infers a hierarchical structure (context-free grammar) from a sequence of discrete symbols developed by
Craig Nevill-Manning andIan H. Witten in 1997.cite journal
author = Nevill-Manning, C.G.
coauthors = Witten, I.H.
year = 1997
title = Identifying Hierarchical Structure in Sequences: A linear-time algorithm
journal = Arxiv preprint cs.AI/9709102
url = http://arxiv.org/abs/cs/9709102
accessdate = 2008-04-10] The algorithm operates in linear space and time. It can be used indata compression software applications.Method summary
The algorithm works by scanning a sequence of
terminal symbol s, building a list of all the symbol pairs which it has read. Whenever a second occurrence of a pair is discovered, the two occurrences are replaced in the sequence by an inventednonterminal symbol , the list of symbol pairs is adjusted to match the new sequence, and scanning continues. Once the scanning has been completed, the transformed sequence can be interpreted as the top-level rule in a grammar for the original sequence. The rule definitions for the nonterminal symbols which it contains can be found in the list of symbol pairs. Those rule definitions may themselves contain additional nonterminal symbols whose rule definitions can also be read from elsewhere in the list of symbol pairs.ee also
* context-free grammar
* Algorithms for context-free grammar generation
* lossless data compression
*data compression References
External links
* [http://sequitur.info/ sequitur.info]
Wikimedia Foundation. 2010.
