Compressed representations of sequences and full-text indexes

ABSTRACT

Given a sequence S = s₁s₂…s_n of integers smaller than r = O(polylog(n)), we show how S can be represented using nH₀(S) + o(n) bits, so that we can know any s_q, as well as answer rank and select queries on S, in constant time. H₀(S) is the zero-order empirical entropy of S and nH₀(S) provides an information-theoretic lower bound to the bit storage of any sequence S via a fixed encoding of its symbols. This extends previous results on binary sequences, and improves previous results on general sequences where those queries are answered in O(log r) time. For larger r, we can still represent S in nH₀(S) + o(n log r) bits and answer queries in O(log r/log log n) time.

Another contribution of this article is to show how to combine our compressed representation of integer sequences with a compression boosting technique to design compressed full-text indexes that scale well with the size of the input alphabet Σ. Specifically, we design a variant of the FM-index that indexes a string T[1, n] within nH_k(T) + o(n) bits of storage, where H_k(T) is the kth-order empirical entropy of T. This space bound holds simultaneously for all k ≤ α log_|Σ| n, constant 0 < α < 1, and |Σ| = O(polylog(n)). This index counts the occurrences of an arbitrary pattern P[1, p] as a substring of T in O(p) time; it locates each pattern occurrence in O(log^1+ϵ n) time for any constant 0 < ϵ < 1; and reports a text substring of length ℓ in O(ℓ + log^1+ϵ n) time.

Compared to all previous works, our index is the first that removes the alphabet-size dependance from all query times, in particular, counting time is linear in the pattern length. Still, our index uses essentially the same space of the kth-order entropy of the text T, which is the best space obtained in previous work. We can also handle larger alphabets of size |Σ| = O(n^β), for any 0 < β < 1, by paying o(n log|Σ|) extra space and multiplying all query times by O(log |Σ|/log log n).

REFERENCES

