乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:36:15Z","timestamp":1725474975700},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540496946"},{"type":"electronic","value":"9783540496960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11940128_49","type":"book-chapter","created":{"date-parts":[[2006,11,29]],"date-time":"2006-11-29T05:57:35Z","timestamp":1164779855000},"page":"484-493","source":"Crossref","is-referenced-by-count":1,"title":["Improving Time and Space Complexity for Compressed Pattern Matching"],"prefix":"10.1007","author":[{"given":"Shirou","family":"Maruyama","sequence":"first","affiliation":[]},{"given":"Hiromitsu","family":"Miyagawa","sequence":"additional","affiliation":[]},{"given":"Hiroshi","family":"Sakamoto","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Amir, A., Benson, G.: Efficient two-dimensional compressed matching. In: Proc. Data Compression Conference, p. 279 (1992)","key":"49_CR1","DOI":"10.1109\/DCC.1992.227453"},{"key":"49_CR2","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1006\/jcss.1996.0023","volume":"52","author":"A. Amir","year":"1996","unstructured":"Amir, A., Benson, G., Farach, M.: Let sleeping files lie: pattern matching in Z-compressed files. J. Comput. System Sci.\u00a052, 299\u2013307 (1996)","journal-title":"J. Comput. System Sci."},{"key":"49_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Heidelberg (1999)"},{"doi-asserted-by":"crossref","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Rasala, A., Sahai, A., Shelat, A.: Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models. In: Proc. 29th Ann. Sympo. on Theory of Computing, pp. 792\u2013801 (2002)","key":"49_CR4","DOI":"10.1145\/509907.510021"},{"doi-asserted-by":"crossref","unstructured":"Farach, M., Thorup, M.: String-matching in Lempel-Ziv compressed strings. In: 27th ACM STOC, pp. 703\u2013713 (1995)","key":"49_CR5","DOI":"10.1145\/225058.225288"},{"key":"49_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences, Computer Science and Computational Biology","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences, Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"doi-asserted-by":"crossref","unstructured":"Kida, T., Shibata, Y., Takeda, M., Shinohara, A., Arikawa, S.: Collage System: a Unifying Framework for Compressed Pattern Matching. Theoret. Comput. Sci. 298, 253\u2013272","key":"49_CR7","DOI":"10.1016\/S0304-3975(02)00426-7"},{"issue":"1","key":"49_CR8","first-page":"133","volume":"1","author":"T. Kida","year":"2000","unstructured":"Kida, T., Takeda, M., Shinohara, A., Miyazaki, M., Arikawa, S.: Multiple pattern matching in LZW compressed text. J. Discrete Algorithms\u00a01(1), 133\u2013158 (2000)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"49_CR9","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1109\/18.841160","volume":"46","author":"J.C. Kieffer","year":"2000","unstructured":"Kieffer, J.C., Yang, E.-H.: Grammar-Based Codes: a New Class of Universal Lossless Source Codes. IEEE Trans. on Inform. Theory\u00a046(3), 737\u2013754 (2000)","journal-title":"IEEE Trans. on Inform. Theory"},{"issue":"4","key":"49_CR10","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1109\/18.850665","volume":"IT-46","author":"J.C. Kieffer","year":"2000","unstructured":"Kieffer, J.C., Yang, E.-H., Nelson, G., Cosman, P.: Universal Lossless Compression via Multilevel Pattern Matching. IEEE Trans. Inform. Theory\u00a0IT-46(4), 1227\u20131245 (2000)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"49_CR11","first-page":"441","volume-title":"Seminumerical Algorithms","author":"D. Knuth","year":"1981","unstructured":"Knuth, D.: Seminumerical Algorithms, pp. 441\u2013462. Addison-Wesley, Reading (1981)"},{"issue":"11","key":"49_CR12","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1109\/5.892708","volume":"88","author":"N.J. Larsson","year":"2000","unstructured":"Larsson, N.J., Moffat, A.: Offline Dictionary-Based Compression. Proceedings of the IEEE\u00a088(11), 1722\u20131732 (2000)","journal-title":"Proceedings of the IEEE"},{"unstructured":"Lehman, E.: Approximation Algorithms for Grammar-Based Compression, PhD thesis, MIT (2002)","key":"49_CR13"},{"unstructured":"Lehman, E., Shelat, A.: Approximation Algorithms for Grammar-Based Compression. In: Proc. 20th Ann. ACM-SIAM Sympo. on Discrete Algorithms, pp. 205\u2013212 (2002)","key":"49_CR14"},{"key":"49_CR15","series-title":"Encyclopedia of Mathematics and Its Applications","volume-title":"Combinatorics on Words","author":"M. Lothaire","year":"1983","unstructured":"Lothaire, M.: Combinatorics on Words. Encyclopedia of Mathematics and Its Applications, vol.\u00a017. Addison-Wesley, Reading (1983)"},{"key":"49_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/3-540-48452-3_2","volume-title":"Combinatorial Pattern Matching","author":"G. Navarro","year":"1999","unstructured":"Navarro, G., Raffinot, M.: A general practical approach to pattern matching over Ziv-Lempel compressed text. In: Crochemore, M., Paterson, M. (eds.) CPM 1999. LNCS, vol.\u00a01645, pp. 14\u201336. Springer, Heidelberg (1999)"},{"issue":"2\/3","key":"49_CR17","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":"Nevill-Manning, C., Witten, I.: Compression and Explanation Using Hierarchical Grammars. Computer Journal\u00a040(2\/3), 103\u2013116 (1997)","journal-title":"Computer Journal"},{"key":"49_CR18","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1613\/jair.374","volume":"7","author":"C. Nevill-Manning","year":"1997","unstructured":"Nevill-Manning, C., Witten, I.: Identifying hierarchical structure in sequences: a linear-time algorithm. J. Artificial Intelligence Research\u00a07, 67\u201382 (1997)","journal-title":"J. Artificial Intelligence Research"},{"doi-asserted-by":"crossref","unstructured":"Rytter, W.: Application of Lempel-Ziv Factorization to the Approximation of Grammar-Based Compression. In: Proc. 13th Ann. Sympo. Combinatorial Pattern Matching, pp. 20\u201331 (2002)","key":"49_CR19","DOI":"10.1007\/3-540-45452-7_3"},{"key":"49_CR20","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1016\/j.jda.2004.08.016","volume":"3","author":"H. Sakamoto","year":"2005","unstructured":"Sakamoto, H.: A Fully Linear-Time Approximation Algorithm for Grammar-Based Compression. Journal of Discrete Algorithms\u00a03, 416\u2013430 (2005)","journal-title":"Journal of Discrete Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Sakamoto, H., Kida, T., Shimozono, S.: A Space-Saving Linear-Time Algorithm for Grammar-Based Compression. In: Proc. 11th International Symposium on String Processing and Information Retrieval, pp. 218\u2013229 (2004)","key":"49_CR21","DOI":"10.1007\/978-3-540-30213-1_33"},{"key":"49_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2939-9","volume-title":"Data compression: the complete reference","author":"D. Salomon","year":"1998","unstructured":"Salomon, D.: Data compression: the complete reference, 2nd edn. Springer, Heidelberg (1998)","edition":"2"},{"issue":"4","key":"49_CR23","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1145\/322344.322346","volume":"29","author":"J. Storer","year":"1982","unstructured":"Storer, J., Szymanski, T.: Data compression via textual substitution. J. Assoc. Comput. Mach.\u00a029(4), 928\u2013951 (1982)","journal-title":"J. Assoc. Comput. Mach."},{"doi-asserted-by":"crossref","unstructured":"Storer, J.A., Szymanski, T.G.: The Macro Model for Data Compression. In: Proc. 10th Ann. Sympo. on Theory of Computing, pp. 30\u201339 (1978)","key":"49_CR24","DOI":"10.1145\/800133.804329"},{"key":"49_CR25","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/MC.1984.1659158","volume":"17","author":"T.A. Welch","year":"1984","unstructured":"Welch, T.A.: A Technique for High Performance Data Compression. IEEE Comput.\u00a017, 8\u201319 (1984)","journal-title":"IEEE Comput."},{"unstructured":"Wu, S., Manber, U.: Agrep\u2013a fast approximate pattern-matching tool. In: Usenix Winter 1992 Technical Conference, pp. 153\u2013162 (1992)","key":"49_CR26"},{"issue":"3","key":"49_CR27","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1109\/18.841161","volume":"46","author":"E.-H. Yang","year":"2000","unstructured":"Yang, E.-H., Kieffer, J.C.: Efficient Universal Lossless Data Compression Algorithms Based on a Greedy Sequential Grammar Transform\u2013Part One: without Context Models. IEEE Trans. on Inform. Theory\u00a046(3), 755\u2013777 (2000)","journal-title":"IEEE Trans. on Inform. Theory"},{"issue":"3","key":"49_CR28","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"IT-23","author":"J. Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A Universal Algorithm for Sequential Data Compression. IEEE Trans. on Inform. Theory\u00a0IT-23(3), 337\u2013349 (1977)","journal-title":"IEEE Trans. on Inform. Theory"},{"issue":"5","key":"49_CR29","doi-asserted-by":"publisher","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. on Inform. Theory\u00a024(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. on Inform. Theory"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11940128_49.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:50:00Z","timestamp":1619509800000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11940128_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540496946","9783540496960"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/11940128_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}