Sequitur Algorithm
Jump to navigation
Jump to search
A Sequitur Algorithm is a Recursive Algorithm that infers a context-free grammar from a sequence of discrete symbols.
- AKA: Nevill-Manning Algorithm.
- Example(s):
- …
- Counter-Example(s):
- See: Data Compression, Craig Nevill-Manning, Ian H. Witten, Context-Free Grammar.
References
2021
- (Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/Sequitur_algorithm Retrieved:2021-5-2.
- 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]
- ↑ Nevill-Manning, C.G.; Witten, I.H. (1997). "Identifying Hierarchical Structure in Sequences: A linear-time algorithm". arXiv:cs/9709102.
- ↑ Nevill-Manning, C.G.; Witten, I.H. (1997). "Linear-Time, Incremental Hierarchy Inference for Compression". Proceedings DCC '97. Data Compression Conference. pp. 3–11. CiteSeerX 10.1.1.30.2305. doi:10.1109/DCC.1997.581951. ISBN 978-0-8186-7761-8.