Sequitur algorithm: Difference between revisions

Revision as of 17:04, 31 March 2014

Revision as of 14:40, 26 May 2014

Line 12:

== 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 occurencesoccurrences 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.

== 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 occurenceoccurrence 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.