• 1: Burrows, M., and Wheeler, D. 1994. A block sorting lossless data compression algorithm. Tech. Rep. 124, Digital Equipment Corporation.
• 2: Chan, W.-L., Hon, W.-K., and Lam, T.-W. 2004. Compressed index for a dynamic collection of texts. In Proceedings of the Symposium on Combinatorial Pattern Matching (CPM). Lecture Notes in Computer Science, vol. 3109. Springer Verlag, Berlin. 445--456.
• 3: David Richard Clark, Compact pat trees, University of Waterloo, Waterloo, Ont., Canada, 1998
• 4: Maxime Crochemore , Wojciech Rytter, Text algorithms, Oxford University Press, Inc., New York, NY, 1994
• 5: Erik D. Demaine , Alejandro López-Ortiz, A linear lower bound on index size for text retrieval, Journal of Algorithms, v.48 n.1, p.2-15, August 2003 [doi>10.1016/S0196-6774(03)00043-9]
• 6: Paolo Ferragina , Raffaele Giancarlo , Giovanni Manzini , Marinella Sciortino, Boosting textual compression in optimal linear time, Journal of the ACM (JACM), v.52 n.4, p.688-713, July 2005 [doi>10.1145/1082036.1082043]
• 7: Paolo Ferragina , Fabrizio Luccio , Giovanni Manzini , S. Muthukrishnan, Structuring labeled trees for optimal succinctness, and beyond, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.184-196, October 23-25, 2005 [doi>10.1109/SFCS.2005.69]
• 8: An experimental study of a compressed index, Information Sciences: an International Journal, v.135 n.1-2, p.13-28, June, 2001 [doi>10.1016/S0020-0255(01)00098-6 ]
• 9: Paolo Ferragina , Giovanni Manzini, Indexing compressed text, Journal of the ACM (JACM), v.52 n.4, p.552-581, July 2005 [doi>10.1145/1082036.1082039]
• 10: Ferragina, P., Manzini, G., Mäkinen, V., and Navarro, G. 2004. An alphabet-friendly FM-index. In Proceedings of the 11th International Symposium on String Processing and Information Retrieval (SPIRE). Lecture Notes in Computer Science, vol. 3246. Springer Verlag, Berlin. 150--160.
• 11: Luca Foschini , Roberto Grossi , Ankur Gupta , Jeffrey Scott Vitter, When indexing equals compression: Experiments with compressing suffix arrays and applications, ACM Transactions on Algorithms (TALG), v.2 n.4, p.611-639, October 2006 [doi>10.1145/1198513.1198521]
• 12: Geary, R., Rahman, N., Raman, R., and V.Raman. 2004. A simple optimal representation for balanced parentheses. In Proceedings of the Symposium on Combinatorial Pattern Matching (CPM). Lecture Notes in Computer Science, vol. 3109. Springer Verlag, Berlin. 159--172.
• 13: Alexander Golynski , J. Ian Munro , S. Srinivasa Rao, Rank/select operations on large alphabets: a tool for text indexing, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.368-373, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109599]
• 14: 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
• 15: González, R., and Navarro, G. 2006. Statistical encoding of succinct data structures. In Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching (CPM). Lecture Notes in Computer Science, vol. 4009. Springer Verlag, Berlin. 295--306.
• 16: Grabowski, S., Navarro, G., Przywarski, R., Salinger, A., and Mäkinen, V. 2006. A simple alphabet-independent FM-index. Int. J. Found. Comput. Sci. 17, 6, 1365--1384.
• 17: 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
• 18: Roberto Grossi , Jeffrey Scott Vitter, Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching, SIAM Journal on Computing, v.35 n.2, p.378-407, 2005 [doi>10.1137/S0097539702402354]
• 19: Healy, J., Thomas, E., Schwartz, J., and Wigler, M. 2003. Annotating large genomes with exact word matches. Genome Res. 13, 2306--2315.
• 20: Wing-Kai Hon , Tak-Wah Lam , Kunihiko Sadakane , Wing-Kin Sung , Siu-Ming Yiu, Compressed Index for Dynamic Text, Proceedings of the Conference on Data Compression, p.102, March 23-25, 2004
• 21: Hon, W.-K., Lam, T.-W., Sung, W. K., Tse, W. L., Wong, C.-K., and Yiu, S. M. 2004. Practical aspects of compressed suffix arrays and FM-index in searching DNA sequences. In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 31--38.
• 22: Huynh, N., Hon, W., Lam, T., and Sung, W. 2004. Approximate string matching using compressed suffix arrays. In Proceedings of the Symposium on Combinatorial Pattern Matching (CPM). Lecture Notes in Computer Science, vol. 3109. Springer Verlag, Berlin. 434--444.
• 23: Jacobson, G. 1989. Space-Efficient static trees and graphs. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (FOCS). 549--554.
• 24: Mäkinen, V., and Navarro, G. 2004a. Compressed compact suffix arrays. In Proceedings of the Symposium on Combinatorial Pattern Matching (CPM). Lecture Notes in Computer Science, vol. 3109. Springer Verlag, Berlin. 420--433.
• 25: Mäkinen, V., and Navarro, G. 2004b. New search algorithms and time/space tradeoffs for succinct suffix arrays. Tech. Rep. C-2004-20, Department of Computer Science, University of Helsinki.
• 26: Veli Mäkinen , Gonzalo Navarro, Succinct suffix arrays based on run-length encoding, Nordic Journal of Computing, v.12 n.1, p.40-66, March 2005
• 27: Mäkinen, V., Navarro, G., and Sadakane, K. 2004. Advantages of backward searching---Efficient secondary memory and distributed implementation of compressed suffix arrays. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 3341. Springer Verlag, Berlin. 681--692.
• 28: 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]
• 29: Giovanni Manzini, An analysis of the Burrows—Wheeler transform, Journal of the ACM (JACM), v.48 n.3, p.407-430, May 2001 [doi>10.1145/382780.382782]
• 30: J. Ian Munro, Tables, Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science, p.37-42, December 18-20, 1996
• 31: J. I. Munro , V. Raman, Succinct representation of balanced parentheses, static trees and planar graphs, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.118, October 19-22, 1997
• 32: Munro, J., Raman, R., Raman, V., and Rao, S. 2003. Succinct representations of permutations. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 2719. Springer Verlag, Berlin. 345--356.
• 33: Gonzalo Navarro, Indexing text using the Ziv-Lempel trie, Journal of Discrete Algorithms, v.2 n.1, p.87-114, March 2004 [doi>10.1016/S1570-8667(03)00066-2]
• 34: Rasmus Pagh, Low Redundancy in Static Dictionaries with O(1) Worst Case Lookup Time, Proceedings of the 26th International Colloquium on Automata, Languages and Programming, p.595-604, July 11-15, 1999
• 35: 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
• 36: 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
• 37: Kunihiko Sadakane, New text indexing functionalities of the compressed suffix arrays, Journal of Algorithms, v.48 n.2, p.294-313, September 2003 [doi>10.1016/S0196-6774(03)00087-7]
• 38: Kunihiko Sadakane , Roberto Grossi, Squeezing succinct data structures into entropy bounds, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1230-1239, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109693]
• 39: Sadakane, K., and Shibuya, T. 2001. Indexing huge genome sequences for solving various problems. Genome Inf. 12, 175--183.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching; Pattern matching

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.3 Information Search and Retrieval
          Subjects: Search process

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Index generation

General Terms:
Algorithms, Theory

Keywords:
Burrows-Wheeler transform, Text indexing, compression boosting, entropy, rank and select, text compression, wavelet tree