{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T18:22:20Z","timestamp":1784398940422,"version":"3.55.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,2,22]],"date-time":"2012-02-22T00:00:00Z","timestamp":1329868800000},"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":[[2013,3]]},"DOI":"10.1007\/s00453-012-9618-6","type":"journal-article","created":{"date-parts":[[2012,2,21]],"date-time":"2012-02-21T16:40:04Z","timestamp":1329842404000},"page":"685-709","source":"Crossref","is-referenced-by-count":29,"title":["Sublinear Algorithms for Approximating String Compressibility"],"prefix":"10.1007","volume":"65","author":[{"given":"Sofya","family":"Raskhodnikova","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adam","family":"Smith","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,2,22]]},"reference":[{"issue":"1","key":"9618_CR1","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1109\/T-C.1974.223784","volume":"23","author":"N. Ahmed","year":"1974","unstructured":"Ahmed, N., Natarajan, T., Rao, K.R.: Discrete cosine transform. IEEE Trans. Comput. 23(1), 90\u201393 (1974)","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"9618_CR2","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. 58(1), 137\u2013147 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"9618_CR3","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1145\/380752.380810","volume-title":"Proceedings of the Thirty-Third Annual ACM Symposium on the Theory of Computing (STOC)","author":"Z. Bar-Yossef","year":"2001","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Sampling algorithms: lower bounds and applications. In: Proceedings of the Thirty-Third Annual ACM Symposium on the Theory of Computing (STOC), pp. 266\u2013275 (2001)"},{"issue":"1","key":"9618_CR4","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1137\/S0097539702403645","volume":"35","author":"T. Batu","year":"2005","unstructured":"Batu, T., Dasgupta, S., Kumar, R., Rubinfeld, R.: The complexity of approximating the entropy. SIAM J. Comput. 35(1), 132\u2013150 (2005)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9618_CR5","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevLett.88.048702","volume":"88","author":"D. Benedetto","year":"2002","unstructured":"Benedetto, D., Caglioti, E., Loreto, V.: Language trees and zipping. Phys. Rev. Lett. 88(4), 048702 (2002). See comment by Khmelev D.V., Teahan W.J.: Phys. Rev. Lett. 90(8), 089803 (2003); and the reply: Phys. Rev. Lett. 90(8), 089804 (2003)","journal-title":"Phys. Rev. Lett."},{"key":"9618_CR6","first-page":"366","volume-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"M. Brautbar","year":"2007","unstructured":"Brautbar, M., Samorodnitsky, A.: Approximating entropy from sublinear samples. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 366\u2013375 (2007)"},{"key":"9618_CR7","unstructured":"Bunge, J.: Bibliography on estimating the number of classes in a population. www.stat.cornell.edu\/~bunge\/bibliography.htm"},{"key":"9618_CR8","unstructured":"Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Tech. Rep. 124, Digital Equipment Corporation (1994)"},{"issue":"7","key":"9618_CR9","doi-asserted-by":"crossref","first-page":"1551","DOI":"10.1109\/TIT.2004.830771","volume":"50","author":"H. Cai","year":"2004","unstructured":"Cai, H., Kulkarni, S.R., Verd\u00fa, S.: Universal entropy estimation via block sorting. IEEE Trans. Inf. Theory 50(7), 1551\u20131561 (2004)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9618_CR10","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1145\/335168.335230","volume-title":"Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS)","author":"M. Charikar","year":"2000","unstructured":"Charikar, M., Chaudhuri, S., Motwani, R., Narasayya, V.R.: Towards estimation error guarantees for distinct values. In: Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pp. 268\u2013279. ACM, New York (2000)"},{"key":"9618_CR11","volume-title":"An Introduction to Wavelets","author":"C.K. Chui","year":"1992","unstructured":"Chui, C.K.: An Introduction to Wavelets. Academic Press, San Diego (1992)"},{"issue":"4","key":"9618_CR12","doi-asserted-by":"crossref","first-page":"1523","DOI":"10.1109\/TIT.2005.844059","volume":"51","author":"R. Cilibrasi","year":"2005","unstructured":"Cilibrasi, R., Vit\u00e1nyi, P.M.B.: Clustering by compression. IEEE Trans. Inf. Theory 51(4), 1523\u20131545 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9618_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/11750321_2","volume-title":"Proceedings of the Third International Conference on Theory and Applications of Models of Computation (TAMC)","author":"R. Cilibrasi","year":"2006","unstructured":"Cilibrasi, R., Vit\u00e1nyi, P.M.B.: Similarity of objects and the meaning of words. In: Cai,\u00a0J., Cooper,\u00a0S.B., Li,\u00a0A. (eds.) Proceedings of the Third International Conference on Theory and Applications of Models of Computation (TAMC). Lecture Notes in Computer Science, vol. 3959, pp. 21\u201345. Springer, Berlin (2006)"},{"issue":"4","key":"9618_CR14","doi-asserted-by":"crossref","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."},{"key":"9618_CR15","first-page":"321","volume-title":"Proceedings of the Thirty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"G. Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: Substring compression problems. In: Proceedings of the Thirty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 321\u2013330 (2005)"},{"key":"9618_CR16","doi-asserted-by":"crossref","DOI":"10.1002\/0471200611","volume-title":"Elements of Information Theory","author":"T. Cover","year":"1991","unstructured":"Cover, T., Thomas, J.: Elements of Information Theory. Wiley, New York (1991)"},{"key":"9618_CR17","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Giancarlo, R., Greco, V., Manzini, G., Valiente, G.: Compression-based classification of biological sequences and structures via the universal similarity metric: experimental assessment. BMC Bioinformatics 2007, 8:252 (2007)","DOI":"10.1186\/1471-2105-8-252"},{"issue":"1","key":"9618_CR18","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/S0304-3975(98)00248-5","volume":"218","author":"A. Luca de","year":"1999","unstructured":"de Luca, A.: On the combinatorics of finite words. Theor. Comput. Sci. 218(1), 13\u201339 (1999)","journal-title":"Theor. Comput. Sci."},{"key":"9618_CR19","first-page":"555","volume-title":"Proceedings of the Data Compression Conference (DCC)","author":"E. Frank","year":"2000","unstructured":"Frank, E., Chui, C., Witten, I.H.: Text categorization using compression models. In: Proceedings of the Data Compression Conference (DCC), p. 555 (2000)"},{"key":"9618_CR20","first-page":"1","volume-title":"Discrete Math and Theoretical Computer Science (DMTCS), Proceedings of the Conference on Analysis of Algorithms (AofA)","author":"I. Gheorghiciuc","year":"2007","unstructured":"Gheorghiciuc, I., Ward, M.: On correlation polynomials and subword complexity. In: Discrete Math and Theoretical Computer Science (DMTCS), Proceedings of the Conference on Analysis of Algorithms (AofA), pp. 1\u201318 (2007)"},{"key":"9618_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/3-540-45655-4_35","volume-title":"Proceedings of the 8th Annual International Conference on Computing and Combinatorics (COCOON)","author":"L. Ilie","year":"2002","unstructured":"Ilie, L., Yu, S., Zhang, K.: Repetition complexity of words. In: Ibarra,\u00a0O.H., Zhang,\u00a0L. (eds.) Proceedings of the 8th Annual International Conference on Computing and Combinatorics (COCOON). Lecture Notes in Computer Science, vol. 2387, pp. 320\u2013329. Springer, Berlin (2002)"},{"issue":"1\u20133","key":"9618_CR22","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/j.tcs.2004.06.023","volume":"326","author":"S. Janson","year":"2004","unstructured":"Janson, S., Lonardi, S., Szpankowski, W.: On average sequence complexity. Theor. Comput. Sci. 326(1\u20133), 213\u2013227 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"9618_CR23","first-page":"119","volume":"9","author":"Z. K\u00e1sa","year":"1998","unstructured":"K\u00e1sa, Z.: On the d-complexity of strings. Pure Math. Appl. 9(1\u20132), 119\u2013128 (1998)","journal-title":"Pure Math. Appl."},{"key":"9618_CR24","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/978-3-642-02441-2_3","volume-title":"Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM)","author":"O. Keller","year":"2009","unstructured":"Keller, O., Kopelowitz, T., Landau, S., Lewenstein, M.: Generalized substring compression. In: Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 26\u201338 (2009)"},{"key":"9618_CR25","first-page":"206","volume-title":"Proceedings of ACM Conference on Knowledge Discovery and Data Mining (KDD)","author":"E. Keogh","year":"2004","unstructured":"Keogh, E., Lonardi, S., Ratanamahatana, C.: Towards parameter-free data mining. In: Proceedings of ACM Conference on Knowledge Discovery and Data Mining (KDD), pp. 206\u2013215 (2004)"},{"key":"9618_CR26","doi-asserted-by":"crossref","first-page":"278","DOI":"10.4018\/978-1-60566-010-3.ch045","volume-title":"Encyclopedia of Data Warehousing and Mining","author":"E.J. Keogh","year":"2009","unstructured":"Keogh, E.J., Keogh, L., Handley, J.: Compression-based data mining. In: Wang,\u00a0J. (ed.) Encyclopedia of Data Warehousing and Mining, pp. 278\u2013285. IGI Global (2009)"},{"issue":"2","key":"9618_CR27","first-page":"96","volume":"37","author":"O.V. Kukushkina","year":"2000","unstructured":"Kukushkina, O.V., Polikarpov, A.A., Khmelev, D.V.: Using literal and grammatical statistics for authorship attribution. Problemy Peredachi Inf. 37(2), 96\u201398 (2000) (Problems of Information Transmission (Engl. Transl.) 37, 172\u2013184 (2001))","journal-title":"Problemy Peredachi Inf."},{"key":"9618_CR28","first-page":"205","volume-title":"Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"E. Lehman","year":"2002","unstructured":"Lehman, E., Shelat, A.: Approximation algorithms for grammar-based compression. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 205\u2013212 (2002)"},{"issue":"2","key":"9618_CR29","doi-asserted-by":"crossref","first-page":"277","DOI":"10.36045\/bbms\/1102714173","volume":"8","author":"F. Lev\u00e9","year":"2001","unstructured":"Lev\u00e9, F., S\u00e9\u00e9bold, P.: Proof of a conjecture on word complexity. Bull. Belg. Math. Soc. 8(2), 277\u2013291 (2001)","journal-title":"Bull. Belg. Math. Soc."},{"issue":"12","key":"9618_CR30","doi-asserted-by":"crossref","first-page":"3250","DOI":"10.1109\/TIT.2004.838101","volume":"50","author":"M. Li","year":"2004","unstructured":"Li, M., Chen, X., Li, X., Ma, B., Vit\u00e1nyi, P.M.B.: The similarity metric. IEEE Trans. Inf. Theory 50(12), 3250\u20133264 (2004)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9618_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M. Li","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and Its Applications. Springer, Berlin (1997)"},{"key":"9618_CR32","unstructured":"Loewenstern, D., Hirsh, H., Noordewier, M., Yianilos, P.: DNA sequence classification using compression-based induction. Tech. Rep. 95-04, Rutgers University, DIMACS (1995)"},{"issue":"6","key":"9618_CR33","doi-asserted-by":"crossref","first-page":"1191","DOI":"10.1162\/089976603321780272","volume":"15","author":"L. Paninski","year":"2003","unstructured":"Paninski, L.: Estimation of entropy and mutual information. Neural Comput. 15(6), 1191\u20131253 (2003)","journal-title":"Neural Comput."},{"issue":"9","key":"9618_CR34","doi-asserted-by":"crossref","first-page":"2200","DOI":"10.1109\/TIT.2004.833360","volume":"50","author":"L. Paninski","year":"2004","unstructured":"Paninski, L.: Estimating entropy on m bins given fewer than m samples. IEEE Trans. Inf. Theory 50(9), 2200\u20132203 (2004)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9618_CR35","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/978-1-4757-6048-4_32","volume-title":"Numbers, Information and Complexity, I","author":"L. Pierce II","year":"2000","unstructured":"Pierce, L. II, Shields, P.C.: Sequences incompressible by SLZ (LZW), yet fully compressible by ULZ. In: Numbers, Information and Complexity, I, pp. 385\u2013390. Kluwer, Norwell (2000)"},{"key":"9618_CR36","first-page":"609","volume-title":"Proceedings of the Eleventh International Workshop on Randomization and Computation (RANDOM)","author":"S. Raskhodnikova","year":"2007","unstructured":"Raskhodnikova, S., Ron, D., Rubinfeld, R., Smith, A.: Sublinear algorithms for approximating string compressibility. In: Proceedings of the Eleventh International Workshop on Randomization and Computation (RANDOM), pp. 609\u2013623 (2007)"},{"issue":"3","key":"9618_CR37","doi-asserted-by":"crossref","first-page":"813","DOI":"10.1137\/070701649","volume":"39","author":"S. Raskhodnikova","year":"2009","unstructured":"Raskhodnikova, S., Ron, D., Shpilka, A., Smith, A.: Strong lower bounds for approximating distribution support size and the distinct elements problem. SIAM J. Comput. 39(3), 813\u2013842 (2009)","journal-title":"SIAM J. Comput."},{"key":"9618_CR38","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1109\/DCC.2006.13","volume-title":"Proceedings of the Data Compression Conference (DCC)","author":"D. Sculley","year":"2006","unstructured":"Sculley, D., Brodley, C.E.: Compression and machine learning: a new perspective on feature space vectors. In: Proceedings of the Data Compression Conference (DCC), pp. 332\u2013341 (2006)"},{"issue":"2","key":"9618_CR39","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/BF02988306","volume":"9","author":"J. Shallit","year":"1993","unstructured":"Shallit, J.: On the maximum number of distinct factors of a binary string. Graphs Comb. 9(2), 197\u2013200 (1993)","journal-title":"Graphs Comb."},{"issue":"3","key":"9618_CR40","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1109\/18.382012","volume":"41","author":"F.M.J. Willems","year":"1995","unstructured":"Willems, F.M.J., Shtarkov, Y.M., Tjalkens, T.J.: The context-tree weighting method: basic properties. IEEE Trans. Inf. Theory 41(3), 653\u2013664 (1995)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9618_CR41","first-page":"198","volume-title":"Proceedings of the Data Compression Conference (DCC)","author":"I.H. Witten","year":"1999","unstructured":"Witten, I.H., Bray, Z., Mahoui, M., Teahan, W.J.: Text mining: a new frontier for lossless compression. In: Proceedings of the Data Compression Conference (DCC), pp. 198\u2013207 (1999)"},{"key":"9618_CR42","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J. Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory 23, 337\u2013343 (1977)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9618_CR43","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J. Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theory 24, 530\u2013536 (1978)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9618-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9618-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9618-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,2]],"date-time":"2020-07-02T20:25:41Z","timestamp":1593721541000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9618-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,22]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["9618"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9618-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,22]]}}}