{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T10:52:57Z","timestamp":1772103177539,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,6,25]],"date-time":"2020-06-25T00:00:00Z","timestamp":1593043200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,25]],"date-time":"2020-06-25T00:00:00Z","timestamp":1593043200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,4]]},"DOI":"10.1007\/s00224-020-09992-7","type":"journal-article","created":{"date-parts":[[2020,6,25]],"date-time":"2020-06-25T08:02:37Z","timestamp":1593072157000},"page":"593-612","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Forward Looking Huffman Coding"],"prefix":"10.1007","volume":"65","author":[{"given":"Shmuel T.","family":"Klein","sequence":"first","affiliation":[]},{"given":"Shoham","family":"Saadia","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2320-9064","authenticated-orcid":false,"given":"Dana","family":"Shapira","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,6,25]]},"reference":[{"key":"9992_CR1","unstructured":"Amir, A., Benson, G.: Efficient two-dimensional compressed matching. In: Proc. IEEE Data Compression Conference DCC\u201392, pp 279\u2013288 (1992)"},{"key":"9992_CR2","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.jda.2016.12.001","volume":"43","author":"G Baruch","year":"2017","unstructured":"Baruch, G., Klein, S.T., Shapira, D.: A space efficient direct access data structure. Journal of Discrete Algorithms 43, 26\u201337 (2017)","journal-title":"Journal of Discrete Algorithms"},{"key":"9992_CR3","doi-asserted-by":"crossref","unstructured":"Baruch, G., Klein, S.T., Shapira, D.: Applying compression to hierarchical clustering. In: Similarity Search and Applications - 11th International Conference, SISAP 2018, Lima, Peru, October 7-9, 2018, Proceedings, pp 151\u2013162 (2018)","DOI":"10.1007\/978-3-030-02224-2_12"},{"issue":"4","key":"9992_CR4","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1109\/TCOM.1984.1096090","volume":"32","author":"J Cleary","year":"1984","unstructured":"Cleary, J., Witten, I.: Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. 32(4), 396\u2013402 (1984)","journal-title":"IEEE Trans. Commun."},{"issue":"2","key":"9992_CR5","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","volume":"21","author":"P Elias","year":"1975","unstructured":"Elias, P.: Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory 21(2), 194\u2013203 (1975)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9992_CR6","unstructured":"Faller, N.: An adaptive system for data compression. In: Record of the 7th Asilomar Conference on Circuits, Systems and Computers, pp 593\u2013597 (1973)"},{"issue":"4","key":"9992_CR7","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1109\/TIT.1984.1056931","volume":"30","author":"TJ Ferguson","year":"1984","unstructured":"Ferguson, T.J., Rabinowitz, J.H.: Self-synchronizing Huffman codes. IEEE Trans. Inf. Theory 30(4), 687\u2013693 (1984)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"6","key":"9992_CR8","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1109\/TIT.1978.1055959","volume":"24","author":"R Gallager","year":"1978","unstructured":"Gallager, R.: Variations on a theme by Huffman. IEEE Trans. Inf. Theory 24 (6), 668\u2013674 (1978)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"9","key":"9992_CR9","doi-asserted-by":"publisher","first-page":"1098","DOI":"10.1109\/JRPROC.1952.273898","volume":"40","author":"DA Huffman","year":"1952","unstructured":"Huffman, D.A.: A method for the construction of minimum-redundancy codes. Proc. IRE 40(9), 1098\u20131101 (1952)","journal-title":"Proc. IRE"},{"key":"9992_CR10","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space efficient static trees and graphs. In: Proceedings of FOCS, pp 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"9992_CR11","doi-asserted-by":"crossref","unstructured":"Klein, S.T., Opalinsky, E., Shapira, D.: Selective dynamic compression. In: Proceedings of the Prague Stringology Conference 2019, Czech Technical University in Prague, Czech Republic (2019)","DOI":"10.1109\/DCC.2019.00095"},{"key":"9992_CR12","doi-asserted-by":"crossref","unstructured":"Klein, S.T., Saadia, S., Shapira, D.: Forward looking Huffman coding. In: The 14th Computer Science Symposium in Russia, CSR, Novosibirsk, Russia, July 1-5, LNCS 11532, pp 203\u2013214 (2019)","DOI":"10.1007\/978-3-030-19955-5_18"},{"key":"9992_CR13","unstructured":"Klein, S.T., Shapira, D.: A new compression method for compressed matching. In: Data Compression Conference, DCC Snowbird, Utah, USA, March 28-30, 2000, pp 400\u2013409 (2000)"},{"issue":"6","key":"9992_CR14","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1142\/S012905410600442X","volume":"17","author":"ST Klein","year":"2006","unstructured":"Klein, S.T., Shapira, D.: Compressed pattern matching in JPEG images. Int. J. Found Comput. Sci. 17(6), 1297\u20131306 (2006)","journal-title":"Int. J. Found Comput. Sci."},{"issue":"1","key":"9992_CR15","doi-asserted-by":"publisher","first-page":"61","DOI":"10.3390\/a4010061","volume":"4","author":"ST Klein","year":"2011","unstructured":"Klein, S.T., Shapira, D.: Compressed matching in dictionaries. Algorithms 4(1), 61\u201374 (2011)","journal-title":"Algorithms"},{"issue":"5","key":"9992_CR16","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1016\/j.ipm.2011.01.005","volume":"47","author":"ST Klein","year":"2011","unstructured":"Klein, S.T., Shapira, D.: On improving Tunstall codes. Inf. Process. Manage. 47(5), 777\u2013785 (2011)","journal-title":"Inf. Process. Manage."},{"key":"9992_CR17","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/j.tcs.2015.12.021","volume":"638","author":"ST Klein","year":"2016","unstructured":"Klein, S.T., Shapira, D.: Compressed matching for feature vectors. Theor Comput. Sci. 638, 52\u201362 (2016)","journal-title":"Theor Comput. Sci."},{"key":"9992_CR18","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.dam.2015.11.003","volume":"212","author":"ST Klein","year":"2016","unstructured":"Klein, S.T., Shapira, D.: Random access to Fibonacci encoded files. Discret. Appl. Math. 212, 115\u2013128 (2016)","journal-title":"Discret. Appl. Math."},{"key":"9992_CR19","doi-asserted-by":"crossref","unstructured":"Klein, S.T., Shapira, D.: Integrated encryption in dynamic arithmetic compression. In: Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Ume\u00e5, Sweden, March 6-9, 2017, Proceedings, pp 143\u2013154 (2017)","DOI":"10.1007\/978-3-319-53733-7_10"},{"issue":"2","key":"9992_CR20","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0196-6774(85)90036-7","volume":"6","author":"DE Knuth","year":"1985","unstructured":"Knuth, D.E.: Dynamic Huffman coding. Journal of Algorithms 6(2), 163\u2013180 (1985)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"9992_CR21","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1002\/spe.4380190207","volume":"19","author":"A Moffat","year":"1989","unstructured":"Moffat, A.: Word-based compression. Softw. Pract. Exper. 19(2), 185\u2013198 (1989)","journal-title":"Softw. Pract. Exper."},{"key":"9992_CR22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316588284","volume-title":"Compact Data Structures: a Practical Approach","author":"G Navarro","year":"2016","unstructured":"Navarro, G.: Compact Data Structures: a Practical Approach. Cambridge University Press, Cambridge (2016)"},{"key":"9992_CR23","unstructured":"Nelson, M., Gailly, J.-L.: The Data Compression Book. 2nd edn. M & T Books (1996)"},{"issue":"4","key":"9992_CR24","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R Raman","year":"2007","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"9992_CR25","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1145\/363958.363991","volume":"7","author":"ES Schwartz","year":"1964","unstructured":"Schwartz, E.S., Kallick, B.: Generating a canonical prefix encoding. Commun. ACM 7, 166\u2013169 (1964)","journal-title":"Commun. ACM"},{"issue":"2","key":"9992_CR26","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/j.ipm.2005.02.003","volume":"42","author":"D Shapira","year":"2006","unstructured":"Shapira, D., Daptardar, A.H.: Adapting the knuth-morris-pratt algorithm for pattern matching in huffman encoded texts. Inf. Process. Manage. 42(2), 429\u2013439 (2006)","journal-title":"Inf. Process. Manage."},{"issue":"3","key":"9992_CR27","doi-asserted-by":"publisher","first-page":"58","DOI":"10.5121\/ijnsa.2011.3305","volume":"3","author":"A Singh","year":"2011","unstructured":"Singh, A., Gilhotra, R.: Data security using private key encryption system based on arithmetic coding. International Journal of Network Security & Its Applications (IJNSA) 3(3), 58\u201367 (2011)","journal-title":"International Journal of Network Security & Its Applications (IJNSA)"},{"issue":"4","key":"9992_CR28","doi-asserted-by":"publisher","first-page":"928","DOI":"10.1145\/322344.322346","volume":"29","author":"JA Storer","year":"1982","unstructured":"Storer, J.A., Szymanski, T.G.: Data compression via textural substitution. J. ACM 29(4), 928\u2013951 (1982)","journal-title":"J. ACM"},{"key":"9992_CR29","unstructured":"Tunstall, B.P.: Synthesis of noiseless compression codes. Georgia Institute of Technology (1967)"},{"key":"9992_CR30","doi-asserted-by":"crossref","unstructured":"V\u00e9ronis, J., Langlais, P.: Evaluation of parallel text alignment systems: the arcade project. In: V\u00e9ronis, J. (ed.) Parallel Text Processing. Kluwer Academic Publishers, Dordrecht, Chapter 19, pp. 369\u2013388 (2000)","DOI":"10.1007\/978-94-017-2535-4_19"},{"issue":"4","key":"9992_CR31","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1145\/31846.42227","volume":"34","author":"JS Vitter","year":"1987","unstructured":"Vitter, J.S.: Design and analysis of dynamic Huffman codes. J. ACM 34(4), 825\u2013845 (1987)","journal-title":"J. ACM"},{"issue":"2","key":"9992_CR32","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1109\/LSP.2005.861589","volume":"13","author":"J Wen","year":"2006","unstructured":"Wen, J., Kim, H., Villasenor, J.: Binary arithmetic coding with key based interval splitting. IEEE Trans. on Signal Processing Letters 13(2), 69\u201372 (2006)","journal-title":"IEEE Trans. on Signal Processing Letters"},{"issue":"6","key":"9992_CR33","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1145\/214762.214771","volume":"30","author":"IH Witten","year":"1987","unstructured":"Witten, I.H., Neal, Radford M., Cleary, J.G.: Arithmetic coding for data compression. Commun. ACM 30(6), 520\u2013540 (1987)","journal-title":"Commun. ACM"},{"issue":"2","key":"9992_CR34","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/1132956.1132959","volume":"38","author":"J Zobel","year":"2006","unstructured":"Zobel, J., Moffat, A.: Inverted files for text search engines. ACM Comput. Surv. 38(2), 6 (2006)","journal-title":"ACM Comput. Surv."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09992-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-09992-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09992-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,24]],"date-time":"2021-06-24T23:19:29Z","timestamp":1624576769000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-09992-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,25]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["9992"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-09992-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,25]]},"assertion":[{"value":"25 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}