World Library  
Flag as Inappropriate
Email this Article

Sequitur algorithm

Article Id: WHEBN0001234577
Reproduction Date:

Title: Sequitur algorithm  
Author: World Heritage Encyclopedia
Language: English
Subject: Grammar-based code, Non sequitur, Grammar induction, Data compression, Lossless compression algorithms
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

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.[2]

Contents

  • Constraints 1
  • Digram Uniqueness 2
  • Rule Utility 3
  • Method summary 4
  • See also 5
  • References 6
  • External links 7

Constraints

Sequitur algorithm constructs grammar by substituting repeating phrases in the given sequence with new rules and therefore produces concise representation of the sequence. For example, if the sequence is S→abcab, sequitur algorithm will produce: S→AcA, A→ab. While scanning the input sequence, sequitur algorithm follows two constraints for generating its grammar efficiently: digram uniqueness and rule utility.

Digram Uniqueness

Whenever a new symbol is scanned from the sequence, it is appended with the last scanned symbol to form a new digram. If this digram has been formed earlier then a new rule is made to replace both the occurrences of the digrams. Therefore, it ensures that no digram occurs more than once in the grammar. For example, in sequence S→abaaba, when the first four symbols are already scanned, digrams formed are - ab, ba, aa. When the fifth symbol is read, a new digram 'ab' is formed which exists already. Therefore, both instances of 'ab' are replaced by a new rule (say, A) in S. Now, the grammar becomes S→AaAa, A→ab, and the process continues until no repeated digram exists in the grammar.

Rule Utility

This constraint ensures that all the rules are used more than once in right side of all the productions of the grammar, i.e., if a rule occurs just once, it should be removed from the grammar and its occurrence should be substituted with the symbols from which it is created. For example, in the above example, if we scan the last symbol and apply digram uniqueness for 'Aa', then grammar will produce: S→BB, A→ab, B→Aa. Now, rule 'A' occurs only once in the grammar in B→Aa. Therefore, A is deleted and finally grammar becomes: S→BB, B→aba. This constraint helps in removing redundant rules from the grammar.

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. If a pair's nonterminal symbol is used only in the just created symbol's definition, the used symbol is replaced by its definition and the symbol is removed from the defined nonterminal symbols. 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. ^  
  2. ^  

External links

  • sequitur.info - the reference Sequitur algorithm implementation in C++, Java, and other languages.
  • GrammarViz 2.0 - Sequitur and parallel Sequitur implementations in Java, Sequitur-based time series patterns discovery.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.