{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T20:47:05Z","timestamp":1770497225431,"version":"3.49.0"},"publisher-location":"Cham","reference-count":67,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031439797","type":"print"},{"value":"9783031439803","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-43980-3_14","type":"book-chapter","created":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T12:02:15Z","timestamp":1695124935000},"page":"171-187","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Sublinear Time Lempel-Ziv (LZ77) Factorization"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3305-6185","authenticated-orcid":false,"given":"Jonas","family":"Ellert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,20]]},"reference":[{"issue":"5","key":"14_CR1","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0020-0190(01)00275-7","volume":"82","author":"A Amir","year":"2002","unstructured":"Amir, A., Landau, G.M., Ukkonen, E.: Online timestamped text indexing. Inf. Process. Lett. 82(5), 253\u2013259 (2002). https:\/\/doi.org\/10.1016\/S0020-0190(01)00275-7","journal-title":"Inf. Process. Lett."},{"key":"14_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-642-21458-5_25","volume-title":"Combinatorial Pattern Matching","author":"J Barbay","year":"2011","unstructured":"Barbay, J., Fischer, J., Navarro, G.: LRM-trees: compressed indices, adaptive sorting, and compressed permutations. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 285\u2013298. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-21458-5_25"},{"key":"14_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/978-3-319-38851-9_5","volume-title":"Experimental Algorithms","author":"D Belazzougui","year":"2016","unstructured":"Belazzougui, D., K\u00e4rkk\u00e4inen, J., Kempa, D., Puglisi, S.J.: Lempel-Ziv decoding in external memory. In: Goldberg, A.V., Kulikov, A.S. (eds.) SEA 2016. LNCS, vol. 9685, pp. 63\u201374. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-38851-9_5"},{"key":"14_CR4","doi-asserted-by":"publisher","unstructured":"Belazzougui, D., Puglisi, S.J.: Range predecessor and Lempel-Ziv parsing. In: Proceedings of the 27th Annual Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, USA, pp. 2053\u20132071 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch143","DOI":"10.1137\/1.9781611974331.ch143"},{"key":"14_CR5","doi-asserted-by":"publisher","unstructured":"Bille, P., Cording, P.H., Fischer, J., G\u00f8rtz, I.L.: Lempel-Ziv compression in a sliding window. In: Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), Warsaw, Poland, pp. 15:1\u201315:11 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2017.15","DOI":"10.4230\/LIPIcs.CPM.2017.15"},{"key":"14_CR6","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2017.12.021","volume":"713","author":"P Bille","year":"2018","unstructured":"Bille, P., Ettienne, M.B., G\u00f8rtz, I.L., Vildh\u00f8j, H.W.: Time-space trade-offs for Lempel-Ziv compressed indexing. Theor. Comput. Sci. 713, 66\u201377 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2017.12.021","journal-title":"Theor. Comput. Sci."},{"key":"14_CR7","doi-asserted-by":"publisher","unstructured":"Bille, P., G\u00f8rtz, I.L., Steiner, T.A.: String indexing with compressed patterns. In: Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Montpellier, France, pp. 10:1\u201310:13 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.10","DOI":"10.4230\/LIPIcs.STACS.2020.10"},{"issue":"2","key":"14_CR8","doi-asserted-by":"publisher","first-page":"45","DOI":"10.20382\/jocg.v9i2a5","volume":"9","author":"TM Chan","year":"2018","unstructured":"Chan, T.M., Tsakalidis, K.: Dynamic orthogonal range searching on the ram, revisited. J. Comput. Geom. 9(2), 45\u201366 (2018). https:\/\/doi.org\/10.20382\/jocg.v9i2a5","journal-title":"J. Comput. Geom."},{"issue":"7","key":"14_CR9","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar, M., et al.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005). https:\/\/doi.org\/10.1109\/TIT.2005.850116","journal-title":"IEEE Trans. Inf. Theory"},{"key":"14_CR10","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.jda.2011.12.021","volume":"14","author":"M Crochemore","year":"2012","unstructured":"Crochemore, M., Giambruno, L., Langiu, A., Mignosi, F., Restivo, A.: Dictionary-symbolwise flexible parsing. J. Discret. Algorithms 14, 74\u201390 (2012). https:\/\/doi.org\/10.1016\/j.jda.2011.12.021","journal-title":"J. Discret. Algorithms"},{"issue":"2","key":"14_CR11","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.ipl.2007.10.006","volume":"106","author":"M Crochemore","year":"2008","unstructured":"Crochemore, M., Ilie, L.: Computing longest previous factor in linear time and applications. Inf. Process. Lett. 106(2), 75\u201380 (2008). https:\/\/doi.org\/10.1016\/j.ipl.2007.10.006","journal-title":"Inf. Process. Lett."},{"key":"14_CR12","doi-asserted-by":"publisher","unstructured":"Crochemore, M., Langiu, A., Mignosi, F.: The rightmost equal-cost position problem. In: Proceedings of the 2013 Data Compression Conference (DCC 2013), Snowbird, UT, USA, pp. 421\u2013430 (2013). https:\/\/doi.org\/10.1109\/DCC.2013.50","DOI":"10.1109\/DCC.2013.50"},{"issue":"2","key":"14_CR13","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0020-0190(91)90223-5","volume":"38","author":"M Crochemore","year":"1991","unstructured":"Crochemore, M., Rytter, W.: Efficient parallel algorithms to test square-freeness and factorize strings. Inf. Process. Lett. 38(2), 57\u201360 (1991). https:\/\/doi.org\/10.1016\/0020-0190(91)90223-5","journal-title":"Inf. Process. Lett."},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"Ellert, J., Fischer, J., Pedersen, M.R.: New advances in rightmost Lempel-Ziv. In: Proceedings of the 30th International Symposium on String Processing and Information Retrieval (SPIRE 2023), Pisa, Italy (2023)","DOI":"10.1007\/978-3-031-43980-3_15"},{"key":"14_CR15","doi-asserted-by":"publisher","unstructured":"Farach, M., Muthukrishnan, S.: Optimal parallel dictionary matching and compression (extended abstract). In: Proceedings of the 7th Annual Symposium on Parallel Algorithms and Architectures (SPAA 1995), Santa Barbara, CA, USA, pp. 244\u2013253 (1995). https:\/\/doi.org\/10.1145\/215399.215451","DOI":"10.1145\/215399.215451"},{"key":"14_CR16","doi-asserted-by":"publisher","unstructured":"Ferrada, H., Gagie, T., Hirvola, T., Puglisi, S.J.: Hybrid indexes for repetitive datasets. Philos. Trans. R. Soc. A 372(2016) (2014). https:\/\/doi.org\/10.1098\/rsta.2013.0137","DOI":"10.1098\/rsta.2013.0137"},{"issue":"4","key":"14_CR17","doi-asserted-by":"publisher","first-page":"1521","DOI":"10.1137\/120869511","volume":"42","author":"P Ferragina","year":"2013","unstructured":"Ferragina, P., Nitto, I., Venturini, R.: On the bit-complexity of Lempel-Ziv compression. SIAM J. Comput. 42(4), 1521\u20131541 (2013). https:\/\/doi.org\/10.1137\/120869511","journal-title":"SIAM J. Comput."},{"key":"14_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/978-3-662-48350-3_45","volume-title":"Algorithms - ESA 2015","author":"J Fischer","year":"2015","unstructured":"Fischer, J., Gagie, T., Gawrychowski, P., Kociumaka, T.: Approximating LZ77 via small-space multiple-pattern matching. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 533\u2013544. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_45"},{"key":"14_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-319-19929-0_15","volume-title":"Combinatorial Pattern Matching","author":"J Fischer","year":"2015","unstructured":"Fischer, J., I, T., K\u00f6ppl, D.: Lempel Ziv computation in small space (LZ-CISS). In: Cicalese, F., Porat, E., Vaccaro, U. (eds.) CPM 2015. LNCS, vol. 9133, pp. 172\u2013184. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-19929-0_15"},{"issue":"7","key":"14_CR20","doi-asserted-by":"publisher","first-page":"2048","DOI":"10.1007\/s00453-017-0333-1","volume":"80","author":"J Fischer","year":"2017","unstructured":"Fischer, J., I, T., K\u00f6ppl, D., Sadakane, K.: Lempel\u2013Ziv factorization powered by space efficient suffix trees. Algorithmica 80(7), 2048\u20132081 (2017). https:\/\/doi.org\/10.1007\/s00453-017-0333-1","journal-title":"Algorithmica"},{"key":"14_CR21","doi-asserted-by":"publisher","unstructured":"Gagie, T.: Space-efficient RLZ-to-LZ77 conversion. CoRR abs\/2211.13254 (2022). https:\/\/doi.org\/10.48550\/arXiv.2211.13254","DOI":"10.48550\/arXiv.2211.13254"},{"key":"14_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/978-3-642-54423-1_63","volume-title":"LATIN 2014: Theoretical Informatics","author":"T Gagie","year":"2014","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: LZ77-based self-indexing with faster pattern matching. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 731\u2013742. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54423-1_63"},{"key":"14_CR23","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.jda.2014.10.003","volume":"32","author":"T Gagie","year":"2015","unstructured":"Gagie, T., Gawrychowski, P., Puglisi, S.J.: Approximate pattern matching in LZ77-compressed texts. J. Discret. Algorithms 32, 64\u201368 (2015). https:\/\/doi.org\/10.1016\/j.jda.2014.10.003","journal-title":"J. Discret. Algorithms"},{"key":"14_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/978-3-319-77404-6_36","volume-title":"LATIN 2018: Theoretical Informatics","author":"T Gagie","year":"2018","unstructured":"Gagie, T., Navarro, G., Prezza, N.: On the approximation ratio of\u00a0Lempel-Ziv parsing. In: Bender, M.A., Farach-Colton, M., Mosteiro, M.A. (eds.) LATIN 2018. LNCS, vol. 10807, pp. 490\u2013503. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-77404-6_36"},{"key":"14_CR25","doi-asserted-by":"publisher","unstructured":"Goto, K., Bannai, H.: Simpler and faster Lempel Ziv factorization. In: Proceedings of the 2013 Data Compression Conference (DCC 2013), Snowbird, UT, USA, pp. 133\u2013142 (2013). https:\/\/doi.org\/10.1109\/DCC.2013.21","DOI":"10.1109\/DCC.2013.21"},{"key":"14_CR26","doi-asserted-by":"publisher","unstructured":"Goto, K., Bannai, H.: Space efficient linear time Lempel-Ziv factorization for small alphabets. In: Proceedings of the 2014 Data Compression Conference (DCC 2014), Snowbird, UT, USA, pp. 163\u2013172 (2014). https:\/\/doi.org\/10.1109\/DCC.2014.62","DOI":"10.1109\/DCC.2014.62"},{"key":"14_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/BFb0028575","volume-title":"STACS 98","author":"T Hagerup","year":"1998","unstructured":"Hagerup, T.: Sorting and searching on the word RAM. In: Morvan, M., Meinel, C., Krob, D. (eds.) STACS 1998. LNCS, vol. 1373, pp. 366\u2013398. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0028575"},{"key":"14_CR28","doi-asserted-by":"publisher","unstructured":"Hong, A., Rossi, M., Boucher, C.: LZ77 via prefix-free parsing. In: Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX 2023), Florence, Italy, pp. 123\u2013134 (2023). https:\/\/doi.org\/10.1137\/1.9781611977561.ch11","DOI":"10.1137\/1.9781611977561.ch11"},{"key":"14_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-3-642-38527-8_14","volume-title":"Experimental Algorithms","author":"J K\u00e4rkk\u00e4inen","year":"2013","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D., Puglisi, S.J.: Lightweight Lempel-Ziv parsing. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds.) SEA 2013. LNCS, vol. 7933, pp. 139\u2013150. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38527-8_14"},{"key":"14_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/978-3-642-38905-4_19","volume-title":"Combinatorial Pattern Matching","author":"J K\u00e4rkk\u00e4inen","year":"2013","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D., Puglisi, S.J.: Linear time Lempel-Ziv factorization: simple, fast, small. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 189\u2013200. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38905-4_19"},{"issue":"1","key":"14_CR31","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/PL00009205","volume":"21","author":"J K\u00e4rkk\u00e4inen","year":"1998","unstructured":"K\u00e4rkk\u00e4inen, J., Sutinen, E.: Lempel-Ziv index for q-grams. Algorithmica 21(1), 137\u2013154 (1998). https:\/\/doi.org\/10.1007\/PL00009205","journal-title":"Algorithmica"},{"key":"14_CR32","doi-asserted-by":"publisher","unstructured":"Kempa, D.: Optimal construction of compressed indexes for highly repetitive texts. In: Proceedings of the 30th Annual Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, pp. 1344\u20131357 (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.82","DOI":"10.1137\/1.9781611975482.82"},{"key":"14_CR33","doi-asserted-by":"publisher","unstructured":"Kempa, D., Kociumaka, T.: String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure. In: Proceedings of the 51st Annual Symposium on Theory of Computing (STOC 2019), Phoenix, AZ, USA, pp. 756\u2013767 (2019). https:\/\/doi.org\/10.1145\/3313276.3316368","DOI":"10.1145\/3313276.3316368"},{"issue":"6","key":"14_CR34","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/3531445","volume":"65","author":"D Kempa","year":"2022","unstructured":"Kempa, D., Kociumaka, T.: Resolution of the burrows-wheeler transform conjecture. Commun. ACM 65(6), 91\u201398 (2022). https:\/\/doi.org\/10.1145\/3531445","journal-title":"Commun. ACM"},{"key":"14_CR35","doi-asserted-by":"publisher","unstructured":"Kempa, D., Prezza, N.: At the roots of dictionary compression: string attractors. In: Proceedings of the 50th Annual Symposium on Theory of Computing (STOC 2018), Los Angeles, CA, USA, pp. 827\u2013840 (2018). https:\/\/doi.org\/10.1145\/3188745.3188814","DOI":"10.1145\/3188745.3188814"},{"key":"14_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-030-61792-9_17","volume-title":"LATIN 2020: Theoretical Informatics","author":"T Kociumaka","year":"2020","unstructured":"Kociumaka, T., Navarro, G., Prezza, N.: Towards a definitive measure of repetitiveness. In: Kohayakawa, Y., Miyazawa, F.K. (eds.) LATIN 2021. LNCS, vol. 12118, pp. 207\u2013219. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-61792-9_17"},{"issue":"2","key":"14_CR37","doi-asserted-by":"publisher","first-page":"44","DOI":"10.3390\/a14020044","volume":"14","author":"D K\u00f6ppl","year":"2021","unstructured":"K\u00f6ppl, D.: Non-overlapping LZ77 factorization and LZ78 substring compression queries with suffix trees. Algorithms 14(2), 44 (2021). https:\/\/doi.org\/10.3390\/a14020044","journal-title":"Algorithms"},{"key":"14_CR38","doi-asserted-by":"publisher","unstructured":"K\u00f6ppl, D., Navarro, G., Prezza, N.: HOLZ: high-order entropy encoding of Lempel-Ziv factor distances. In: Proceedings of the 2022 Data Compression Conference (DCC 2022), Snowbird, UT, USA, pp. 83\u201392 (2022). https:\/\/doi.org\/10.1109\/DCC52660.2022.00016","DOI":"10.1109\/DCC52660.2022.00016"},{"key":"14_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/978-3-662-48054-0_36","volume-title":"Mathematical Foundations of Computer Science 2015","author":"D Kosolobov","year":"2015","unstructured":"Kosolobov, D.: Faster lightweight Lempel-Ziv parsing. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 432\u2013444. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48054-0_36"},{"issue":"11","key":"14_CR40","doi-asserted-by":"publisher","first-page":"3195","DOI":"10.1007\/s00453-020-00722-6","volume":"82","author":"D Kosolobov","year":"2020","unstructured":"Kosolobov, D., Valenzuela, D., Navarro, G., Puglisi, S.J.: Lempel\u2013Ziv-like parsing in small space. Algorithmica 82(11), 3195\u20133215 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00722-6","journal-title":"Algorithmica"},{"key":"14_CR41","doi-asserted-by":"publisher","unstructured":"K\u00f6ppl, D., Sadakane, K.: Lempel-Ziv computation in compressed space (LZ-CICS). In: Proceedings of the 2016 Data Compression Conference (DCC 2016), Snowbird, UT, USA, pp. 3\u201312 (2016). https:\/\/doi.org\/10.1109\/DCC.2016.38","DOI":"10.1109\/DCC.2016.38"},{"key":"14_CR42","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2012.02.006","volume":"483","author":"S Kreft","year":"2013","unstructured":"Kreft, S., Navarro, G.: On compressing and indexing repetitive sequences. Theor. Comput. Sci. 483, 115\u2013133 (2013). https:\/\/doi.org\/10.1016\/j.tcs.2012.02.006","journal-title":"Theor. Comput. Sci."},{"key":"14_CR43","doi-asserted-by":"publisher","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D., Puglisi, S.J.: Lempel-Ziv parsing in external memory. In: Proceedings of the 2014 Data Compression Conference (DCC 2014), Snowbird, UT, USA, pp. 153\u2013162 (2014). https:\/\/doi.org\/10.1109\/DCC.2014.78","DOI":"10.1109\/DCC.2014.78"},{"key":"14_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/978-3-319-07566-2_26","volume-title":"Combinatorial Pattern Matching","author":"NJ Larsson","year":"2014","unstructured":"Larsson, N.J.: Most recent match queries in on-line suffix trees. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol. 8486, pp. 252\u2013261. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-07566-2_26"},{"issue":"1","key":"14_CR45","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","volume":"22","author":"A Lempel","year":"1976","unstructured":"Lempel, A., Ziv, J.: On the complexity of finite sequences. IEEE Trans. Inf. Theory 22(1), 75\u201381 (1976). https:\/\/doi.org\/10.1109\/TIT.1976.1055501","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"14_CR46","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). https:\/\/doi.org\/10.1137\/0222058","journal-title":"SIAM J. Comput."},{"issue":"6","key":"14_CR47","doi-asserted-by":"publisher","first-page":"1494","DOI":"10.1137\/S0097539703436722","volume":"35","author":"CW Mortensen","year":"2006","unstructured":"Mortensen, C.W.: Fully dynamic orthogonal range reporting on RAM. SIAM J. Comput. 35(6), 1494\u20131525 (2006). https:\/\/doi.org\/10.1137\/S0097539703436722","journal-title":"SIAM J. Comput."},{"key":"14_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1007\/3-540-54233-7_179","volume-title":"Automata, Languages and Programming","author":"M Naor","year":"1991","unstructured":"Naor, M.: String matching with preprocessing of text and pattern. In: Albert, J.L., Monien, B., Artalejo, M.R. (eds.) ICALP 1991. LNCS, vol. 510, pp. 739\u2013750. Springer, Heidelberg (1991). https:\/\/doi.org\/10.1007\/3-540-54233-7_179"},{"issue":"4","key":"14_CR49","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.comgeo.2008.09.001","volume":"42","author":"Y Nekrich","year":"2009","unstructured":"Nekrich, Y.: Orthogonal range searching in linear and almost-linear space. Comput. Geom. 42(4), 342\u2013351 (2009). https:\/\/doi.org\/10.1016\/j.comgeo.2008.09.001","journal-title":"Comput. Geom."},{"key":"14_CR50","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.dam.2019.01.014","volume":"274","author":"T Nishimoto","year":"2020","unstructured":"Nishimoto, T., I, T., Inenaga, S., Bannai, H., Takeda, M.: Dynamic index and LZ factorization in compressed space. Discret. Appl. Math. 274, 116\u2013129 (2020). https:\/\/doi.org\/10.1016\/j.dam.2019.01.014","journal-title":"Discret. Appl. Math."},{"key":"14_CR51","doi-asserted-by":"publisher","unstructured":"Nishimoto, T., Tabei, Y.: LZRR: LZ77 parsing with right reference. Inf. Comput. 285 (2022). https:\/\/doi.org\/10.1016\/j.ic.2021.104859","DOI":"10.1016\/j.ic.2021.104859"},{"key":"14_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-642-21458-5_4","volume-title":"Combinatorial Pattern Matching","author":"E Ohlebusch","year":"2011","unstructured":"Ohlebusch, E., Gog, S.: Lempel-Ziv factorization revisited. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol. 6661, pp. 15\u201326. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-21458-5_4"},{"key":"14_CR53","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1007\/978-3-540-87744-8_58","volume-title":"Algorithms - ESA 2008","author":"D Okanohara","year":"2008","unstructured":"Okanohara, D., Sadakane, K.: An online algorithm for finding the longest previous factors. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 696\u2013707. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-87744-8_58"},{"key":"14_CR54","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-319-23826-5_2","volume-title":"String Processing and Information Retrieval","author":"A Policriti","year":"2015","unstructured":"Policriti, A., Prezza, N.: Fast online Lempel-Ziv factorization in compressed space. In: Iliopoulos, C., Puglisi, S., Yilmaz, E. (eds.) SPIRE 2015. LNCS, vol. 9309, pp. 13\u201320. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-23826-5_2"},{"key":"14_CR55","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1007\/s00453-012-9618-6","volume":"65","author":"S Raskhodnikova","year":"2013","unstructured":"Raskhodnikova, S., Ron, D., Rubinfeld, R., Smith, A.: Sublinear algorithms for approximating string compressibility. Algorithmica 65, 685\u2013709 (2013). https:\/\/doi.org\/10.1007\/s00453-012-9618-6","journal-title":"Algorithmica"},{"issue":"1","key":"14_CR56","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/322234.322237","volume":"28","author":"M Rodeh","year":"1981","unstructured":"Rodeh, M., Pratt, V.R., Even, S.: Linear algorithm for data compression via string matching. J. ACM 28(1), 16\u201324 (1981). https:\/\/doi.org\/10.1145\/322234.322237","journal-title":"J. ACM"},{"issue":"1","key":"14_CR57","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci. 302(1), 211\u2013222 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(02)00777-6","journal-title":"Theor. Comput. Sci."},{"key":"14_CR58","doi-asserted-by":"publisher","unstructured":"Shigekuni, M., I, T.: Converting RLBWT to LZ77 in smaller space. In: Proceedings of the 2022 Data Compression Conference (DCC 2022), Snowbird, UT, USA, pp. 242\u2013251 (2022). https:\/\/doi.org\/10.1109\/DCC52660.2022.00032","DOI":"10.1109\/DCC52660.2022.00032"},{"key":"14_CR59","doi-asserted-by":"publisher","unstructured":"Shun, J.: Parallel Lempel-Ziv Factorization, chap. 13. Association for Computing Machinery and Morgan & Claypool (2018). https:\/\/doi.org\/10.1145\/3018787.3018801","DOI":"10.1145\/3018787.3018801"},{"key":"14_CR60","doi-asserted-by":"publisher","unstructured":"Shun, J., Zhao, F.: Practical parallel Lempel-Ziv factorization. In: Proceedings of the 2013 Data Compression Conference (DCC 2013), Snowbird, UT, USA, pp. 123\u2013132 (2013). https:\/\/doi.org\/10.1109\/DCC.2013.20","DOI":"10.1109\/DCC.2013.20"},{"key":"14_CR61","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1007\/978-3-642-32589-2_68","volume-title":"Mathematical Foundations of Computer Science 2012","author":"T Starikovskaya","year":"2012","unstructured":"Starikovskaya, T.: Computing Lempel-Ziv factorization online. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 789\u2013799. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32589-2_68"},{"issue":"4","key":"14_CR62","doi-asserted-by":"publisher","first-page":"928","DOI":"10.1145\/322344.322346","volume":"29","author":"JA Storer","year":"1982","unstructured":"Storer, J.A., Szymanski, T.G.: Data compression via textual substitution. J. ACM 29(4), 928\u2013951 (1982). https:\/\/doi.org\/10.1145\/322344.322346","journal-title":"J. ACM"},{"key":"14_CR63","doi-asserted-by":"publisher","unstructured":"Sun, X., Wu, D., Mo, D., Cui, J., Zhong, H.: Accelerating Knuth-Morris-Pratt string matching over LZ77 compressed text. In: Proceedings of the 2021 Data Compression Conference (DCC 2021), Snowbird, UT, USA, p. 372 (2021). https:\/\/doi.org\/10.1109\/DCC50243.2021.00070","DOI":"10.1109\/DCC50243.2021.00070"},{"key":"14_CR64","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/978-3-319-38851-9_22","volume-title":"Experimental Algorithms","author":"D Valenzuela","year":"2016","unstructured":"Valenzuela, D.: CHICO: a compressed hybrid index for repetitive collections. In: Goldberg, A.V., Kulikov, A.S. (eds.) SEA 2016. LNCS, vol. 9685, pp. 326\u2013338. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-38851-9_22"},{"key":"14_CR65","doi-asserted-by":"publisher","unstructured":"Wu, C.Y.: Improved LZ77 compression. In: Proceedings of the 2021 Data Compression Conference (DCC 2021), Snowbird, UT, USA, p. 377 (2021). https:\/\/doi.org\/10.1109\/DCC50243.2021.00066","DOI":"10.1109\/DCC50243.2021.00066"},{"key":"14_CR66","doi-asserted-by":"publisher","unstructured":"Yamamoto, J., I, T., Bannai, H., Inenaga, S., Takeda, M.: Faster compact on-line Lempel-Ziv factorization. In: Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), Lyon, France, pp. 675\u2013686 (2014). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2014.675","DOI":"10.4230\/LIPIcs.STACS.2014.675"},{"issue":"3","key":"14_CR67","doi-asserted-by":"publisher","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(3), 337\u2013343 (1977). https:\/\/doi.org\/10.1109\/TIT.1977.1055714","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43980-3_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,22]],"date-time":"2023-12-22T02:03:10Z","timestamp":1703210590000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43980-3_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031439797","9783031439803"],"references-count":67,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43980-3_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"20 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Pisa","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spire2023.isti.cnr.it\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"31","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"66% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}