{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T17:18:38Z","timestamp":1790702318223,"version":"4.1.0"},"reference-count":53,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2021,1,29]],"date-time":"2021-01-29T00:00:00Z","timestamp":1611878400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18F18120"],"award-info":[{"award-number":["JP18F18120"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We present algorithms computing the non-overlapping Lempel\u2013Ziv-77 factorization and the longest previous non-overlapping factor table within small space in linear or near-linear time with the help of modern suffix tree representations fitting into limited space. With similar techniques, we show how to answer substring compression queries for the Lempel\u2013Ziv-78 factorization with a possible logarithmic multiplicative slowdown depending on the used suffix tree representation.<\/jats:p>","DOI":"10.3390\/a14020044","type":"journal-article","created":{"date-parts":[[2021,1,29]],"date-time":"2021-01-29T09:25:22Z","timestamp":1611912322000},"page":"44","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Non-Overlapping LZ77 Factorization and LZ78 Substring Compression Queries with Suffix Trees"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8721-4444","authenticated-orcid":false,"given":"Dominik","family":"K\u00f6ppl","sequence":"first","affiliation":[{"name":"M&amp;D Data Science Center, Tokyo Medical and Dental University, Tokyo 113-8510, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2021,1,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv","year":"1977","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","article-title":"Compression of individual sequences via variable-rate coding","volume":"24","author":"Ziv","year":"1978","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1145\/322344.322346","article-title":"Data compression via textural substitution","volume":"29","author":"Storer","year":"1982","journal-title":"J. ACM"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"2048","DOI":"10.1007\/s00453-017-0333-1","article-title":"Lempel-Ziv Factorization Powered by Space Efficient Suffix Trees","volume":"80","author":"Fischer","year":"2018","journal-title":"Algorithmica"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.ipl.2010.12.005","article-title":"Computing Longest Previous non-overlapping Factors","volume":"111","author":"Crochemore","year":"2011","journal-title":"Inf. Process. Lett."},{"key":"ref_6","unstructured":"Cormode, G., and Muthukrishnan, S. (2005, January 23\u201325). Substring compression problems. Proceedings of the SODA, Vancouver, BC, Canada."},{"key":"ref_7","unstructured":"Jacobson, G. (November, January 30). Space-efficient Static Trees and Graphs. Proceedings of the FOCS, Research Triangle Park, NC, USA."},{"key":"ref_8","unstructured":"Clark, D.R. (1996). Compact Pat Trees. [Ph.D. Thesis, University of Waterloo]."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","article-title":"Suffix Arrays: A New Method for On-Line String Searches","volume":"22","author":"Manber","year":"1993","journal-title":"SIAM J. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","article-title":"Compressed Suffix Trees with Full Functionality","volume":"41","author":"Sadakane","year":"2007","journal-title":"Theory Comput. Syst."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1137\/S0097539702402354","article-title":"Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching","volume":"35","author":"Grossi","year":"2005","journal-title":"SIAM J. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"2162","DOI":"10.1137\/070685373","article-title":"Breaking a Time-and-Space Barrier in Constructing Full-Text Indices","volume":"38","author":"Hon","year":"2009","journal-title":"SIAM J. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Munro, J.I., Navarro, G., and Nekrich, Y. (2017, January 16\u201319). Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time. Proceedings of the SODA, Barcelona, Spain.","DOI":"10.1137\/1.9781611974782.26"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"16:1","DOI":"10.1145\/2601073","article-title":"Fully Functional Static and Dynamic Succinct Trees","volume":"10","author":"Navarro","year":"2014","journal-title":"ACM Trans. Algorithms"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.ipl.2018.09.005","article-title":"Comparison of LZ77-type parsings","volume":"141","author":"Kosolobov","year":"2019","journal-title":"Inf. Process. Lett."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0304-3975(02)00448-6","article-title":"Finding approximate repetitions under Hamming distance","volume":"303","author":"Kolpakov","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/j.tcs.2004.06.024","article-title":"Linear-time computation of local periods","volume":"326","author":"Duval","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Kociumaka, T., Kubica, M., Radoszewski, J., Rytter, W., and Walen, T. (2012, January 17\u201319). A linear time algorithm for seeds computation. Proceedings of the SODA, Kyoto, Japan.","DOI":"10.1137\/1.9781611973099.86"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Butrak, T., and Chairungsee, S. (2019, January 13\u201315). A Linear Time Algorithm for Finding Tandem Repeat in DNA Sequences. Proceedings of the ICIT, Melbourne, Australia.","DOI":"10.1145\/3377170.3377203"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Lothaire, M. (2005). Applied Combinatorics on Words, Encyclopedia of Mathematics and Its Applications, Cambridge University Press.","DOI":"10.1017\/CBO9781107341005"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.jda.2011.02.002","article-title":"Efficient algorithms for three variants of the LPF table","volume":"11","author":"Crochemore","year":"2012","journal-title":"J. Discret. Algorithms"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Chairungsee, S., Butrak, T., Chareonrak, S., and Charuphanthuset, T. (2015, January 1\u20134). Longest Previous Non-overlapping Factors Computation. Proceedings of the DEXA, Valencia, Spain.","DOI":"10.1109\/DEXA.2015.21"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Chairungsee, S., and Crochemore, M. (2017, January 16\u201318). Longest Previous Non-overlapping Factors Table Computation. Proceedings of the COCOA, LNCS, Shanghai, China.","DOI":"10.1007\/978-3-319-71147-8_35"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"291","DOI":"10.3233\/FI-2018-1745","article-title":"Efficient Approaches to Compute Longest Previous Non-overlapping Factor Array","volume":"163","author":"Chairungsee","year":"2018","journal-title":"Fundam. Inform."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Ohlebusch, E., and Weber, P. (2019, January 7\u20139). On the Computation of Longest Previous Non-overlapping Factors. Proceedings of the SPIRE, LNCS, Segovia, Spain.","DOI":"10.1007\/978-3-030-32686-9_26"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.ipl.2007.10.006","article-title":"Computing Longest Previous Factor in linear time and applications","volume":"106","author":"Crochemore","year":"2008","journal-title":"Inf. Process. Lett."},{"key":"ref_27","unstructured":"Bannai, H., Inenaga, S., and K\u00f6ppl, D. (2017, January 17\u201319). Computing All Distinct Squares in Linear Time for Integer Alphabets. Proceedings of the CPM, LIPIcs, Copenhagen, Denmark."},{"key":"ref_28","unstructured":"Ferragina, P., and Manzini, G. (2000, January 12\u201314). Opportunistic Data Structures with Applications. Proceedings of the FOCS, Redondo Beach, CA, USA."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Okanohara, D., and Sadakane, K. (2008, January 15\u201317). An Online Algorithm for Finding the Longest Previous Factors. Proceedings of the ESA, LNCS, Karlsruhe, Germany.","DOI":"10.1007\/978-3-540-87744-8_58"},{"key":"ref_30","unstructured":"Prezza, N., and Rosone, G. (July, January 29). Faster Online Computation of the Succinct Longest Previous Factor Array. Proceedings of the CiE, LNCS, Fisciano, Italy."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press.","DOI":"10.1017\/CBO9780511574931"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1137\/090779759","article-title":"Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays","volume":"40","author":"Fischer","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"5354","DOI":"10.1016\/j.tcs.2009.09.012","article-title":"Faster entropy-bounded compressed suffix trees","volume":"410","author":"Fischer","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.tcs.2013.10.010","article-title":"Generalized substring compression","volume":"525","author":"Keller","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"ref_35","unstructured":"Matsuda, K., Sadakane, K., Starikovskaya, T., and Tateshita, M. (July, January 30). Compressed Orthogonal Search on Suffix Arrays with Applications to Range LCP. Proceedings of the CPM, LIPIcs, Aarhus, Denmark."},{"key":"ref_36","unstructured":"Bille, P., G\u00f8rtz, I.L., and Steiner, T.A. (2020, January 10\u201313). String Indexing with Compressed Patterns. Proceedings of the STACS, LIPIcs, Montpelier, France."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/0020-0190(76)90071-5","article-title":"An Almost Optimal Algorithm for Unbounded Searching","volume":"5","author":"Bentley","year":"1976","journal-title":"Inf. Process. Lett."},{"key":"ref_38","unstructured":"Lifshits, Y. (2006, January 14\u201319). Solving Classical String Problems an Compressed Texts. Proceedings of the Combinatorial and Algorithmic Foundations of Pattern and Association Discovery, Dagstuhl Seminar Proceedings, Dagstuhl, Germany. Number 06201."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"50:1","DOI":"10.1145\/3398681","article-title":"Deterministic Sparse Suffix Sorting in the Restore Model","volume":"16","author":"Fischer","year":"2020","journal-title":"ACM Trans. Algorithms"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.jda.2012.07.009","article-title":"ESP-index: A compressed index based on edit-sensitive parsing","volume":"18","author":"Maruyama","year":"2013","journal-title":"J. Discret. Algorithms"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"2:1","DOI":"10.1145\/1186810.1186812","article-title":"The string edit distance matching problem with moves","volume":"3","author":"Cormode","year":"2007","journal-title":"ACM Trans. Algorithms"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","article-title":"The smallest grammar problem","volume":"51","author":"Charikar","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Bannai, H., Gawrychowski, P., Inenaga, S., and Takeda, M. (2013, January 17\u201319). Converting SLP to LZ78 in almost Linear Time. Proceedings of the CPM, LNCS, Bad Herrenalb, Germany.","DOI":"10.1007\/978-3-642-38905-4_6"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","article-title":"Application of Lempel-Ziv factorization to the approximation of grammar-based compression","volume":"302","author":"Rytter","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1016\/j.ipl.2015.04.002","article-title":"Constructing LZ78 tries and position heaps in linear time for large alphabets","volume":"115","author":"Nakashima","year":"2015","journal-title":"Inf. Process. Lett."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1007\/s00453-013-9836-6","article-title":"Linked Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space","volume":"71","author":"Jansson","year":"2015","journal-title":"Algorithmica"},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Husfeldt, T., and Rauhe, T. (1998, January 8\u201311). Marked Ancestor Problems. Proceedings of the FOCS, Palo Alto, CA, USA.","DOI":"10.7146\/brics.v5i16.21956"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.jda.2012.07.003","article-title":"Near real-time suffix tree construction via the fringe marked ancestor problem","volume":"18","author":"Breslauer","year":"2013","journal-title":"J. Discret. Algorithms"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Grossi, R., Gupta, A., Shah, R., and Vitter, J.S. (2008, January 9\u201311). On searching compressed string collections cache-obliviously. Proceedings of the PODS, Vancouver, BC, Canada.","DOI":"10.1145\/1376916.1376943"},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Raman, R., Raman, V., and Rao, S.S. (2001, January 8\u201310). Succinct Dynamic Data Structures. Proceedings of the WADS, LNCS, Providence, RI, USA.","DOI":"10.1007\/3-540-44634-6_39"},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Arbitman, Y., Naor, M., and Segev, G. (2010, January 23\u201326). Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation. Proceedings of the FOCS, Las Vegas, NV, USA.","DOI":"10.1109\/FOCS.2010.80"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"5365","DOI":"10.1016\/j.tcs.2009.09.013","article-title":"Searching for gapped palindromes","volume":"410","author":"Kolpakov","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_53","unstructured":"K\u00f6ppl, D. (2018). Exploring Regular Structures in Strings. [Ph.D. Thesis, TU Dortmund]."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/2\/44\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:17:17Z","timestamp":1760159837000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/2\/44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,29]]},"references-count":53,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["a14020044"],"URL":"https:\/\/doi.org\/10.3390\/a14020044","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,29]]}}}