A categorization theorem on suffix arrays with applications to space efficient text indexes

ABSTRACT

In this paper, we design succinct index structures for a text string T of n binary symbols to support efficient searching of a pattern P of length m. Motivated by the fact that the standard representation of suffix arrays uses n lg n bits which is more than the theoretical minimum, we present a theorem that characterizes a permutation as the suffix array of a binary string. Based on the theorem, we design a succinct representation of suffix arrays of binary strings that uses n + o(n) bits, which is the theoretical minimum plus a lower order term, and answers existential and cardinality queries in O(m) time without storing the raw text. With 2n+o(n) bits, we can list pattern occurrences in O(m + occ lg n) time in the general case, and for long patterns, when m = Ω(lg^1+∈ n), we answer such listing queries in O(m + occ) time. We also present another implementation that uses O(n) bits and supports pattern searching in O(m + occ lg^λ n) time for any fixed λ such that 0 < λ < 1. More results and trade-offs are reported in the paper.

REFERENCES

• 1: S. Alstrup , G. Stolting Brodal , T. Rauhe, New data structures for orthogonal range searching, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.198, November 12-14, 2000
• 2: S. Burkhardt and J. Kärkkäinen. Fast light suffix array construction and checking. In Proceedings of the 14th Symposium on Combinatorial Pattern Matching, pages 55--69. Springer-Verlag LNCS 2676, 2003.
• 3: M. Burrows and D. Wheeler. A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation, 1994.
• 4: David R. Clark , J. Ian Munro, Efficient suffix trees on secondary storage, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.383-391, January 28-30, 1996, Atlanta, Georgia, United States
• 5: 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
• 6: Paolo Ferragina , Giovanni Manzini, An experimental study of an opportunistic index, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.269-278, January 07-09, 2001, Washington, D.C., United States
• 7: Paolo Ferragina , Giovanni Manzini, On compressing and indexing data, University of Pisa, 2002
• 8: Gaston H. Gonnet , Ricardo A. Baeza-Yates , Tim Snider, New indices for text: PAT Trees and PAT arrays, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 9: Roberto Grossi , Ankur Gupta , Jeffrey Scott Vitter, High-order entropy-compressed text indexes, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 10: R. Grossi and J. S. Vitter. Compressed suffix arrays and suffix trees with applications to text indexing and string matching. Manuscript, http://www.cs.duke.edu/~jsv/Papers/GrV00.text_indexing_slides.ps.gz.
• 11: 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]
• 12: Donna Harman , R. Baeza-Yates , Edward Fox , W. Lee, Inverted files, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 13: G. Jacobson. Space-efficient static trees and graphs. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pages 549--554, 1989.
• 14: D. K. Kim, J. S. Sim, H. Park, and K. Park. Linear-time construction of suffix arrays. In Proceedings of the 14th Symposium on Combinatorial Pattern Matching, pages 186--199. Springer-Verlag LNCS 2676, 2003.
• 15: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 16: P. Ko and S. Aluru. Space efficient linear time construction of suffix arrays. In Proceedings of the 14th Symposium on Combinatorial Pattern Matching, pages 200--210. Springer-Verlag LNCS 2676, 2003.
• 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: J. I. Munro. Succinct data structures. In Proceedings of Workshop on Data Structures, pages 3--7, 1999.
• 19: Rajeev Raman , Venkatesh Raman , S. Srinivasa Rao, Succinct indexable dictionaries with applications to encoding k-ary trees and multisets, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.233-242, January 06-08, 2002, San Francisco, California
• 20: Kunihiko Sadakane, Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Array, Proceedings of the 11th International Conference on Algorithms and Computation, p.410-421, December 18-20, 2000
• 21: P. Weiner. Linear pattern matching algorithm. In Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theory, pages 1--11, 1973.