TY - GEN
T1 - Space-economical construction of index structures for all suffixes of a string
AU - Inenaga, Shunsuke
AU - Shinohara, Ayumi
AU - Takeda, Masayuki
AU - Bannai, Hideo
AU - Arikawa, Setsuo
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - The minimum all-suffixes directed acyclic word graph (MASDAWG) of a string w has |w| + 1 initial nodes, where the dag induced by all reachable nodes from the k-th initial node conforms with the DAWG of the k-th suffix of w. A new space-economical algorithm for the construction of MASDAWG(w) is presented. The algorithm reads a given string w from right to left, and constructs MASDAWG(w) without suffix links. It performs in time linear in the output size. Furthermore, we introduce the minimum all-suffixes compact DAWG (MASCDAWG). CDAWGs are known to be more space-economical than DAWGs, and thus MASCDAWG(w) requires smaller space than MASDAWG(w). We present an on-line (right-to-left) algorithm to build MASCDAWG(w) without suffix links, whose running time is also linear in its size.
AB - The minimum all-suffixes directed acyclic word graph (MASDAWG) of a string w has |w| + 1 initial nodes, where the dag induced by all reachable nodes from the k-th initial node conforms with the DAWG of the k-th suffix of w. A new space-economical algorithm for the construction of MASDAWG(w) is presented. The algorithm reads a given string w from right to left, and constructs MASDAWG(w) without suffix links. It performs in time linear in the output size. Furthermore, we introduce the minimum all-suffixes compact DAWG (MASCDAWG). CDAWGs are known to be more space-economical than DAWGs, and thus MASCDAWG(w) requires smaller space than MASDAWG(w). We present an on-line (right-to-left) algorithm to build MASCDAWG(w) without suffix links, whose running time is also linear in its size.
UR - http://www.scopus.com/inward/record.url?scp=84956991457&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84956991457&partnerID=8YFLogxK
U2 - 10.1007/3-540-45687-2_28
DO - 10.1007/3-540-45687-2_28
M3 - Conference contribution
AN - SCOPUS:84956991457
SN - 3540440402
SN - 9783540440406
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 341
EP - 352
BT - Mathematical Foundations of Computer Science 2002 - 27th International Symposium, MFCS 2002, Proceedings
A2 - Diks, Krzysztof
A2 - Rytter, Wojciech
A2 - Rytter, Wojciech
PB - Springer Verlag
T2 - 27th International Symposium on Mathematical Foundations of Computer Science, MFCS 2002
Y2 - 26 August 2002 through 30 August 2002
ER -