Sequitur algorithm: Difference between revisions

Revision as of 07:18, 26 September 2014

Revision as of 07:44, 19 May 2015

Line 19:

== 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 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' 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 Utility ==