When indexing equals compression: Experiments with compressing suffix arrays and applications

ABSTRACT

We report on a new experimental analysis of high-order entropy-compressed suffix arrays, which retains the theoretical performance of previous work and represents an improvement in practice. Our experiments indicate that the resulting text index offers state-of-the-art compression. In particular, we require roughly 20% of the original text size---without requiring a separate instance of the text. We can additionally use a simple notion to encode and decode block-sorting transforms (such as the Burrows--Wheeler transform), achieving a compression ratio comparable to that of bzip2. We also provide a compressed representation of suffix trees (and their associated text) in a total space that is comparable to that of the text alone compressed with gzip.

REFERENCES

• 1: Mohamed Ibrahim Abouelhoda , Stefan Kurtz , Enno Ohlebusch, Replacing suffix trees with enhanced suffix arrays, Journal of Discrete Algorithms, v.2 n.1, p.53-86, March 2004 [doi>10.1016/S1570-8667(03)00065-0]
• 2: Hiroki Arimura , Hiroki Asaka , Hiroshi Sakamoto , Setsuo Arikawa, Efficient Discovery of Proximity Patterns with Suffix Arrays, Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, p.152-156, July 01-04, 2001
• 3: Michael A. Bender , Martín Farach-Colton, The level ancestor problem simplified, Theoretical Computer Science, v.321 n.1, p.5-12, June 16, 2004 [doi>10.1016/j.tcs.2003.05.002]
• 4: Jon Louis Bentley , Daniel D. Sleator , Robert E. Tarjan , Victor K. Wei, A locally adaptive data compression scheme, Communications of the ACM, v.29 n.4, p.320-330, April 1986 [doi>10.1145/5684.5688]
• 5: Andrej Brodnik , J. Ian Munro, Membership in Constant Time and Almost-Minimum Space, SIAM Journal on Computing, v.28 n.5, p.1627-1640, April/May 1999 [doi>10.1137/S0097539795294165]
• 6: The Canterbury Corpus. 2001. http://corpus.canterbury.ac.nz.
• 7: Chazelle, B., and Guibas, L. J. 1986. Fractional cascading: I. A data structuring technique. Algorithmica 1, 2, 133--162.
• 8: Sebastian Deorowicz, Second step algorithms in the Burrows-Wheeler compression algorithm, Software—Practice & Experience, v.32 n.2, p.99-111, February 2002 [doi>10.1002/spe.426]
• 9: Fenwick, P. 1996. Punctured elias codes for variable-length coding of the integers. The University of Auckland, NZ. TR 137. ISSN 1173--3500.
• 10: Peter Fenwick, Burrows--Wheeler compression with variable length integer codes, Software—Practice & Experience, v.32 n.13, p.1307-1316, 10 November 2002 [doi>10.1002/spe.484]
• 11: 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]
• 12: 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
• 13: 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]
• 14: Luca Foschini , Roberto Grossiy , Ankur Guptaz , Jeffrey Scott Vitter, Fast Compression with a Static Model in High-Order Entropy, Proceedings of the Conference on Data Compression, p.62, March 23-25, 2004
• 15: 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
• 16: 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
• 17: 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
• 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: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 20: Hon, W., Lam, T., Tse, W., Wong, C., and Yiu, S. 2004. Practical aspects of compressed suffix arrays and fm-index in searching dna sequences. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX).
• 21: Wing-Kai Hon , Kunihiko Sadakane , Wing-Kin Sung, Breaking a Time-and-Space Barrier in Constructing Full-Text Indices, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.251, October 11-14, 2003
• 22: P. Howard, Interleaving Entropy Codes, Proceedings of the Compression and Complexity of Sequences 1997, p.45, June 11-13, 1997
• 23: Jacobson, G. 1989. Space-efficient static trees and graphs. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, pp. 549--554.
• 24: Toru Kasai , Gunho Lee , Hiroki Arimura , Setsuo Arikawa , Kunsoo Park, Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications, Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, p.181-192, July 01-04, 2001
• 25: Stefan Kurtz, Reducing the space requirement of suffix trees, Software—Practice & Experience, v.29 n.13, p.1149-1171, Nov. 1999 [doi>10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O]
• 26: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 27: 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]
• 28: 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]
• 29: Alistair Moffat , Radford M. Neal , Ian H. Witten, Arithmetic coding revisited, ACM Transactions on Information Systems (TOIS), v.16 n.3, p.256-294, July 1998 [doi>10.1145/290159.290162]
• 30: 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]
• 31: J. Ian Munro, Space efficient suffix trees, Journal of Algorithms, v.39 n.2, p.205-222, May 2001 [doi>10.1006/jagm.2000.1151]
• 32: Navarro, G., and Mäkinen, V. 2006. Compressed full-text indexes. Tech. Rep. TR/DCC-2006-6, University of Chile.
• 33: Nelson, M. 2003. Run length encoding/RLE. http://www.datacompression.info/RLE.shtml.
• 34: Oki, M. 2003. http://www.infor.kanazawa-it.ac.jp/~ishii/lhaunix/.
• 35: Rasmus Pagh, Low Redundancy in Static Dictionaries with Constant Query Time, SIAM Journal on Computing, v.31 n.2, p.353-363, 2001 [doi>10.1137/S0097539700369909]
• 36: 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
• 37: S. Srinivasa Rao, Time-space trade-offs for compressed suffix arrays, Information Processing Letters, v.82 n.6, p.307-311, June 30, 2002 [doi>10.1016/S0020-0190(01)00298-8]
• 38: Rissanen, J., and Langdon, G. G. 1979. Arithmetic coding. IBM J. Res. Devel. 23, 2 (Mar.), 149--162.
• 39: 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
• 40: 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]
• 41: Schindler, M. 1999. http://www.compressconsult.com/rangecoder.
• 42: Smith, J. O., III. 2003. http://ccrma-www.stanford.edu/~jos/mdft/Autocorrelation.html.
• 43: TREC. Tipster 3. 2000. http://trec.nist.gov/data/docs_eng.html.
• 44: Anthony Ian Wirth , Alistair Moffat, Can We Do without Ranks in Burrows Wheeler Transform Compression?, Proceedings of the Data Compression Conference (DCC '01), p.419, March 27-29, 2001
• 45: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression
  E.5 FILES
      Subjects: Sorting/searching

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.3 Index Generation**

General Terms:
Algorithms, Design, Experimentation, Theory

Keywords:
Burrows--Wheeler Transform, Entropy, suffix array, text indexing