PDMI TUM State University St. Petersburg
Steklov Institute St. Petersburg Technische Universität München State University St. Petersburg

Joint Advanced Student School (JASS)

Course 1: Complexity Analysis of String Algorithms


St. Petersburg - Sunday, March 28 through Wednesday, April 7, 2004

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.


Presentation:
05 Kazmenko Ivan Asymptotic properties of suffix trees.pdf
Paper:
Chapter 5 (Postscript PS, PDF PDF) of the proceedings (Postscript PS, PDF PDF).