Sequitur algorithm: Difference between revisions

Revision as of 18:55, 27 August 2014

Latest revision as of 00:53, 6 December 2024

(21 intermediate revisions by 17 users not shown)

Line 1:

'''Sequitur''' (or '''Nevill-ManningManning–Witten algorithm''') is a recursive algorithm developed by [[Craig Nevill-Manning]] and [[Ian H. Witten]] in 1997<ref name=Nevill-manning1997>{{cite journal

| author = [[Craig Nevill-Manning|Nevill-Manning, C.G.]]

| author-link = Craig Nevill-Manning

|author2=Witten, I.H.

| author2 = Witten, I.H.

| year = 1997

| title = Identifying Hierarchical Structure in Sequences: A linear-time algorithm

| arxiv = cs/9709102

}}</ref> 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.

| bibcode= 1997cs........9102N

}}</ref> 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.<ref name=Nevill-manning1997_2>{{cite book

| doi = 10.1109/DCC.1997.581951

| author = Nevill-Manning, C.G.

| author-link = Craig Nevill-Manning

| title = Proceedings DCC '97. Data Compression Conference

| pages = 3–11

| author2=Witten, I.H.

| year = 1997

| chapter = Linear-Time, Incremental Hierarchy Inference for Compression

| isbn = 978-0-8186-7761-8

| citeseerx = 10.1.1.30.2305

| s2cid = 14324301

}}</ref>

== Constraints ==

SequiturThe sequitur algorithm constructs a grammar by substituting repeating phrases in the given sequence with new rules and therefore produces a concise representation of the sequence. For example, if the sequence is
: S→abcab, sequitur
the algorithm will produce
: '''S→AcA, A→ab'''.

While scanning the input sequence, sequiturthe algorithm follows two constraints for generating its grammar efficiently: '''digram uniqueness''' and '''rule utility'''.

=== Digram Uniquenessuniqueness ===

Whenever a new symbol is scanned from the sequence, it is appended with the last scanned symbol to form a new [[Bigram|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 the 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' isare replaced by a new rule (say, A) in ''S''. Now, the grammar becomes, '''S→AaAa, A→ab''', and the process continues tilluntil no repeated digram exists in the grammar.

=== Rule Utilityutility ===

This constraint ensures that all the rules are used more than once in the right sidesides 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 weone scanscans the last symbol and applyapplies digram uniqueness for 'Aa', then the 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 the grammar becomes
: '''S→BB, B→aba'''.

This constraint helps inreduce removingthe redundantnumber of rules fromin the grammar.

== Method summary ==

The algorithm works by scanning a sequence of [[terminal symbol]]s, and 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.<ref>[https://github.com/GrammarViz2/grammarviz2_src GrammarViz 2.0 – Sequitur and parallel Sequitur implementations in Java, Sequitur-based time series patterns discovery]</ref>

==See also==

* [[Context-free grammar]]

* [[Straight-line grammar]]

* [[Lossless compression|Lossless data compression]]

* [[Data compression]]

* [[Lossless compression|Lossless data compression]]

* [[Straight-line grammar]]

* [[Byte pair encoding]]

==References==

{{reflistReflist}}

==External links==

* [http://www.sequitur.info/ sequitur.info] -– the reference Sequitur algorithm implementation in C++, Java, and other languages.]

*[http://github.com/GrammarViz2/grammarviz2_src GrammarViz 2.0] - Sequitur-based time series anomalous and recurrent patterns discovery.

{{Compression methods}}

[[Category:Lossless compression algorithms]]

[[Category:Data compression]]