Ivan Kazmenko

Asymptotic Properties of Suffix Trees

Abstract

Unlike the previous chapters, this one is not going to introduce a new sophisticated suffix tree construction algorithm, dig into its properties and prove that it works fast and fine. Instead, we'll consider one of the most dumb algorithms of suffix tree construction and find out that under certain conditions on the text, it almost surely works rather well, meaning that we can find almost sure upper and lower bound for the complexity of new suffix insertion while the size of the text tends to infinity.
This chapter is based on the article Asymptotic Properties of Data Compression And Suffix Trees by Wojciech Szpankowski and the book Average case analysis of algorithms on sequences by the same author.