Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/101496
Title: Optimal skeleton huffman trees revisited
Authors: Kosolobov, D.
Merkurev, O.
Issue Date: 2020
Publisher: Springer
Citation: Kosolobov D. Optimal skeleton huffman trees revisited / D. Kosolobov, O. Merkurev. — DOI 10.1007/978-3-030-50026-9_20 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2020. — Vol. 12159 LNCS. — P. 276-288.
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 (formula presented)-time algorithm that, given n symbol frequencies, constructs an optimal skeleton tree and its corresponding optimal code. © Springer Nature Switzerland AG 2020.
Keywords: DYNAMIC PROGRAMMING
HUFFMAN TREE
SKELETON TREE
CODES (SYMBOLS)
FORESTRY
MUSCULOSKELETAL SYSTEM
OPTIMAL SYSTEMS
CODEWORD LENGTH
HUFFMAN TREES
OPTIMAL CODES
PREFIX-FREE CODES
SIMPLE ALGORITHM
SKELETON TREE
STORAGE SPACES
TIME ALGORITHMS
TREES (MATHEMATICS)
URI: http://hdl.handle.net/10995/101496
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85087272570
PURE ID: 13387441
b6978e04-022c-4e95-be53-0f58d4fddda8
ISSN: 3029743
ISBN: 9783030500252
DOI: 10.1007/978-3-030-50026-9_20
metadata.dc.description.sponsorship: Supported by the Russian Science Foundation (RSF), project 18-71-00002.
RSCF project card: 18-71-00002
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85087272570.pdf202,52 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.