TY - GEN
T1 - Optimal skeleton Huffman trees
AU - Klein, Shmuel T.
AU - Serebro, Tamar C.
AU - Shapira, Dana
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85030169470&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-67428-5_21
DO - 10.1007/978-3-319-67428-5_21
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
AN - SCOPUS:85030169470
SN - 9783319674278
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 241
EP - 253
BT - String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Proceedings
A2 - Venturini, Rossano
A2 - Fici, Gabriele
A2 - Sciortino, Marinella
T2 - 24th International Symposium on String Processing and Information Retrieval, SPIRE 2017
Y2 - 26 September 2017 through 29 September 2017
ER -