Abstract | ||
---|---|---|
A skeleton Huffman tree is a Huffman tree from which all complete subtrees of depth h >= 1 have been pruned. Skeleton Huffman trees are used to save storage and enhance processing time in several applications such as decoding, compressed pattern matching and Wavelet trees for random access. However, the straightforward way of basing the construction of a skeleton tree on a canonical Huffman tree does not necessarily yield the least number of nodes. The notion of optimal skeleton trees is introduced, and an algorithm for achieving such trees is investigated. The resulting more compact trees can be used to further enhance the time and space complexities of the corresponding algorithms. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1007/978-3-319-67428-5_21 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Compressed pattern matching,Combinatorics,Computer science,Algorithm,Huffman coding,Decoding methods,Skeleton (computer programming),Wavelet,Random access | Conference | 10508 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Shmuel T. Klein | 1 | 434 | 77.80 |
Tamar C. Serebro | 2 | 0 | 0.68 |
Dana Shapira | 3 | 144 | 32.15 |