93-45 An Efficient Algorithm for Dynamic Text Indexing

DIMACS TR: 93-45

An Efficient Algorithm for Dynamic Text Indexing

Authors: Ming Gu, Martin Farach and Richard Beigel

ABSTRACT
Text indexing is one of the fundamental problems of string matching. Indeed, the suffix tree, the central data structure of string matching, was developed as an efficient static text indexer. The text indexing problem is that of building a data structure on a text which allows the occurrences of patterns to be quickly looked up.

All previous text indexing schemes have been static in the sense that if the text is modified, the data structure must be rebuilt from scratch. In this paper, we present a first dynamic data structure and algorithms for the On-line Dynamic Text Indexing problem. Our algorithms are based on a novel data structure, the border tree, which exploits string periodicities.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-45.ps

DIMACS Home Page