{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T04:43:03Z","timestamp":1743136983299,"version":"3.40.3"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319181721"},{"type":"electronic","value":"9783319181738"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-18173-8_29","type":"book-chapter","created":{"date-parts":[[2015,5,15]],"date-time":"2015-05-15T08:47:43Z","timestamp":1431679663000},"page":"390-402","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An Opportunistic Text Indexing Structure Based on Run Length Encoding"],"prefix":"10.1007","author":[{"given":"Yuya","family":"Tamakoshi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Keisuke","family":"Goto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hideo","family":"Bannai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masayuki","family":"Takeda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,5,16]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Apostolico, A., Erd\u00f6s, P.L., J\u00fcttner, A.: Parameterized searching with mismatches for run-length encoded strings. Theor. Comput., Sci. (2012)","DOI":"10.1016\/j.tcs.2012.03.018"},{"key":"29_CR2","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Tech. Rep. SRC-RR-124, Systems Research Center (1994)"},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"Chen, K.Y., Chao, K.M.: A fully compressed algorithm for computing the edit distance of run-length encoded strings. Algorithmica (2011)","DOI":"10.1007\/s00453-011-9592-4"},{"key":"29_CR4","doi-asserted-by":"crossref","unstructured":"Eltabakh, M.Y., Hon, W.K., Shah, R., Aref, W.G., Vitter, J.S.: The SBC-tree: an index for run-length compressed sequences. In: Proc. EDBT, pp. 523\u2013534 (2008)","DOI":"10.1145\/1353343.1353407"},{"issue":"2","key":"29_CR5","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"29_CR6","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.ipl.2004.02.011","volume":"90","author":"V Freschi","year":"2004","unstructured":"Freschi, V., Bogliolo, A.: Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism. IPL 90(4), 167\u2013173 (2004)","journal-title":"IPL"},{"issue":"3","key":"29_CR7","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/j.tcs.2007.07.041","volume":"387","author":"A Golynski","year":"2007","unstructured":"Golynski, A.: Optimal lower bounds for rank and select indexes. Theor. Comput. Sci. 387(3), 348\u2013359 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"29_CR8","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35(2), 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"key":"29_CR9","doi-asserted-by":"crossref","unstructured":"Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Proc. CPM 2001, pp. 181\u2013192 (2001)","DOI":"10.1007\/3-540-48194-X_17"},{"issue":"2\u20134","key":"29_CR10","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.jda.2004.08.002","volume":"3","author":"P Ko","year":"2005","unstructured":"Ko, P., Aluru, S.: Space efficient linear time construction of suffix arrays. J. Discrete Algorithms 3(2\u20134), 143\u2013156 (2005)","journal-title":"J. Discrete Algorithms"},{"issue":"43","key":"29_CR11","doi-asserted-by":"publisher","first-page":"4402","DOI":"10.1016\/j.tcs.2009.07.021","volume":"410","author":"S Lee","year":"2009","unstructured":"Lee, S., Park, K.: Dynamic rank\/select structures with applications to run-length encoded texts. Theor. Comput. Sci. 410(43), 4402\u20134413 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"29_CR12","first-page":"40","volume":"12","author":"V M\u00e4kinen","year":"2005","unstructured":"M\u00e4kinen, V., Navarro, G.: Succinct suffix arrays based on run-length encoding. Nord. J. Comput. 12(1), 40\u201366 (2005)","journal-title":"Nord. J. Comput."},{"issue":"3","key":"29_CR13","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1089\/cmb.2009.0169","volume":"17","author":"V M\u00e4kinen","year":"2010","unstructured":"M\u00e4kinen, V., Navarro, G., Sir\u00e9n, J., V\u00e4lim\u00e4ki, N.: Storage and retrieval of highly repetitive sequence collections. J. Computational Biology 17(3), 281\u2013308 (2010)","journal-title":"J. Computational Biology"},{"issue":"5","key":"29_CR14","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, E.W.: Suffix arrays: A new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"key":"29_CR15","doi-asserted-by":"crossref","unstructured":"Navarro, G.: Wavelet trees for all. In: Proc. CPM, pp. 2\u201326 (2012)","DOI":"10.1007\/978-3-642-31265-6_2"},{"issue":"10","key":"29_CR16","doi-asserted-by":"publisher","first-page":"1471","DOI":"10.1109\/TC.2010.188","volume":"60","author":"G Nong","year":"2011","unstructured":"Nong, G., Zhang, S., Chan, W.H.: Two efficient algorithms for linear time suffix array construction. IEEE Trans. Computers 60(10), 1471\u20131484 (2011)","journal-title":"IEEE Trans. Computers"},{"key":"29_CR17","unstructured":"Yamamoto, J., I, T., Bannai, H., Inenaga, S., Takeda, M.: Faster compact on-line Lempel-Ziv factorization. In: Proc. STACS 2014. pp. 675\u2013686 (2014)"},{"key":"29_CR18","doi-asserted-by":"crossref","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Transactions on Information Theory IT-23(3), 337\u2013349 (1977)","DOI":"10.1109\/TIT.1977.1055714"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-18173-8_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T08:14:04Z","timestamp":1676016844000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-18173-8_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319181721","9783319181738"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-18173-8_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 May 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}