Entropic Bounds on the Average Length of Codes with a Space
<|reference_start|>Entropic Bounds on the Average Length of Codes with a Space: We consider the problem of constructing prefix-free codes in which a designated symbol, a space, can only appear at the end of codewords. We provide a linear-time algorithm to construct almost-optimal codes with this property, meaning that their average length differs from the minimum possible by at most one. We obtain our results by uncovering a relation between our class of codes and the class of one-to-one codes. Additionally, we derive upper and lower bounds to the average length of optimal prefix-free codes with a space in terms of the source entropy.<|reference_end|>
@article{bruno2024entropic,
    title={Entropic Bounds on the Average Length of Codes with a Space},
    author={Roberto Bruno, Ugo Vaccaro},
    journal={Entropy 2024, 26(4), 283;},
    year={2024},
    doi={10.3390/e26040283},
    archivePrefix={arXiv},
    eprint={2405.06379},
    primaryClass={cs.IT math.IT}
}