Sequitur algorithm - Wikiwand
The 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,
the algorithm will produce
- S→AcA, A→ab.
While scanning the input sequence, the 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 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' 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 the right sides 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 one scans the last symbol and applies 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 reduce the number of rules in the grammar.