Sequitur algorithm

Sequitur algorithm

Sequitur (or Nevill-Manning algorithm) is a recursive algorithm developed by Craig Nevill-Manning and Ian H. Witten in 1997[1] that infers a hierarchical structure (context-free grammar) from a sequence of discrete symbols. The algorithm operates in linear space and time. It can be used in data compression software applications.

Contents

Method summary

The algorithm works by scanning a sequence of terminal symbols, 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.

See also

References

  1. ^ Nevill-Manning, C.G.; Witten, I.H. (1997). Identifying Hierarchical Structure in Sequences: A linear-time algorithm. arXiv:cs/9709102. 

External links



Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • 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 and Ian H. Witten in 1997.cite journal author =… …   Wikipedia

  • Sequitur — ist ein Algorithmus zur verlustfreien Datenkompression, welcher in der Arbeit “Identifying hierarchical structure in sequences: A linear time algorithm“ von Craig Nevill Manning und Ian Witten von der Universität von Waikato, Neuseeland im Jahr… …   Deutsch Wikipedia

  • Non sequitur — (pronounced /nɒnˈsɛkwɪtər/) is Latin for it does not follow. It is most often used as a noun to describe illogical statements. Non sequitur may refer to: Non sequitur (literary device), an irrelevant, often humorous comment to a preceding topic… …   Wikipedia

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

  • Grammar-based code — Grammar based codes are compression algorithms based on the idea of constructing a context free grammar for the string to be compressed. Examples include universal lossless data compression algorithms proposed in Kieffer and Yang 2000, and… …   Wikipedia

  • Wave–particle duality — Quantum mechanics Uncertainty principle …   Wikipedia

  • Context-free grammar generation algorithms — are algorithms which generate a context free grammar or grammars from given symbol sequence or sequences.Applications for such algorithms include lossless data compression and data mining. A list of algorithms * Sequitur * Lempel Ziv Welch… …   Wikipedia

  • Straight-line grammar — Straight line grammars (SLG) are formal grammars that do not branch (every non terminal has only one associated production rule) nor loop (if non terminal A appears in a derivation of B, B does not appear in a derivation of A). Such grammars… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”