{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T09:34:26Z","timestamp":1777455266169,"version":"3.51.4"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,12,14]],"date-time":"2007-12-14T00:00:00Z","timestamp":1197590400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,9]]},"DOI":"10.1007\/s00453-007-9140-4","type":"journal-article","created":{"date-parts":[[2007,12,13]],"date-time":"2007-12-13T12:59:06Z","timestamp":1197550746000},"page":"29-41","source":"Crossref","is-referenced-by-count":6,"title":["A Fast Algorithm for Adaptive Prefix Coding"],"prefix":"10.1007","volume":"55","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yakov","family":"Nekrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,12,14]]},"reference":[{"key":"9140_CR1","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/S0304-3975(98)00172-8","volume":"215","author":"A. Andersson","year":"1999","unstructured":"Andersson, A., Miltersen, P.B., Thorup, M.: Fusion trees can be implemented with AC0 instructions only. Theor. Comput. Sci. 215, 337\u2013344 (1999)","journal-title":"Theor. Comput. Sci."},{"key":"9140_CR2","doi-asserted-by":"crossref","first-page":"1046","DOI":"10.1109\/PROC.1973.9200","volume":"61","author":"J.B. Connell","year":"1973","unstructured":"Connell, J.B.: A Huffman-Shannon-Fano code. Proc. IEEE 61, 1046\u20131047 (1973)","journal-title":"Proc. IEEE"},{"key":"9140_CR3","doi-asserted-by":"crossref","first-page":"1095","DOI":"10.1109\/18.87001","volume":"37","author":"R.M. Capocelli","year":"1991","unstructured":"Capocelli, R.M., De Santis, A.: New bounds on the redundancy of Huffman codes. IEEE Trans. Inf. Theory 37, 1095\u20131104 (1991)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9140_CR4","unstructured":"Faller, N.: An adaptive system for data compression. In: Proc. 7th Asilomar Conference on Circuits, Systems, and Computers, pp.\u00a0593\u2013597 (1973)"},{"key":"9140_CR5","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M.L. Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J.\u00a0Comput. Syst. Sci. 47, 424\u2013436 (1993)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9140_CR6","series-title":"LNCS","first-page":"359","volume-title":"Proc. the 12th European Symposium on Algorithms","author":"T. Gagie","year":"2004","unstructured":"Gagie, T.: Dynamic Shannon coding. In: Proc. the 12th European Symposium on Algorithms. LNCS, vol.\u00a03221, pp.\u00a0359\u2013370. Springer, Berlin (2004), see also Inf. Process. Lett. 102, 113\u2013117 (2007)"},{"key":"9140_CR7","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1109\/TIT.1978.1055959","volume":"24","author":"R.G. Gallager","year":"1978","unstructured":"Gallager, R.G.: Variations on a theme by Huffman. IEEE Trans. Inf. Theory 24, 668\u2013674 (1978)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9140_CR8","doi-asserted-by":"crossref","first-page":"1164","DOI":"10.1109\/TC.1976.1674574","volume":"25","author":"M.C. Golumbic","year":"1976","unstructured":"Golumbic, M.C.: Combinatorial merging. IEEE Trans. Comput. 25, 1164\u20131167 (1976)","journal-title":"IEEE Trans. Comput."},{"key":"9140_CR9","doi-asserted-by":"crossref","first-page":"1098","DOI":"10.1109\/JRPROC.1952.273898","volume":"40","author":"D.A. Huffman","year":"1952","unstructured":"Huffman, D.A.: A method for construction of minimum-redundancy codes. Proc. IRE 40, 1098\u20131101 (1952)","journal-title":"Proc. IRE"},{"key":"9140_CR10","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1023\/A:1009910017828","volume":"3","author":"S.T. Klein","year":"2000","unstructured":"Klein, S.T.: Skeleton trees for the efficient decoding of Huffman encoded texts. Inf. Retr. 3, 7\u201323 (2000). A\u00a0preliminary version, Space- and time-efficient decoding with canonical Huffman trees, appeared in Proc. the 8th Annual Symposium on Combinatorial Pattern Matching. LNCS, vol.\u00a01264, pp.\u00a065\u201375 (1997).","journal-title":"Inf. Retr."},{"key":"9140_CR11","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0196-6774(85)90036-7","volume":"6","author":"D.E. Knuth","year":"1985","unstructured":"Knuth, D.E.: Dynamic Huffman coding. J. Algorithms 6, 163\u2013180 (1985)","journal-title":"J. Algorithms"},{"key":"9140_CR12","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/45072.45074","volume":"19","author":"D.A. Lelewer","year":"1987","unstructured":"Lelewer, D.A., Hirschberg, D.S.: Data compression. ACM Comput. Surv. 19, 261\u2013296 (1987)","journal-title":"ACM Comput. Surv."},{"key":"9140_CR13","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1006\/jagm.1999.1012","volume":"32","author":"R.L. Milidi\u00fa","year":"1999","unstructured":"Milidi\u00fa, R.L., Laber, E.S., Pessoa, A.A.: Bounding the compression loss of the FGK algorithm. J.\u00a0Algorithms 32, 195\u2013211 (1999)","journal-title":"J.\u00a0Algorithms"},{"key":"9140_CR14","doi-asserted-by":"crossref","first-page":"1200","DOI":"10.1109\/26.634683","volume":"45","author":"A. Moffat","year":"1997","unstructured":"Moffat, A., Turpin, A.: On the implementation of minimum-redundancy prefix codes. IEEE Trans. Commun. 45, 1200\u20131207 (1997)","journal-title":"IEEE Trans. Commun."},{"key":"9140_CR15","doi-asserted-by":"crossref","first-page":"1656","DOI":"10.1016\/j.ins.2005.07.010","volume":"176","author":"L. Rueda","year":"2006","unstructured":"Rueda, L., Oommen, B.J.: A fast and efficient nearly-optimal adaptive Fano coding scheme. Inf. Sci. 176, 1656\u20131683 (2006)","journal-title":"Inf. Sci."},{"key":"9140_CR16","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","volume":"27","author":"C.E. Shannon","year":"1948","unstructured":"Shannon, C.E.: A mathematical theory of communication. Bell Syst. Techn. J. 27, 379\u2013423 (1948)","journal-title":"Bell Syst. Techn. J."},{"key":"9140_CR17","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1002\/j.1538-7305.1948.tb00917.x","volume":"27","author":"C.E. Shannon","year":"1948","unstructured":"Shannon, C.E.: A mathematical theory of communication. Bell Syst. Techn. J. 27, 623\u2013656 (1948)","journal-title":"Bell Syst. Techn. J."},{"key":"9140_CR18","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1145\/363958.363991","volume":"7","author":"E.S. Schwartz","year":"1964","unstructured":"Schwartz, E.S., Kallick, B.: Generating a canonical prefix encoding. Commun. ACM 7, 166\u2013169 (1964)","journal-title":"Commun. ACM"},{"key":"9140_CR19","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1109\/18.904514","volume":"47","author":"A. Turpin","year":"2001","unstructured":"Turpin, A., Moffat, A.: On-line adaptive canonical prefix coding with bounded compression loss. IEEE Trans. Inf. Theory 47, 88\u201398 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9140_CR20","first-page":"825","volume":"34","author":"J.S. Vitter","year":"1987","unstructured":"Vitter, J.S.: Design and analysis of dynamic Huffman codes. J.\u00a0ACM 34, 825\u2013845 (1987)","journal-title":"J.\u00a0ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9140-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9140-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9140-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:01Z","timestamp":1559123101000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9140-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12,14]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["9140"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9140-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12,14]]}}}