Abstract
A skeleton Huffman tree is a Huffman tree in which all disjoint maximal perfect subtrees are shrunk into leaves. Skeleton Huffman trees, besides saving storage space, are also used for faster decoding and for speeding up Huffman-shaped wavelet trees. In 2017 Klein et al. introduced an optimal skeleton tree: for given symbol frequencies, it has the least number of nodes among all optimal prefix-free code trees (not necessarily Huffman’s) with shrunk perfect subtrees. Klein et al. described a simple algorithm that, for fixed codeword lengths, finds a skeleton tree with the least number of nodes; with this algorithm one can process each set of optimal codeword lengths to find an optimal skeleton tree. However, there are exponentially many such sets in the worst case. We describe an \(\mathcal {O}(n^2\log n)\)-time algorithm that, given n symbol frequencies, constructs an optimal skeleton tree and its corresponding optimal code.
Supported by the Russian Science Foundation (RSF), project 18-71-00002.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
If not supported, it can be implemented using a precomputed table of size \(\mathcal {O}(n)\) [6].
References
Abrahams, J.: Code and parse trees for lossless source encoding. In: Proceedings of the Compression and Complexity of Sequences, pp. 145–171. IEEE (1997). https://doi.org/10.1109/SEQUEN.1997.666911
Baruch, G., Klein, S.T., Shapira, D.: A space efficient direct access data structure. J. Discrete Algorithms 43, 26–37 (2017). https://doi.org/10.1016/j.jda.2016.12.001
Duda, J.: Asymmetric numeral systems. arXiv preprint arXiv:0902.0271 (2009)
Ferguson, T.J., Rabinowitz, J.H.: Self-synchronizing Huffman codes. IEEE Trans. Inf. Theory 30(4), 687–693 (1984). https://doi.org/10.1109/TIT.1984.1056931
Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 390–398. IEEE (2000). https://doi.org/10.1109/SFCS.2000.892127
Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47(3), 424–436 (1993). https://doi.org/10.1016/0022-0000(93)90040-4
Gallager, R.G.: Variations on a theme by Huffman. IEEE Trans. Inf. Theory 24(6), 168–174 (1978). https://doi.org/10.1109/TIT.1978.1055959
Golomb, S.W.: Sources which maximize the choice of a Huffman coding tree. Inf. Control 45(3), 263–272 (1980). https://doi.org/10.1016/S0019-9958(80)90648-8
Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 841–850. SIAM (2003)
Huffman, D.A.: A method for the construction of minimum-redundancy codes. Proc. Inst. Radio Eng. (IRE) 40(9), 1098–1101 (1952). https://doi.org/10.1109/JRPROC.1952.273898
Klein, S.T.: Skeleton trees for the efficient decoding of Huffman encoded texts. Inf. Retrieval 3(1), 7–23 (2000). https://doi.org/10.1023/A:1009910017828
Klein, S.T., Serebro, T.C., Shapira, D.: Optimal skeleton Huffman trees. In: Fici, G., Sciortino, M., Venturini, R. (eds.) SPIRE 2017. LNCS, vol. 10508, pp. 241–253. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-67428-5_21
Kraft, L.G.: A device for quantizing, grouping, and coding amplitude modulated pulses. Master’s thesis, MIT, Cambridge, Massachusetts (1949)
van Leeuwen, J.: On the construction of Huffman trees. In: Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), pp. 382–410. Edinburgh University Press (1976)
Mäkinen, V., Navarro, G.: New search algorithms and time/space tradeoffs for succinct suffix arrays. Technical report C-2004-20, University of Helsinki, Finland, April 2004
Moffat, A.: Huffman coding. ACM Comput. Surv. 52(4), 1–35 (2019). https://doi.org/10.1145/3342555
Shapira, D., Daptardar, A.: Adapting the Knuth-Morris-Pratt algorithm for pattern matching in Huffman encoded texts. Inf. Process. Manag. 42(2), 429–439 (2006). https://doi.org/10.1016/j.ipm.2005.02.003
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Kosolobov, D., Merkurev, O. (2020). Optimal Skeleton Huffman Trees Revisited. In: Fernau, H. (eds) Computer Science – Theory and Applications. CSR 2020. Lecture Notes in Computer Science(), vol 12159. Springer, Cham. https://doi.org/10.1007/978-3-030-50026-9_20
Download citation
DOI: https://doi.org/10.1007/978-3-030-50026-9_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-50025-2
Online ISBN: 978-3-030-50026-9
eBook Packages: Computer ScienceComputer Science (R0)