论文标题
最佳骨架霍夫曼树重新审视
Optimal Skeleton Huffman Trees Revisited
论文作者
论文摘要
骨骼霍夫曼树是一棵霍夫曼树，其中所有脱节最大的完美子树都缩小到叶子中。除了节省存储空间外，骨骼霍夫曼树也用于更快的解码和加速霍夫曼形小波树。 2017年，克莱因（Klein）等人。引入了最佳骨架树：对于给定的符号频率，它在所有最佳的无前缀代码树（不一定是霍夫曼）中具有最少的节点。 Klein等。描述了一种简单的算法，该算法对于固定编码长的长度，它找到了一个骨骼树，其节点数量最少。使用此算法，可以处理每组最佳代码字长度以找到最佳骨架树。但是，在最坏的情况下，有很多这样的集合。我们描述了一个$ O（n^2 \ log n）$ - 时间算法，在给定$ n $符号频率的情况下，构造了最佳骨架树及其相应的最佳代码。
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 $O(n^2\log n)$-time algorithm that, given $n$ symbol frequencies, constructs an optimal skeleton tree and its corresponding optimal code.
