A Framework for Succinct Labeled Ordinal Trees over Large Alphabets
Tóm tắt
We consider succinct representations of labeled ordinal trees that support a rich set of operations. Our new representations support a much broader collection of operations than previous work. In our approach, labels of nodes are stored in a preorder label sequence, which can be compressed using any succinct representation of strings that supports
$$\mathtt{{access}}$$
,
$${\mathtt{{rank}}}$$
and
$$\mathtt{{select}}$$
operations. Thus, we present a framework for succinct representations of labeled ordinal trees that is able to handle large alphabets. This answers an open problem presented by Geary et al., which asks for representations of labeled ordinal trees that remain space-efficient for large alphabets. We further extend our work and present the first succinct representations for dynamic labeled ordinal trees that support several label-based operations including finding the level ancestor with a given label.
Tài liệu tham khảo
Barbay, J., Golynski, A., Munro, J.I., Rao, S.S.: Adaptive searching in succinctly encoded binary relations and tree-structured documents. Theor. Comput. Sci. 387(3), 284–297 (2007)
Barbay, J., Rao, S.S.: Succinct encoding for XPath location steps. Technical Report CS-2006-10, University of Waterloo (2006)
Belazzougui, D., Navarro, G.: Optimal lower and upper bounds for representing sequences. ACM Trans. Algorithms (to appear)
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)
Bille, P.: A survey on tree edit distance and related problems. Theor. Comput. Sci. 337(1–3), 217–239 (2005)
Clark, D.R., Munro, J.I.: Efficient suffix trees on secondary storage (extended abstract). In: Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 383–391. Society for Industrial and Applied Mathematics (1996)
Farzan, A., Munro, J.I.: A uniform paradigm to succinctly encode various families of trees. Algorithmica 68(1), 16–40 (2014)
Farzan, A., Raman, R., Rao, S.S.: Universal succinct representations of trees? In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 5555, pp. 451–462. Springer, Berlin (2009)
Ferragina, P., Luccio, F., Manzini, G., Muthukrishnan, S.: Compressing and indexing labeled trees, with applications. J. ACM 57(1), 4 (2009)
Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. Theor. Comput. Sci. 372(1), 115–121 (2007)
Geary, R.F., Raman, R., Raman, V.: Succinct ordinal trees with level-ancestor queries. ACM Trans. Algorithms 2(4), 510–534 (2006)
He, M., Munro, J.I.: Succinct representations of dynamic strings. In: Proceedings of String Processing and Information Retrieval—17th International Symposium. Lecture Notes in Computer Science, vol. 6393, pp. 334–346. Springer, Berlin (2010)
He, M., Munro, J.I., Rao, S.S.: Succinct ordinal trees based on tree covering. ACM Trans. Algorithms 8(4), 42 (2012)
He, M., Munro, J.I., Zhou, G.: Path queries in weighted trees. In: Proceedings of the 22nd International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 7074, pp. 140–149. Springer, Berlin (2011)
He, M., Munro, J.I., Zhou, G.: A framework for succinct labeled ordinal trees over large alphabets. In: Proceedings of the 23rd International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 7676, pp. 537–547. Springer, Berlin (2012)
He, M., Munro, J.I., Zhou, G.: Succinct data structures for path queries. In: Proceedings of the 20th Annual European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 7501, pp. 575–586. Springer, Berlin (2012)
Manzini, G.: An analysis of the burrows-wheeler transform. J. ACM 48(3), 407–430 (2001)
Navarro, G., Nekrich, Y.: Optimal dynamic sequence representations. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 865–876. Society for Industrial and Applied Mathematics (2013)
Navarro, G., Nekrich, Y.: Optimal dynamic sequence representations. CoRR abs/1206.6982 (2013)
Navarro, G., Sadakane, K.: Fully-functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), 16 (2014)
Tsur, D.: Succinct representation of labeled trees. CoRR abs/1312.6039 (2013)
Zhou, G.: Path Queries in Weighted Trees. Master’s thesis, Waterloo, ON, Canada (2012)