{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:40:18Z","timestamp":1775281218041,"version":"3.50.1"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,6,1]],"date-time":"2010-06-01T00:00:00Z","timestamp":1275350400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000090","name":"Mountain Equipment Co-op","doi-asserted-by":"publisher","award":["TIN2006-15071-C03-03"],"award-info":[{"award-number":["TIN2006-15071-C03-03"]}],"id":[{"id":"10.13039\/501100000090","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002850","name":"Fondo Nacional de Desarrollo Cient\u00edfico y Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["1-080019"],"award-info":[{"award-number":["1-080019"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004892","name":"Agencia Espa\u00f1ola de Cooperaci\u00f3n Internacional para el Desarrollo","doi-asserted-by":"publisher","award":["A\/8065\/07"],"award-info":[{"award-number":["A\/8065\/07"]}],"id":[{"id":"10.13039\/501100004892","id-type":"DOI","asserted-by":"publisher"}]},{"name":"MEC","award":["TIN2006-15071-C03-03"],"award-info":[{"award-number":["TIN2006-15071-C03-03"]}]},{"name":"Millennium Nucleus Center for Web Research","award":["P04-067-F"],"award-info":[{"award-number":["P04-067-F"]}]},{"DOI":"10.13039\/501100010801","name":"Xunta de Galicia","doi-asserted-by":"crossref","award":["2006\/4"],"award-info":[{"award-number":["2006\/4"]}],"id":[{"id":"10.13039\/501100010801","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2010,6]]},"abstract":"<jats:p>We address the problem of adaptive compression of natural language text, considering the case where the receiver is much less powerful than the sender, as in mobile applications. Our techniques achieve compression ratios around 32% and require very little effort from the receiver. Furthermore, the receiver is not only lighter, but it can also search the compressed text with less work than that necessary to decompress it. This is a novelty in two senses: it breaks the usual compressor\/decompressor symmetry typical of adaptive schemes, and it contradicts the long-standing assumption that only semistatic codes could be searched more efficiently than the uncompressed text. Our novel compression methods are preferable in several aspects over the existing adaptive and semistatic compressors for natural language texts.<\/jats:p>","DOI":"10.1145\/1777432.1777433","type":"journal-article","created":{"date-parts":[[2010,6,29]],"date-time":"2010-06-29T13:02:22Z","timestamp":1277816542000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Dynamic lightweight text compression"],"prefix":"10.1145","volume":"28","author":[{"given":"Nieves","family":"Brisaboa","sequence":"first","affiliation":[{"name":"University of A Coru\u00f1a, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonio","family":"Fari\u00f1a","sequence":"additional","affiliation":[{"name":"University of A Coru\u00f1a, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"University of Chile, Blanco Encalada, Santiago"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9","family":"Param\u00e1","sequence":"additional","affiliation":[{"name":"University of A Coru\u00f1a, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,7,2]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Modern Information Retrieval","author":"Baeza-Yates R.","unstructured":"Baeza-Yates , R. and Ribeiro-Neto , B. 1999. Modern Information Retrieval . Addison-Wesley Longman , New York, NY . Baeza-Yates, R. and Ribeiro-Neto, B. 1999. Modern Information Retrieval. Addison-Wesley Longman, New York, NY."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/5684.5688"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11551362_41"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1076034.1076076"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-006-9001-9"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.v38:13"},{"key":"e_1_2_1_8_1","unstructured":"Burrows M. and Wheeler D. J. 1994. A block-sorting lossless data compression algorithm. Tech. rep. 124 Digital Equipment Corporation Palo Alto CA.  Burrows M. and Wheeler D. J. 1994. A block-sorting lossless data compression algorithm. Tech. rep. 124 Digital Equipment Corporation Palo Alto CA."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1984.1096090"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2111648.2111686"},{"key":"e_1_2_1_13_1","volume-title":"Information Retrieval: Computational and Theoretical Aspects","author":"Heaps H. S.","year":"1978","unstructured":"Heaps , H. S. 1978 . Information Retrieval: Computational and Theoretical Aspects . Academic Press , New York, NY . Heaps, H. S. 1978. Information Retrieval: Computational and Theoretical Aspects. Academic Press, New York, NY."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380100608"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380190207"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/290941.291013"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/348751.348754"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009934302807"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Navarro G. and Raffinot M. 2002. Flexible Pattern Matching in Strings\u2014Practical on-line search algorithms for texts and biological sequences. Cambridge University Press Cambridge UK.   Navarro G. and Raffinot M. 2002. Flexible Pattern Matching in Strings\u2014Practical on-line search algorithms for texts and biological sequences. Cambridge University Press Cambridge UK.","DOI":"10.1017\/CBO9781316135228"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.v35:12"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Conference on Data Compression (DCC'97)","author":"Turpin A.","unstructured":"Turpin , A. and Moffat , A . 1997a. Efficient approximate adaptive coding . In Proceedings of the Conference on Data Compression (DCC'97) . IEEE Computer Society, 357--366. Turpin, A. and Moffat, A. 1997a. Efficient approximate adaptive coding. In Proceedings of the Conference on Data Compression (DCC'97). IEEE Computer Society, 357--366."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 20th Australian Computer Science Conference (ACSC'97)","author":"Turpin A.","unstructured":"Turpin , A. and Moffat , A . 1997b. Fast file search using text compression . In Proceedings of the 20th Australian Computer Science Conference (ACSC'97) . 1--8. Turpin, A. and Moffat, A. 1997b. Fast file search using text compression. In Proceedings of the 20th Australian Computer Science Conference (ACSC'97). 1--8."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/42.3.193"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the USENIX Winter Technical Conference. 153--162","author":"Wu S.","unstructured":"Wu , S. and Manber , U . 1992a. Agrep\u2014a fast approximate pattern-matching tool . In Proceedings of the USENIX Winter Technical Conference. 153--162 . Wu, S. and Manber, U. 1992a. Agrep\u2014a fast approximate pattern-matching tool. In Proceedings of the USENIX Winter Technical Conference. 153--162."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/135239.135244"},{"key":"e_1_2_1_26_1","volume-title":"Report TR-94-17, Department of Computer Science","author":"Wu S.","year":"1994","unstructured":"Wu , S. and Manber , U . 1994 . A fast algorithm for multi-pattern searching. Report TR-94-17, Department of Computer Science , University of Arizona, Tucson, AZ . Wu, S. and Manber, U. 1994. A fast algorithm for multi-pattern searching. Report TR-94-17, Department of Computer Science, University of Arizona, Tucson, AZ."},{"key":"e_1_2_1_27_1","volume-title":"Human Behavior and the Principle of Least Effort","author":"Zipf G. K.","unstructured":"Zipf , G. K. 1949. Human Behavior and the Principle of Least Effort . Addison-Wesley, Reading , MA. Zipf, G. K. 1949. Human Behavior and the Principle of Least Effort. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055934"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.881693"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1777432.1777433","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1777432.1777433","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:25:52Z","timestamp":1750278352000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1777432.1777433"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["10.1145\/1777432.1777433"],"URL":"https:\/\/doi.org\/10.1145\/1777432.1777433","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"value":"1046-8188","type":"print"},{"value":"1558-2868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6]]},"assertion":[{"value":"2008-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}