Directed acyclic word graph: Difference between revisions
Content deleted Content added
No edit summary |
Carry out proposed merge |
||
| Line 1: | Line 1: | ||
#REDIRECT [[Suffix automaton]] |
|||
{{R from merge}} |
|||
{{distinguish|Deterministic acyclic finite state automaton}} |
|||
In [[computer science]], a '''directed acyclic word graph''' ('''DAWG''') is a [[data structure]] that represents the set of all [[substring]]s of a string. As its name implies, a DAWG takes the form of a [[directed acyclic graph]]; it can also be viewed as a [[deterministic finite automaton]], and is similar in structure to [[suffix tree]]s. DAWG have applications in [[approximate string matching]].<ref>{{Cite journal | last1 = Navarro | first1 = Gonzalo| doi = 10.1145/375360.375365 | title = A guided tour to approximate string matching | journal = ACM Computing Surveys | volume = 33| issue = 1| pages = 31–88| year = 2001 | pmid = | pmc = | url = http://repositorio.uchile.cl/bitstream/handle/2250/126168/Navarro_Gonzalo_Guided_tour.pdf}}</ref> |
|||
==See also== |
|||
* [[GADDAG]] |
|||
* [[Suffix array]] |
|||
==References== |
|||
{{reflist}} |
|||
*{{citation | doi=10.1109/SPIRE.2001.989743|last1= Inenaga|first1= S.|last2= Hoshino|first2=H.|last3= Shinohara|first3= A. |last4= Takeda|first4= M. |last5= Arikawa|first5= S. |contribution= On-line construction of symmetric compact directed acyclic word graphs|title=Proc. 8th Int. Symp. String Processing and Information Retrieval, 2001. SPIRE 2001|year=2001|pages=96–110|url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=989743|isbn= 0-7695-1192-9}}. |
|||
*{{citation | first1=Maxime | last1=Crochemore | first2=Renaud | last2=Vérin | contribution=Direct construction of compact directed acyclic word graphs | series=[[Lecture Notes in Computer Science]] | publisher=Springer-Verlag | title=Combinatorial Pattern Matching | year=1997 | pages=116–129 | doi=10.1007/3-540-63220-4_55 }}. |
|||
*{{citation | last1=Epifanio | first1=Chiara | last2=Mignosi | first2=Filippo | last3=Shallit | first3=Jeffrey | last4=Venturini | first4=Ilaria | chapter=Sturmian graphs and a conjecture of Moser | pages=175–187 | editor1-last=Calude | editor1-first=Cristian S. | editor2-last=Calude | editor2-first=Elena | editor3-last=Dineen | editor3-first=Michael J. | title=Developments in language theory. Proceedings, 8th international conference (DLT 2004), Auckland, New Zealand, December 2004 | year=2004 | publisher=[[Springer-Verlag]] | series=Lecture Notes in Computer Science | volume=3340 | isbn=3-540-24014-4 | zbl=1117.68454 }} |
|||
*{{citation | first1=H.H. | last1=Do | first2=W.K. | last2=Sung | contribution=Compressed Directed Acyclic Word Graph with Application in Local Alignment | series=Lecture Notes in Computer Science | publisher=[[Springer-Verlag]] | title=Computing and Combinatorics | volume=6842 | pages=503–518 | doi=10.1007/978-3-642-22685-4_44 | year=2011 | isbn=978-3-642-22684-7 }} |
|||
{{Data structures}} |
|||
[[Category:Graph data structures]] |
|||
[[Category:String data structures]] |
|||
[[Category:Finite automata]] |
|||
{{compu-stub}} |
|||
Revision as of 23:56, 21 February 2016
Redirect to:
- From a merge: This is a redirect from a page that was merged into another page. This redirect was kept in order to preserve the edit history of this page after its content was merged into the content of the target page. Please do not remove the tag that generates this text (unless the need to recreate content on this page has been demonstrated) or delete this page.
- For redirects with substantive page histories that did not result from page merges use {{R with history}} instead.