Squeezing succinct data structures into entropy bounds

ABSTRACT

Consider a sequence S of n symbols drawn from an alphabet A = {1, 2,. . .,σ}, stored as a binary string of nlog σ bits. A succinct data structure on S supports a given set of primitive operations on S using just f (n) = o(n log σ) extra bits. We present a technique for transforming succinct data structures (which do not change the binary content of S) into compressed data structures using nHk + f(n) + O(n log σ + log logσ n + k)/ logσ n) bits of space, where Hk ≤ log σ is the kth-order empirical entropy of S. When k + log σ = o(log n), we improve the space complexity of the succinct data structure from n log σ + o(n log σ) to n Hk + o(nlog σ) bits by keeping S in compressed format, so that any substring of O(log σ n) symbols in S (i.e. O(log n) bits) can be decoded on the fly in constant time. Thus, the time complexity of the supported operations does not change asymptotically. Namely, if an operation takes t(n) time in the succinct data structure, it requires O(t(n)) time in the resulting compressed data structure. Using this simple approach we improve the space complexity of some of the best known results on succinct data structures We extend our results to handle another definition of entropy.

REFERENCES

• 1: Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.295-304, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301323]
• 2: 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]
• 3: David Benoit , Erik D. Demaine , J. Ian Munro , Venkatesh Raman, Representing Trees of Higer Degree, Proceedings of the 6th International Workshop on Algorithms and Data Structures, p.169-180, August 11-14, 1999
• 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: Daniel K. Blandford , Guy E. Blelloch, Compact representations of ordered sets, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 6: Daniel K. Blandford , Guy E. Blelloch , Ian A. Kash, Compact representations of separable graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 7: 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]
• 8: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 9: Peter Elias, Interval and recency rank source coding: two on-line adaptive variable-length schemes, IEEE Transactions on Information Theory, v.33 n.1, p.3-10, January 2, 1987 [doi>10.1109/TIT.1987.1057251]
• 10: P. Ferragina, G. Manzini, V. Mäkinen, and G. Navarro. Succinct Representation of Sequences. Tr/dcc-2004-5, August 2004. ftp://ftp.dcc.uchile.cl/pub/users/gnavarro/sequences.ps.gz.
• 11: Paolo Ferragina and Giovanni Manzini. On compressing and indexing data. Journal of the ACM, 2005.
• 12: 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]
• 13: Anna Gál and Peter Bro Miltersen. The cell probe complexity of succinct data structures. In Proc. ICALP, em LNCS 2719, pp. 332--344, 2003.
• 14: R. F. Geary, N. Rahman, R. Raman, and V. Raman. A simple optimal representation for balanced parentheses. In Proc. CPM, LNCS 3109, pp. 159--172, 2004.
• 15: Richard F. Geary , Rajeev Raman , Venkatesh Raman, Succinct ordinal trees with level-ancestor queries, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 16: 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]
• 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 , 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
• 19: 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]
• 20: A. Gupta, W.-K. Hon, R. Shah, and J. S. Vitter. Compressed Data Structures: Dictionaries and Data-Aware Measures. Manuscript, 2005.
• 21: G. Jacobson. Space-efficient static trees and graphs. In Proc. IEEE FOCS, pp. 549--554, 1989.
• 22: S. Rao Kosaraju , Giovanni Manzini, Compression of Low Entropy Strings with Lempel--Ziv Algorithms, SIAM Journal on Computing, v.29 n.3, p.893-911, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539797331105]
• 23: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 24: Peter Bro Miltersen, Lower bounds on the size of selection and rank indexes, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 25: 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
• 26: 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]
• 27: 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]
• 28: J. Ian Munro, Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Succinct representations of permutations. In Proc. ICALP, LNCS 2719, pp. 345--356, 2003.
• 29: 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]
• 30: J. Ian Munro , Venkatesh Raman , Adam J. Storm, Representing dynamic binary trees succinctly, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.529-536, January 07-09, 2001, Washington, D.C., United States
• 31: J. Ian Munro and S. Srinivasa Rao. Succinct representations of functions. In Proc. ICALP, LNCS 3142, pp. 1006--1015, 2004.
• 32: 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]
• 33: C. K. Poon and W. K. Yiu. Opportunistic Data Structures for Range Queries. In Proc. COCOON, LNCS 3595, pp. 560--569, 2005.
• 34: 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
• 35: Rajeev Raman and S. Srinivasa Rao. Succinct dynamic dictionaries and trees. In Proc. ICALP, LNCS 2719, pp. 357--368, 2003.
• 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: J. Ziv and A. Lempel. Compression of individual sequences via variable-rate coding. IEEE Trans. Inform. Theory, IT-24(5):530--536, September 1978.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory