{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,15]],"date-time":"2025-01-15T13:40:26Z","timestamp":1736948426434,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540403111"},{"type":"electronic","value":"9783540448884"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-44888-8_25","type":"book-chapter","created":{"date-parts":[[2007,3,5]],"date-time":"2007-03-05T16:34:12Z","timestamp":1173112452000},"page":"348-360","source":"Crossref","is-referenced-by-count":0,"title":["A Fully Linear-Time Approximation Algorithm for Grammar-Based Compression"],"prefix":"10.1007","author":[{"given":"Hiroshi","family":"Sakamoto","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,5,27]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, 1999.","DOI":"10.1007\/978-3-642-58412-1"},{"key":"25_CR2","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(96)00068-3","volume":"59","author":"S. Agostino De","year":"1996","unstructured":"S. De Agostino and J. A. Storer. On-Line versus Off-Line Computation in Dynamic Text Compression. Inform. Process. Lett., 59:169\u2013174, 1996.","journal-title":"Inform. Process. Lett."},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"M. Charikar, E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Rasala, A. Sahai, and A. Shelat. Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models. In Proc. 29th Ann. Sympo. on Theory of Computing, 792\u2013801, 2002.","DOI":"10.1145\/510019.510021"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"D. Gusfield. Algorithms on Strings, Trees, and Sequences. Computer Science and Computational Biology. Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511574931"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"T. Kida, Y. Shibata, M. Takeda, A. Shinohara, and S. Arikawa. Collage System: a Unifying Framework for Compressed Pattern Matching. Theoret. Comput. Sci. (to appear).","DOI":"10.1016\/S0304-3975(02)00426-7"},{"issue":"3","key":"25_CR6","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1109\/18.841160","volume":"46","author":"J. C. Kieffer","year":"2000","unstructured":"J. C. Kieffer and E.-H. Yang. Grammar-Based Codes: a New Class of Universal Lossless Source Codes. IEEE Trans. on Inform. Theory, 46(3):737\u2013754, 2000.","journal-title":"IEEE Trans. on Inform. Theory"},{"issue":"4","key":"25_CR7","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1109\/18.850665","volume":"IT-46","author":"J. C. Kieffer","year":"2000","unstructured":"J. C. Kieffer, E.-H. Yang, G. Nelson, and P. Cosman. Universal Lossless Compression via Multilevel Pattern Matching. IEEE Trans. Inform. Theory, IT-46(4), 1227\u20131245, 2000.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"25_CR8","unstructured":"D. Knuth. Seminumerical Algorithms. Addison-Wesley, 441\u2013462, 1981."},{"issue":"11","key":"25_CR9","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1109\/5.892708","volume":"88","author":"N. J. Larsson","year":"2000","unstructured":"N. J. Larsson and A. Moffat. Offline Dictionary-Based Compression. Proceedings of the IEEE, 88(11):1722\u20131732, 2000.","journal-title":"Proceedings of the IEEE"},{"key":"25_CR10","unstructured":"E. Lehman. Approximation Algorithms for Grammar-Based Compression. PhD thesis, MIT, 2002."},{"key":"25_CR11","unstructured":"E. Lehman and A. Shelat. Approximation Algorithms for Grammar-Based Compression. In Proc. 20th Ann. ACM-SIAM Sympo. on Discrete Algorithms, 205\u2013212, 2002."},{"key":"25_CR12","unstructured":"M. Lothaire. Combinatorics on Words, volume 17 of Encyclopedia of Mathematics and Its Applications. Addison-Wesley, 1983."},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"M. Farach. Optimal Suffix Tree Construction with Large Alphabets. In Proc. 38th Ann. Sympo. on Foundations of Computer Science, 137\u2013143, 1997.","DOI":"10.1109\/SFCS.1997.646102"},{"issue":"2\/3","key":"25_CR14","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1093\/comjnl\/40.2_and_3.103","volume":"40","author":"C. Nevill-Manning","year":"1997","unstructured":"C. Nevill-Manning and I. Witten. Compression and Explanation Using Hierarchical Grammars. Computer Journal, 40(2\/3):103\u2013116, 1997.","journal-title":"Computer Journal"},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"W. Rytter. Application of Lempel-Ziv Factorization to the Approximation of Grammar-Based Compression. In Proc. 13th Ann. Sympo. Combinatorial Pattern Matching, 20\u201331, 2002.","DOI":"10.1007\/3-540-45452-7_3"},{"key":"25_CR16","doi-asserted-by":"crossref","unstructured":"J. A. Storer and T. G. Szymanski. The Macro Model for Data Compression. In Proc. 10th Ann. Sympo. on Theory of Computing, pages 30\u201339, San Diego, California, 1978. ACM Press.","DOI":"10.1145\/800133.804329"},{"key":"25_CR17","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/MC.1984.1659158","volume":"17","author":"T. A. Welch","year":"1984","unstructured":"T. A. Welch. A Technique for High Performance Data Compression. IEEE Comput., 17:8\u201319, 1984.","journal-title":"IEEE Comput."},{"issue":"3","key":"25_CR18","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1109\/18.841161","volume":"46","author":"E.-H. Yang","year":"2000","unstructured":"E.-H. Yang and J. C. Kieffer. Efficient Universal Lossless Data Compression Algorithms Based on a Greedy Sequential Grammar Transform-Part One: without Context Models. IEEE Trans. on Inform. Theory, 46(3):755\u2013777, 2000.","journal-title":"IEEE Trans. on Inform. Theory"},{"issue":"3","key":"25_CR19","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"IT-23","author":"J. Ziv","year":"1977","unstructured":"J. Ziv and A. Lempel. A Universal Algorithm for Sequential Data Compression. IEEE Trans. on Inform. Theory, IT-23(3):337\u2013349, 1977.","journal-title":"IEEE Trans. on Inform. Theory"},{"issue":"5","key":"25_CR20","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J. Ziv","year":"1978","unstructured":"J. Ziv and A. Lempel. Compression of Individual Sequences via Variable-Rate Coding. IEEE Trans. on Inform. Theory, 24(5):530\u2013536, 1978.","journal-title":"IEEE Trans. on Inform. Theory"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44888-8_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T16:07:44Z","timestamp":1736870864000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44888-8_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540403111","9783540448884"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-44888-8_25","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}