TY - JOUR

T1 - 40 Years of suffix trees

AU - Apostolico, Alberto

AU - Crochemore, Maxime

AU - Farach-Colton, Martin

AU - Galil, Zvi

AU - Muthukrishnan, Shanmugavelayutham

PY - 2016/4

Y1 - 2016/4

N2 - The suffix tree is the core data structure in string analysis. It has a rich history, with connections to compression, matching, automata, data structures and more. There are powerful techniques to build suffix trees and use them efficiently in many applications. The appearance of suffix trees merged with some interesting and independent developments in information theory. In his famous approach to the notion of information, Kolmogorov equated the information or structure in a string to the length of the shortest program that would be needed to produce that string by a Universal Turing Machine. In his original paper, Weiner listed a few applications of his 'bi-tree' including most notably offline string searching: preprocessing a text file to support queries that return the occurrences of a given pattern in time linear in the length of the pattern. Udi Manber and Eugene W. Myers took a different approach, however. In 1990, they introduced the ?suffix array,?31 which eliminated most of the structure of the suffix tree, but was still able to implement many of the same operations, requiring space equal to 2 integers per text character and searching in time.

AB - The suffix tree is the core data structure in string analysis. It has a rich history, with connections to compression, matching, automata, data structures and more. There are powerful techniques to build suffix trees and use them efficiently in many applications. The appearance of suffix trees merged with some interesting and independent developments in information theory. In his famous approach to the notion of information, Kolmogorov equated the information or structure in a string to the length of the shortest program that would be needed to produce that string by a Universal Turing Machine. In his original paper, Weiner listed a few applications of his 'bi-tree' including most notably offline string searching: preprocessing a text file to support queries that return the occurrences of a given pattern in time linear in the length of the pattern. Udi Manber and Eugene W. Myers took a different approach, however. In 1990, they introduced the ?suffix array,?31 which eliminated most of the structure of the suffix tree, but was still able to implement many of the same operations, requiring space equal to 2 integers per text character and searching in time.

UR - http://www.scopus.com/inward/record.url?scp=84963800354&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84963800354&partnerID=8YFLogxK

U2 - 10.1145/2810036

DO - 10.1145/2810036

M3 - Review article

AN - SCOPUS:84963800354

SN - 0001-0782

VL - 59

SP - 66

EP - 73

JO - Communications of the ACM

JF - Communications of the ACM

IS - 4

ER -