Sequitur algorithm: Difference between revisions

Revision as of 19:07, 10 May 2008

Revision as of 19:11, 10 May 2008

Line 1:

:''Sequitur redirects here. For the Latin phrase, see [[Non sequitur]]. For the cutting implement, see [[Secateur]].''

'''Sequitur''' (or ''Nevill-Manning algorithm'') is an recursive algorithm that creates infers a ''[[grammar]]''hierarchical structure from thea sequence of discrete symbols useddeveloped toby represent[[Craig aNevill-Manning]] problem. This algorithm can be used inand [[dataIan compressionH. Witten]] softwarein applications1997.<ref name=Nevill-manning1997>{{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

}}</ref> The algorithm operates in linear space and time. It can be used in [[data 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 invented [[nonterminal 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.

==References==

{{reflist}}

==External links==