×

Compressed index for a dynamic collection of texts. (English) Zbl 1103.68473

Sahinalp, Suleyman Cenk (ed.) et al., Combinatorial pattern matching. 15th annual symposium, CPM 2004, Istanbul, Turkey, July 5–7, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22341-X/pbk). Lecture Notes in Computer Science 3109, 445-456 (2004).
Summary: Let \(T\) be a string with \(n\) characters over an alphabet of bounded size. The recent breakthrough on compressed indexing allows us to build an index for \(T\) in optimal space (i.e., \(O (n)\) bits), while supporting very efficient pattern matching. This paper extends the work on optimal-space indexing to a dynamic collection of texts. Precisely, we give a compressed index using \(O (n)\) bits where \(n\) is the total length of texts, such that searching for a pattern \(P\) takes \(O(| P|\log n +\text{occ} \log^{2} n)\) time where occ is the number of occurrences, and inserting or deleting a text \(T\) takes \(O(| T |\log n)\) time.
For the entire collection see [Zbl 1052.68008].

MSC:

68P05 Data structures
68P10 Searching and sorting
PDFBibTeX XMLCite
Full Text: DOI