I think that your proposed encoding is basically based on LOUDS (level order unary degree sequence) built on full binary trees, leveraging the fact that the leaves can be omitted since each internal node has always two children. I therefore wonder whether using compressed bit vectors like RRR built upon a LOUDS representation (omitting the leaves) would achieve even better compression ratios.
[1] Qi Cheng,
"Compressing the Tree of Canonical Huffman Coding",
IEEE Signal Processing Society SigPort,
2022. [Online]. Available: https://sigport.org/documents/compressing-tree-canonical-huffman-coding. Accessed: Nov. 25, 2024.
@misc{6182-22,
url = {https://sigport.org/documents/compressing-tree-canonical-huffman-coding},
author = {Qi Cheng },
publisher = {IEEE Signal Processing Society SigPort},
title = {Compressing the Tree of Canonical Huffman Coding},
year = {2022}
}
TY - DATA
T1 - Compressing the Tree of Canonical Huffman Coding
AU - Qi Cheng
PY - 2022
PB - IEEE Signal Processing Society SigPort
UR - https://sigport.org/documents/compressing-tree-canonical-huffman-coding
ER -
Qi Cheng.
(2022).
Compressing the Tree of Canonical Huffman Coding.
IEEE Signal Processing Society SigPort.
https://sigport.org/documents/compressing-tree-canonical-huffman-coding
Qi Cheng,
2022.
Compressing the Tree of Canonical Huffman Coding.
Available at:
https://sigport.org/documents/compressing-tree-canonical-huffman-coding.
1. Qi Cheng.
Compressing the Tree of Canonical Huffman Coding [Internet].
IEEE Signal Processing Society SigPort; 2022.
Available from :
https://sigport.org/documents/compressing-tree-canonical-huffman-coding
Comments
Using compressed bit vectors
I think that your proposed encoding is basically based on LOUDS (level order unary degree sequence) built on full binary trees, leveraging the fact that the leaves can be omitted since each internal node has always two children. I therefore wonder whether using compressed bit vectors like RRR built upon a LOUDS representation (omitting the leaves) would achieve even better compression ratios.