40 years of suffix trees

less than 1 minute read

Apostolico, A., Crochemore, M., Farach-Colton, M., Galil, Z., & Muthukrishnan, S. (2016). 40 Years of Suffix Trees. Commun. ACM, 59(4), 66–73. https://doi.org/10.1145/2810036

Suffix trees are used in text searching, indexing, statistics. This article describes the history, construction, current developments and applications of suffix trees.

Of special interest are applications that use suffix tries in conjunction with the Burrows-Wheeler transformation for compression and structures such as the succinct suffix tree and the suffix array that aim at reducing the space requirements of the tree.