Fariña, AntonioGagie, TravisGrabowski, MarcinManzini, GiovanniNavarro, GonzaloOrdóñez, Alberto2025-11-052025-11-052022-03-12A. Fariña, T. Gagie, S. Grabowski, G. Manzini, G. Navarro, and A. Ordóñez, "Efficient and compact representations of some non-canonical prefix-free codes", Theoretical Computer Science, Vol. 907, 12 Mar. 2022, pp. 11-25, https://doi.org/10.1016/j.tcs.2022.01.0101879-2294https://hdl.handle.net/2183/46282©2022 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/. This version of the article has been accepted for publication in Theoretical Computer Science. The Version of Record is available online at https://doi.org/10.1016/j.tcs.2022.01.010 Versión final de: https://doi.org/10.1007/978-3-319-46049-9_5[Abstract]: For many kinds of prefix-free codes there are efficient and compact alterna-tives to the traditional tree-based representation. Since these put the codes into canonical form, however, they can only be used when we can choose the order in which codewords are assigned to symbols. In this paper we first show how, given a probability distribution over an alphabet of σ symbols, we can store an optimal alphabetic prefix-free code in O(σ lg L) bits such that we can encode and decode any codeword of length inO (min(, lg L)) time, where L is the maximum codeword length. With O 2L further bits, for any constant > 0, we can encode and decode O(lg ) time. We then show how to store a nearly optimal alphabetic prefix-free code in o(σ) bits such that we can encode and decode in constant time. We also consider a kind of optimal prefix-free code introduced recently where the codewords’ lengths are non-decreasing if arranged in lexicographic order of their reverses. We reduce their storage space to O(σ lg L) while maintaining encoding and de-coding times in O(). We also show how, with O 2L further bits, we can encode and decode in constant time. All of our results hold in the word-RAM model.engAttribution-NonCommercial-NoDerivatives 4.0 Internationalhttp://creativecommons.org/licenses/by-nc-nd/4.0/Compact data structuresPrefix-free codesAlphabetic codesavelet matrixEfficient and compact representations of some non-canonical prefix-free codesjournal articleopen access10.1016/j.tcs.2022.01.010