Dynamic dictionary matching and compressed suffix trees

ABSTRACT

Recent breakthrough in compressed indexing data structures has reduced the space for indexing a text (or a collection of texts) of length n from O(n log n) bits to O(n) bits, while allowing very efficient pattern matching [10, 13]. Yet the compressed nature of such indices also makes them difficult to update dynamically. This paper presents the first O(n)-bit representation of a suffix tree for a dynamic collection of texts whose total length is n, which supports insertion and deletion of a text T in O(|T | log² n) time, as well as all suffix tree traversal operations, including forward and backward suffix links. This work can be regarded as a generalization of the compressed representation of static texts. Our new suffix tree representation serves as a core part in a compact solution for the dynamic dictionary matching problem, i.e., providing an O(d)-bit data structure for a dynamic collection of patterns of total length d that can support the dictionary matching query efficiently. When compared with the O(d log d)-bit suffix tree based solution of Amir et al., the compact solution increases the query time by roughly a factor of log d only. In the study of the above results, we also derive the first O(n)-bit representation for maintaining n pairs of balanced parentheses in O(log n/log log n) time per operation, matching the time complexity of the previous O(n log n)-bit solution.

REFERENCES

• 1: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 2: Amihood Amir , Martin Farach, Adaptive dictionary matching, Proceedings of the 32nd annual symposium on Foundations of computer science, p.760-766, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185445]
• 3: Amihood Amir , Martin Farach , Zvi Galil , Raffaele Giancarlo , Kunsoo Park, Dynamic dictionary matching, Journal of Computer and System Sciences, v.49 n.2, p.208-222, Oct. 1994 [doi>10.1016/S0022-0000(05)80047-9]
• 4: Amihood Amir , Martin Farach , Ramana M. Idury , Johannes A. La Poutré , Alejandro A. Schäffer, Improved dynamic dictionary matching, Information and Computation, v.119 n.2, p.258-282, June 1995 [doi>10.1006/inco.1995.1090]
• 5: Amihood Amir , Martin Farach , Yossi Matias, Efficient Randomized Dictionary Matching Algorithms (Extended Abstract), Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, p.262-275, April 29-May 01, 1992
• 6: M. Burrows and D. J. Wheeler. A Block-sorting Lossless Data Compression Algorithm. Technical Report 124, Digital Equipment Corporation, Paolo Alto, California, 1994.
• 7: H. L. Chan, W. K. Hon, and T. W. Lam. Compressed Index for a Dynamic Collection of Texts. In Proceedings of Symposium on Combinatorial Pattern Matching, pages 445--456, 2004.
• 8: W. I. Chang and E. L. Lawler. Sublinear Approximate String Matching and Biological Applications. Algorithmica, 12(4/5):327--344, 1994.
• 9: A. L. Delcher, S. Kasif, R. D. Fleischmann, J. Peterson, O. White, and S. L. Salzberg. Alignment of whole genomes. Nucleic Acids Research, 27(11):2369--2376, 1999.
• 10: P. Ferragina , G. Manzini, Opportunistic data structures with applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.390, November 12-14, 2000
• 11: M. Fredman , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73040]
• 12: R. Grossi and G. F. Italiano. Suffix Trees and their Applications in String Algorithms. In Proceedings of South American Workshop on String Processing, pages 57--76, 1993.
• 13: Roberto Grossi , Jeffrey Scott Vitter, Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.397-406, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335351]
• 14: Roberto Grossi , Ankur Gupta , Jeffrey Scott Vitter, When indexing equals compression: experiments with compressing suffix arrays and applications, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 15: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 16: G. Jacobson. Space-efficient Static Trees and Graphs. In Proceedings of Symposium on Foundations of Computer Science, pages 549--554, 1989.
• 17: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing, v.22 n.5, p.935-948, Oct. 1993 [doi>10.1137/0222058]
• 18: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 19: J. Ian Munro , Venkatesh Raman, Succinct Representation of Balanced Parentheses and Static Trees, SIAM Journal on Computing, v.31 n.3, p.762-776, 2001 [doi>10.1137/S0097539799364092]
• 20: Rajeev Raman , Venkatesh Raman , S. Srinivasa Rao, Succinct Dynamic Data Structures, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.426-437, August 08-10, 2001
• 21: Kunihiko Sadakane, Succinct representations of lcp information and improvements in the compressed suffix arrays, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.225-232, January 06-08, 2002, San Francisco, California
• 22: K. Sadakane. Compressed Suffix Trees with Full Functionality. Theory of Computing Systems, accepted.
• 23: S. C. Sahinalp , U. Vishkin, Efficient approximate and dynamic matching of patterns using a labeling paradigm, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.320, October 14-16, 1996
• 24: P. Weiner. Linear Pattern Matching Algorithms. In Proceedings of Symposium on Switching and Automata Theory, pages 1--11, 1973.