TY - GEN
T1 - Augmenting suffix trees, with applications
AU - Matias, Yossi
AU - Muthukrishnan, S.
AU - Sahinalp, Süleyman Cenk
AU - Ziv, Jacob
PY - 1998
Y1 - 1998
N2 - Information retrieval and data compression are the two main application areas where the rich theory of string algorithmics plays a fundamental role. In this paper, we consider one algorithmic problem from each of these areas and present highly efficient (linear or near linear time) algorithms for both problems. Our algorithms rely on augmenting the suffix tree, a fundamental data structure in string algorithmics. The augmentations are nontrivial and they form the technical crux of this paper. In particular, they consist of adding extra edges to suffix trees, resulting in Directed Acyclic Graphs (DAGs). Our algorithms construct these "suffix DAGs" and manipulate them to solve the two problems efficiently.
AB - Information retrieval and data compression are the two main application areas where the rich theory of string algorithmics plays a fundamental role. In this paper, we consider one algorithmic problem from each of these areas and present highly efficient (linear or near linear time) algorithms for both problems. Our algorithms rely on augmenting the suffix tree, a fundamental data structure in string algorithmics. The augmentations are nontrivial and they form the technical crux of this paper. In particular, they consist of adding extra edges to suffix trees, resulting in Directed Acyclic Graphs (DAGs). Our algorithms construct these "suffix DAGs" and manipulate them to solve the two problems efficiently.
UR - http://www.scopus.com/inward/record.url?scp=84896750316&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84896750316&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84896750316
SN - 3540648488
SN - 9783540648482
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 67
EP - 78
BT - Algorithms, ESA 1998 - 6th Annual European Symposium, Proceedings
PB - Springer Verlag
T2 - 6th Annual European Symposium on Algorithms, ESA 1998
Y2 - 24 August 1998 through 26 August 1998
ER -