×

zbMATH — the first resource for mathematics

Ultra-succinct representation of ordered trees with applications. (English) Zbl 1242.68083
Summary: There exist two well-known succinct representations of ordered trees: BP (balanced parenthesis, [J. I. Munro and V. Raman, SIAM J. Comput. 31(2001), No. 3, 762–776 (2002; Zbl 1017.68037)]) and DFUDS (depth first unary degree sequence, [D. Benoit et al., Algorithmica 43, No. 4, 275–292 (2005; Zbl 1086.68034)]). Both have size \(2n+o(n)\) bits for \(n\)-node trees, which asymptotically matches the information-theoretic lower bound. Importantly, many fundamental operations on trees can be done in constant time on the word RAM when using BP or DFUDS, for example finding the parent, the first child, the next sibling, the number of descendants, etc.
Although the space needed to store the BP or DFUDS representation of an ordered tree matches the lower bound, this is not optimal when we consider encodings for certain special classes of trees such as trees in which every internal node has exactly two children. In this paper, we introduce a new, conditional entropy for trees called the tree degree entropy, and give a succinct tree representation with matching size. We call such a representation an ultra-succinct data structure. We show how to modify the DFUDS representation to obtain a “compressed DFUDS”, and as a consequence, a tree in which every internal node has exactly two children can be represented in \(n+o(n)\) bits. We also describe applications of the compressed DFUDS representation to ultra-succinct compressed suffix trees and labeled trees.

MSC:
68P05 Data structures
05C05 Trees
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
Software:
PATRICIA
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Benoit, D.; Demaine, E.D.; Munro, J.I.; Raman, R.; Raman, V.; Rao, S.S., Representing trees of higher degree, Algorithmica, 43, 4, 275-292, (2005) · Zbl 1086.68034
[2] Chiang, Y.-T.; Lin, C.-C.; Lu, H.-I., Orderly spanning trees with applications, SIAM J. comput., 34, 4, 924-945, (2005) · Zbl 1069.05054
[3] Farzan, A.; Munro, J.I., A uniform approach towards succinct representation of trees, (), 173-184 · Zbl 1155.68373
[4] Farzan, A.; Raman, R.; Rao, S.S., Universal succinct representations of trees?, (), 451-462 · Zbl 1248.68168
[5] Ferragina, P.; Luccio, F.; Manzini, G.; Muthukrishnan, S., Compressing and indexing labeled trees, with applications, J. ACM, 57, 1, 4, (2009), 1-4:33 · Zbl 1326.68132
[6] Ferragina, P.; Manzini, G., Indexing compressed texts, J. ACM, 52, 4, 552-581, (2005) · Zbl 1323.68261
[7] Ferragina, P.; Venturini, R., A simple storage scheme for strings achieving entropy bounds, Theoret. comput. sci., 372, 1, 115-121, (2007) · Zbl 1110.68029
[8] Geary, R.F.; Rahman, N.; Raman, R.; Raman, V., A simple optimal representation for balanced parentheses, Theoret. comput. sci., 368, 231-246, (December 2006)
[9] Geary, R.F.; Raman, R.; Raman, V., Succinct ordinal trees with level-ancestor queries, ACM trans. algorithms, 2, 510-534, (October 2006)
[10] R. Grossi, A. Gupta, J. S. Vitter, High-order entropy-compressed text indexes, in: Proc. ACM-SIAM SODA, 2003, pp. 841-850. · Zbl 1092.68584
[11] Grossi, R.; Vitter, J.S., Compressed suffix arrays and suffix trees with applications to text indexing and string matching, SIAM J. comput., 35, 2, 378-407, (2005) · Zbl 1092.68115
[12] Gusfield, D., Algorithms on strings, trees, and sequences, (1997), Cambridge University Press · Zbl 0934.68103
[13] Hon, W.K.; Sadakane, K.; Sung, W.K., Succinct data structures for searchable partial sums, (), 505-516 · Zbl 1205.68129
[14] G. Jacobson, Space-efficient static trees and graphs, in: Proc. IEEE FOCS, 1989, pp. 549-554.
[15] J. Jansson, K. Sadakane, W.-K. Sung, Ultra-succinct representation of ordered trees, in: Proc. ACM-SIAM SODA, 2007, pp. 575-584. · Zbl 1302.68100
[16] Lu, H.-I.; Yeh, C.-C., Balanced parentheses strike back, ACM trans. algor. (TALG), 4, 3, (2008), Article No. 28
[17] McCreight, E.M., A space-economical suffix tree construction algorithm, J. ACM, 23, 12, 262-272, (1976) · Zbl 0329.68042
[18] Morrison, D.R., Patricia - practical algorithm to retrieve information coded in alphanumeric, J. ACM, 15, 4, 514-534, (1968)
[19] Munro, J.I., Tables, (), 37-42
[20] Munro, J.I.; Raman, V., Succinct representation of balanced parentheses and static trees, SIAM J. comput., 31, 3, 762-776, (2001) · Zbl 1017.68037
[21] Munro, J.I.; Raman, V.; Rao, S.S., Space efficient suffix trees, J. algorithms, 39, 2, 205-222, (May 2001)
[22] Munro, J.I.; Rao, S.S., Succinct representations of functions, (), 1006-1015 · Zbl 1099.68603
[23] Pagh, R., Low redundancy in static dictionaries with constant query time, SIAM J. comput., 31, 2, 353-363, (2001) · Zbl 0994.68050
[24] Poon, C.K.; Yiu, W.K., Opportunistic data structures for range queries, (), 560-569 · Zbl 1128.68348
[25] R. Raman, V. Raman, S. S. Rao, Succinct indexable dictionaries with applications to encoding k-ary trees and multisets, in: Proc. ACM-SIAM SODA, 2002, pp. 233-242. · Zbl 1093.68582
[26] Srinivasa Rao, S., Time-space trade-offs for compressed suffix arrays, Inform. process. lett., 82, 6, 307-311, (2002) · Zbl 1051.68048
[27] Rote, G., Binary trees having a given number of nodes with 0, 1, and 2 children, Sem. lothar. combin., 38, (1996), B38b, 6 pp. · Zbl 0886.05081
[28] Sadakane, K., New text indexing functionalities of the compressed suffix arrays, J. algorithms, 48, 2, 294-313, (2003) · Zbl 1100.68563
[29] Sadakane, K., Compressed suffix trees with full functionality, Theory comput. syst., 41, 4, 589-607, (2007) · Zbl 1148.68015
[30] K. Sadakane, R. Grossi, Squeezing succinct data structures into entropy bounds, in: Proc. ACM-SIAM SODA, 2006, pp. 1230-1239. · Zbl 1192.68188
[31] K. Sadakane, G. Navarro, Fully-functional succinct trees, in: Proc. ACM-SIAM SODA, January 2010, pp. 134-149. · Zbl 1288.05046
[32] Välimäki, N.; Mäkinen, V.; Gerlach, W.; Dixit, K., Engineering a compressed suffix tree implementation, J. exp. algorithmics (JEA), 14:2:4.2-2:4.23, (January 2010)
[33] P. Weiner, Linear pattern matching algorithms, in: Proceedings of the 14th IEEE Symposium on Switching and Automata Theory, 1973, pp. 1-11.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.