Suffix automaton: Difference between revisions

Revision as of 20:26, 7 November 2020

Revision as of 20:27, 7 November 2020

Line 23:

[[File:Anselm Blumer with DAWG.jpg|thumb|288x288px|Anselm Blumer with a drawing of generalized CDAWG for strings ''ababc'' and ''abcab'']]

The concept of suffix automaton was introduced in 1983<ref>{{harvp|Crochemore, Hancart|1997|ppname=36—39|loc=}}<":16" /ref> by a group of scientists from [[University of Denver]] and [[University of Colorado Boulder]] consisting of Anselm Blumer, Janet Blumer, [[Andrzej Ehrenfeucht]], [[David Haussler]] and Ross McConnell, although similar concepts had earlier been studied alongside suffix trees in the works of Peter Weiner,<ref name=":5" /> Vaughan Pratt<ref>{{harvp|Pratt|1973}}</ref> and [[Anatol Slissenko]].<ref>{{harvp|Slisenko|1983}}</ref> In their initial work, Blumer ''et al''. showed a suffix automaton built for the string <math>S</math> of length greater than <math>1</math> has at most <math>2|S|-1</math> states and at most <math>3|S|-4</math> transitions, and suggested a linear [[algorithm]] for automaton construction.<ref name=":2">{{harvp|Blumer et al.|1984|loc=|p=109}}</ref>

In 1983, Mu-Tian Chen and Joel Seiferas independently showed that Weiner's 1973 suffix-tree construction algorithm<ref name=":5">{{harvp|Weiner|1973}}</ref> while building a suffix tree of the string <math>S</math> constructs a suffix automaton of the reversed string <math display="inline">S^R</math> as an auxiliary structure.<ref name=":6">{{harvp|Chen, Seiferas|1985|loc=|p=97}}</ref> In 1987, Blumer ''et al''. applied the compressing technique used in suffix trees to a suffix automaton and invented the compacted suffix automaton, which is also called the compacted directed acyclic word graph (CDAWG).<ref name=":7">{{harvp|Blumer et al.|1987|loc=|p=578}}</ref> In 1997, [[Maxime Crochemore]] and Renaud Vérin developed a linear algorithm for direct CDAWG construction.<ref name=":16">{{harvp|Crochemore, Vérin|1997|loc=|p=192}}</ref> In 2001, Shunsuke Inenaga ''et al''. developed an algorithm for construction of CDAWG for a set of words given by a [[trie]].<ref name=":8">{{harvp|Inenaga et al.|2001|loc=|p=1}}</ref>

== Definitions ==