{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T05:46:17Z","timestamp":1774590377325,"version":"3.50.1"},"reference-count":47,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2019,12,31]],"date-time":"2019-12-31T00:00:00Z","timestamp":1577750400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We describe an algorithm computing an optimal prefix free code for n unsorted positive weights in time within     O ( n ( 1 + lg \u03b1 ) ) \u2286 O ( n lg n )    , where the alternation     \u03b1 \u2208 [ 1 . . n \u2212 1 ]     approximates the minimal amount of sorting required by the computation. This asymptotical complexity is within a constant factor of the optimal in the algebraic decision tree computational model, in the worst case over all instances of size n and alternation    \u03b1   . Such results refine the state of the art complexity of     \u0398 ( n lg n )     in the worst case over instances of size n in the same computational model, a landmark in compression and coding since 1952. Beside the new analysis technique, such improvement is obtained by combining a new algorithm, inspired by van Leeuwen\u2019s algorithm to compute optimal prefix free codes from sorted weights (known since 1976), with a relatively minor extension of Karp et al.\u2019s deferred data structure to partially sort a multiset accordingly to the queries performed on it (known since 1988). Preliminary experimental results on text compression by words show    \u03b1    to be polynomially smaller than n, which suggests improvements by at most a constant multiplicative factor in the running time for such applications.<\/jats:p>","DOI":"10.3390\/a13010012","type":"journal-article","created":{"date-parts":[[2020,1,3]],"date-time":"2020-01-03T03:28:53Z","timestamp":1578022133000},"page":"12","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Optimal Prefix Free Codes with Partial Sorting"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3392-8353","authenticated-orcid":false,"given":"J\u00e9r\u00e9my","family":"Barbay","sequence":"first","affiliation":[{"name":"Departamento de Ciencias de la Computaci\u00f3n, Universidad de Chile, 8370448 Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,12,31]]},"reference":[{"key":"ref_1","first-page":"1098","article-title":"A Method for the Construction of Minimum-Redundancy Codes","volume":"40","author":"Huffman","year":"1952","journal-title":"Proc. Inst. Radio Eng. (IRE)"},{"key":"ref_2","unstructured":"Chen, C., Pai, Y., and Ruan, S. (2006, January 9\u201311). Low power Huffman coding for high performance data transmission. Proceedings of the International Conference on Hybrid Information Technology ICHIT, Cheju Island, Korea."},{"key":"ref_3","first-page":"85:1","article-title":"Huffman Coding","volume":"52","author":"Moffat","year":"2019","journal-title":"ACM Comput. Surv."},{"key":"ref_4","unstructured":"Chandrasekaran, M.N. (2010). Discrete Mathematics, PHI Learning Pvt. Ltd."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1200","DOI":"10.1109\/26.634683","article-title":"On the implementation of minimum redundancy prefix codes","volume":"45","author":"Moffat","year":"1997","journal-title":"ACM Trans. Commun. TCOM"},{"key":"ref_6","unstructured":"Wikipedia (2019, December 20). bzip2. Available online: https:\/\/en.wikipedia.org\/wiki\/Bzip2."},{"key":"ref_7","unstructured":"Wikipedia (2019, December 20). JPEG. Available online: https:\/\/en.wikipedia.org\/wiki\/JPEG#Entropy_coding."},{"key":"ref_8","first-page":"227","article-title":"Entropy as Computational Complexity","volume":"18","author":"Takaoka","year":"2010","journal-title":"J. Inf. Process. JIP"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Kr\u00e1lovi\u010d, R., and Niwi\u0144ski, D. (2009, January 24\u201328). Partial Solution and Entropy. Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science 2009 (MFCS 2009), Novy Smokovec, High Tatras, Slovakia.","DOI":"10.1007\/978-3-642-03816-7"},{"key":"ref_10","unstructured":"Takaoka, T. (2016, August 23). Minimal Mergesort. Technical Report, University of Canterbury. Available online: http:\/\/ir.canterbury.ac.nz\/handle\/10092\/9676."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/j.tcs.2013.10.019","article-title":"On Compressing Permutations and Adaptive Sorting","volume":"513","author":"Barbay","year":"2013","journal-title":"Theor. Comput. Sci. TCS"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Even, S., and Even, G. (2012). Graph Algorithms, Cambridge University Press. [2nd ed.].","DOI":"10.1017\/CBO9781139015165"},{"key":"ref_13","unstructured":"Aho, A.V., Hopcroft, J.E., and Ullman, J. (1983). Data Structures and Algorithms, Addison-Wesley Longman Publishing Company."},{"key":"ref_14","unstructured":"Van Leeuwen, J. (1976, January 20\u201323). On the construction of Huffman trees. Proceedings of the International Colloquium on Automata, Languages and Programming ICALP, Edinburgh, UK."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1650","DOI":"10.1109\/18.681345","article-title":"Efficient Construction of Minimum-Redundancy Codes for Large Alphabets","volume":"44","author":"Moffat","year":"1998","journal-title":"IEEE Trans. Inf. Theory TIT"},{"key":"ref_16","first-page":"92","article-title":"Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes","volume":"Volume 3884","author":"Durand","year":"2006","journal-title":"Proceedings of the International Symposium on Theoretical Aspects of Computer Science STACS"},{"key":"ref_17","unstructured":"Belal, A.A., and Elmasry, A. (2010). Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes. arXiv, Available online: https:\/\/arxiv.org\/pdf\/cs\/0509015.pdf."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1007\/3-540-60220-8_79","article-title":"In-Place Calculation of Minimum-Redundancy Codes","volume":"Volume 955","author":"Moffat","year":"1995","journal-title":"Proceedings of the International Workshop on Algorithms and Data Structures WADS"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2185","DOI":"10.1109\/18.945242","article-title":"Three space-economical algorithms for calculating minimum-redundancy prefix codes","volume":"47","author":"Pessoa","year":"2001","journal-title":"IEEE Trans. Inf. Theory TIT"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D. (2009, January 7\u20139). Hyperbolic dovetailing. Proceedings of the Annual European Symposium on Algorithms ESA, Copenhagen, Denmark.","DOI":"10.1007\/978-3-642-04128-0_46"},{"key":"ref_21","first-page":"29:1","article-title":"Optimal Prefix Free Codes with Partial Sorting","volume":"Volume 54","author":"Grossi","year":"2016","journal-title":"Proceedings of the Annual Symposium on Combinatorial Pattern Matching CPM"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/0020-0190(76)90071-5","article-title":"An almost optimal algorithm for unbounded searching","volume":"5","author":"Bentley","year":"1976","journal-title":"Inf. Process. Lett. IPL"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1137\/0217055","article-title":"Deferred Data Structuring","volume":"17","author":"Karp","year":"1988","journal-title":"SIAM J. Comput. SJC"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Barbay, J., Gupta, A., Jo, S., Rao, S.S., and Sorenson, J. (2013, January 2\u20134). Theory and Implementation of Online Multiselection Algorithms. Proceedings of the Annual European Symposium on Algorithms ESA, Sophia Antipolis, France.","DOI":"10.1007\/978-3-642-40450-4_10"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0205001","article-title":"Sorting and Searching in Multisets","volume":"5","author":"Munro","year":"1976","journal-title":"SIAM J. Comput. SICOMP"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Stix, G. (1991). Profile: David A. Huffman. Sci. Am. SA, 54\u201358. Available online: http:\/\/www.huffmancoding.com\/my-uncle\/scientific-american.","DOI":"10.1038\/scientificamerican0991-54"},{"key":"ref_27","unstructured":"Website TCS Stack Exchange (2012, October 25). What Are the Real-World Applications of Huffman Coding?. Available online: http:\/\/stackoverflow.com\/questions\/2199383\/what-are-the-real-world-applications-of-huffman-coding."},{"key":"ref_28","unstructured":"Wikipedia (2019, December 26). Huffman Coding. Available online: https:\/\/en.wikipedia.org\/wiki\/Huffman_coding."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1145\/348751.348754","article-title":"Fast and Flexible Word Searching on Compressed Text","volume":"18","author":"Moura","year":"2000","journal-title":"ACM Trans. Inf. Syst. TOIS"},{"key":"ref_30","unstructured":"Hart, M. (2018, May 27). Gutenberg Project. Available online: https:\/\/www.gutenberg.org\/."},{"key":"ref_31","first-page":"70","article-title":"An Overview of Adaptive Sorting","volume":"24","author":"Moffat","year":"1992","journal-title":"Aust. Comput J ACJ"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1145\/146370.146381","article-title":"A Survey of Adaptive Sorting Algorithms","volume":"24","author":"Wood","year":"1992","journal-title":"ACM Comput. Surv. ACMCS"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Milidi\u00fa, R.L., Pessoa, A.A., and Laber, E.S. (1998). A Space-Economical Algorithm for Minimum-Redundancy Coding, Departamento de Inform\u00e1tica, PUC-RJ. Technical Report.","DOI":"10.1109\/DCC.1999.755676"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0020-0190(90)90171-S","article-title":"Dynamic deferred data structuring","volume":"35","author":"Ching","year":"1990","journal-title":"Inf. Process. Lett. IPL"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Kaligosi, K., Mehlhorn, K., Munro, J.I., and Sanders, P. (2005, January 11\u201315). Towards Optimal Multiple Selection. Proceedings of the International Colloquium on Automata, Languages and Programming ICALP, Lisbon, Portugal.","DOI":"10.1007\/11523468_9"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0215021","article-title":"The Ultimate Planar Convex Hull Algorithm?","volume":"15","author":"Kirkpatrick","year":"1986","journal-title":"SIAM J. Comput. SJC"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"3:1","DOI":"10.1145\/3046673","article-title":"Instance-Optimal Geometric Algorithms","volume":"64","author":"Afshani","year":"2017","journal-title":"J. ACM"},{"key":"ref_38","first-page":"31:1","article-title":"Synergistic Solutions on MultiSets","volume":"Volume 78","author":"Radoszewski","year":"2017","journal-title":"Proceedings of the Annual Symposium on Combinatorial Pattern Matching CPM"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1145\/1082036.1082043","article-title":"Boosting textual compression in optimal linear time","volume":"52","author":"Ferragina","year":"2005","journal-title":"J. ACM"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.jalgor.2003.09.001","article-title":"Deterministic sorting in O(n log log n) time and linear space","volume":"50","author":"Han","year":"2004","journal-title":"J. Algorithms JALG"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.jalgor.2005.02.002","article-title":"External selection","volume":"58","author":"Sibeyn","year":"2006","journal-title":"J. Algorithms JALG"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Barbay, J., Gupta, A., Rao, S.S., and Sorenson, J. (2014, January 13\u201315). Dynamic Online Multiselection in Internal and External Memory. Proceedings of the International Workshop on Algorithms and Computation WALCOM, Chennai, India.","DOI":"10.1007\/978-3-319-15612-5_18"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-48518-X_1","article-title":"Efficient Implementation of the WARM-UP Algorithm for the Construction of Length-Restricted Prefix Codes","volume":"Volume 1619","author":"Goodrich","year":"1999","journal-title":"Proceedings of the Workshop on Algorithm Engineering and Experiments ALENEX"},{"key":"ref_44","unstructured":"Milidi\u00fa, R.L., Pessoa, A.A., and Laber, E.S. (1998, January 9\u201311). In-Place Length-Restricted Prefix Coding. Proceedings of the 11th Symposium on String Processing and Information Retrieval SPIRE, Santa Cruz de la Sierra, Bolivia."},{"key":"ref_45","unstructured":"Milidi\u00fa, R.L., and Laber, E.S. (1996). The WARM-UP Algorithm: A Lagrangean Construction of Length Restricted Huffman Codes, Departamento de Inform\u00e1tica, PUC-RJ. Technical Report."},{"key":"ref_46","unstructured":"Knuth, D.E. (1998). Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley Professional. [2nd ed.]."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0020-0190(98)00101-X","article-title":"Optimal alphabetic trees for binary search","volume":"67","author":"Hu","year":"1998","journal-title":"Inf. Process. Lett. IPL"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/1\/12\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:47:01Z","timestamp":1760190421000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/1\/12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,31]]},"references-count":47,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,1]]}},"alternative-id":["a13010012"],"URL":"https:\/\/doi.org\/10.3390\/a13010012","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,31]]}}}