Encoding Trees: A Method for Producing a Variable-Length Prefix Code From Sets of Arbitrary Size
Abstract
In this work we formalize a new class of binary trees called encoding trees. We extend this structure in two ways, through labelling to create the class of labelled encoding trees, and pruning to create the class of pruned encoding trees. We discuss how these two extensions can be combined to create the the class of pruned labelled encoding trees. Using the supplementary results that we prove about these classes of trees, we construct a code that uses pruned labelled encoding trees to convert a string of symbols from a sequence of non-empty sets to a binary string. We prove that this code is a variable-length prefix code that can process any valid string of symbols from the given sequence of non-empty sets. Furthermore, we construct a code from the class of pruned labelled encoding trees that goes in the opposite direction, from binary strings to a string of symbols from a sequence of non-empty sets of arbitrary symbols. We prove that this code is also a variable-length prefix code that can process any binary string of any length, provided that the sequence of non-empty sets is sufficiently long. We provide an equation that establishes the minimum sequence length to encode any binary string of a given length, based on that length.
Related
- Length Bounds for MDS Algebraic Geometry Codes of Arbitrary Positive Genus
- Exponential Growth of Mean Multiplicities in Length Spectra of Semi-Arithmetic Surfaces of Arbitrary Arithmetic Dimension
- Blow-up at arbitrary energy levels for a strongly damped viscoelastic wave equation with a variable-exponent logarithmic source
- Detection of spiking motifs of arbitrary length in neural activity using bounded synaptic delays
- Collision Positivity for Symmetric Orbit-Sum Inequalities in Arbitrary Dimension: A Complete Two-Variable Criterion
BibTeX
@misc{laporte2026encoding,
title = {{Encoding Trees: A Method for Producing a Variable-Length Prefix Code From Sets of Arbitrary Size}},
author = {Bryony H. Laporte and Karen Rudie},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29032},
eprint = {2610.29032},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29032},
}
RIS
TY - UNPB
TI - Encoding Trees: A Method for Producing a Variable-Length Prefix Code From Sets of Arbitrary Size
AU - Bryony H. Laporte
AU - Karen Rudie
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29032
UR - https://arxiv.org/abs/2610.29032
AB - In this work we formalize a new class of binary trees called encoding trees. We extend this structure in two ways, through labelling to create the class of labelled encoding trees, and pruning to create the class of pruned encoding trees. We discuss how these two extensions can be combined to create the the class of pruned labelled encoding trees. Using the supplementary results that we prove about these classes of trees, we construct a code that uses pruned labelled encoding trees to convert a string of symbols from a sequence of non-empty sets to a binary string. We prove that this code is a variable-length prefix code that can process any valid string of symbols from the given sequence of non-empty sets. Furthermore, we construct a code from the class of pruned labelled encoding trees that goes in the opposite direction, from binary strings to a string of symbols from a sequence of non-empty sets of arbitrary symbols. We prove that this code is also a variable-length prefix code that can process any binary string of any length, provided that the sequence of non-empty sets is sufficiently long. We provide an equation that establishes the minimum sequence length to encode any binary string of a given length, based on that length.
ER -