Many different index structures, providing efficient solutions to problems related to pattern matching, have been introduced so far. Examples of these structures are suffix trees and directed acyclic word graphs (DAWGs), which can be efficiently constructed in linear time and space. Compact directed acyclic word graphs (CDAWGs) are an index structure preserving some features of both suffix trees and DAWGs, and require less space than both of them. An algorithm which directly constructs CDAWGs in linear time and space was first introduced by Crochemore and Verin, based on McCreight's algorithm for constructing suffix trees. In this work, we present a novel on-line linear-time algorithm that builds the CDAWG for a single string as well as for a set of strings, inspired by Ukkonen's on-line algorithm for constructing suffix trees.
On-line construction of compact directed acyclic word graphs / S. Inenaga, H. Hoshino, A. Shinohara, M. Takeda, S. Arikawa, G. Mauri, G. Pavesi. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 146:2(2005), pp. 156-179. ((Intervento presentato al 12. convegno Annual Symposium on Combinatorial Pattern Matching (CPM 2001) tenutosi a Jerusalem nel 2001.
On-line construction of compact directed acyclic word graphs
G. PavesiUltimo
2005
Abstract
Many different index structures, providing efficient solutions to problems related to pattern matching, have been introduced so far. Examples of these structures are suffix trees and directed acyclic word graphs (DAWGs), which can be efficiently constructed in linear time and space. Compact directed acyclic word graphs (CDAWGs) are an index structure preserving some features of both suffix trees and DAWGs, and require less space than both of them. An algorithm which directly constructs CDAWGs in linear time and space was first introduced by Crochemore and Verin, based on McCreight's algorithm for constructing suffix trees. In this work, we present a novel on-line linear-time algorithm that builds the CDAWG for a single string as well as for a set of strings, inspired by Ukkonen's on-line algorithm for constructing suffix trees.File | Dimensione | Formato | |
---|---|---|---|
On-line-construction-of-compact-directed-acyclic-word-graphs_2005_Discrete-Applied-Mathematics.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
561.46 kB
Formato
Adobe PDF
|
561.46 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.