 |
HAL UPEC - UPEM Portal |  |
 |
Conference papers
Direct construction of compact Directed Acyclic Word Graphs
Abstract : The Directed Acyclic Word Graph (DAWG) is an efficient data structure to treat and analyze repetitions in a text, especially in DNA genomic sequences. Here, we consider the Compact Directed Acyclic Word Graph of a word. We give the first direct algorithm to construct it. It runs in time linear in the length of the string on a fixed alphabet. Our implementation requires half the memory space used by DAWGs.
Cited literature [14 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-00620006
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 6:27:04 PM
Last modification on : Wednesday, February 3, 2021 - 7:54:25 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:59:36 AM
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 6:27:04 PM
Last modification on : Wednesday, February 3, 2021 - 7:54:25 AM
Long-term archiving on: : Tuesday, May 14, 2013 - 3:59:36 AM
File
97-CPM.pdf
Files produced by the author(s)