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

Alexander Vahitov

Approximate String Indexing


Abstract

Using simple mathematical arguments the matching probabilities in the suffix tree are bound and by a clever division of the search pattern sub-linear time is achieved.
The report is based on the article of G. Navarro and R. Baeza-Yates 'A Hybrid Indexing Method For Approximate String Matching'


Presentation:
03 Vakhitov Alexander Approximate text indexing.ppt
Paper:
Chapter 3 (Postscript PS, PDF PDF) of the proceedings (Postscript PS, PDF PDF).