Description
Sequiter Software (or Nevill-Manning algorithm) is a recursive algorithm developed by Craig Nevill-Manning and Ian H. Witten in 1997that 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.
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.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' is replaced by a new rule(say, A) in S. Now, grammar becomes, S?AaAa, A?ab, and process continues till no repeated digram exists in the grammar.
| Founded: | |
| Corporate Office: | |
| Facebook: | |
| Twitter: | |
| LinkedIn: | |
| WebSite: | http://www.sequiter.com/ |