{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:21:01Z","timestamp":1750220461797,"version":"3.41.0"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T00:00:00Z","timestamp":1635552000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"JSPS KAKENHI","award":["JP18F18120, JP21K17701"],"award-info":[{"award-number":["JP18F18120, JP21K17701"]}]},{"name":"Millennium Science Initiative Program","award":["ICN17_002"],"award-info":[{"award-number":["ICN17_002"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            The Lempel-Ziv 78 (\n            <jats:sc>LZ78<\/jats:sc>\n            ) and Lempel-Ziv-Welch (\n            <jats:sc>LZW<\/jats:sc>\n            ) text factorizations are popular, not only for bare compression but also for building compressed data structures on top of them. Their regular factor structure makes them computable within space bounded by the compressed output size. In this article, we carry out the first thorough study of low-memory\n            <jats:sc>LZ78<\/jats:sc>\n            and\n            <jats:sc>LZW<\/jats:sc>\n            text factorization algorithms, introducing more efficient alternatives to the classical methods, as well as new techniques that can run within less memory space than the necessary to hold the compressed file. Our results build on hash-based representations of tries that may have independent interest.\n          <\/jats:p>","DOI":"10.1145\/3481638","type":"journal-article","created":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T16:06:57Z","timestamp":1635610017000},"page":"1-47","source":"Crossref","is-referenced-by-count":0,"title":["Engineering Practical Lempel-Ziv Tries"],"prefix":"10.1145","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2509-8097","authenticated-orcid":false,"given":"Diego","family":"Arroyuelo","sequence":"first","affiliation":[{"name":"Millennium Institute for Foundational Research on Data (IMFD) and Universidad T\u00e9cnica Federico Santa Mar\u00eda, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodrigo","family":"C\u00e1novas","sequence":"additional","affiliation":[{"name":"Baker Heart and Diabetes Institute, Melbourne VIC, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3384-597X","authenticated-orcid":false,"given":"Johannes","family":"Fischer","sequence":"additional","affiliation":[{"name":"TU Dortmund, Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8721-4444","authenticated-orcid":false,"given":"Dominik","family":"K\u00f6ppl","sequence":"additional","affiliation":[{"name":"Tokyo Medical and Dental University, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marvin","family":"L\u00f6bel","sequence":"additional","affiliation":[{"name":"TU Dortmund, Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2286-741X","authenticated-orcid":false,"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"Millennium Institute for Foundational Research on Data (IMFD) and University of Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajeev","family":"Raman","sequence":"additional","affiliation":[{"name":"University of Leicester, Leicester, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,10,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/17.2.135"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0023"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.03.001"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9443-8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-9969-x"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67428-5_4"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0348-7"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 30th ACSC (CRPIT)","volume":"91","author":"Askitis Nikolas","year":"2009","unstructured":"Nikolas Askitis . 2009 . Fast and compact hash tables for integer keys . In Proceedings of the 30th ACSC (CRPIT) , Vol. 91 . 101\u2013110. Nikolas Askitis. 2009. Fast and compact hash tables for integer keys. In Proceedings of the 30th ACSC (CRPIT), Vol. 91. 101\u2013110."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34109-0_10"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.08.005"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16321-0_15"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118737.3118845"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 8th SODA. 360\u2013369","author":"Bentley Jon Louis","year":"1997","unstructured":"Jon Louis Bentley and Robert Sedgewick . 1997 . Fast algorithms for sorting and searching strings . In Proceedings of the 8th SODA. 360\u2013369 . Jon Louis Bentley and Robert Sedgewick. 1997. Fast algorithms for sorting and searching strings. In Proceedings of the 8th SODA. 360\u2013369."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 2nd WAE. 37\u201348","author":"Black John R.","year":"1998","unstructured":"John R. Black , Charles U. Martel , and Hongbin Qi . 1998 . Graph and hashing algorithms for modern architectures: Design and performance . In Proceedings of the 2nd WAE. 37\u201348 . John R. Black, Charles U. Martel, and Hongbin Qi. 1998. Graph and hashing algorithms for modern architectures: Design and performance. In Proceedings of the 2nd WAE. 37\u201348."},{"volume-title":"Proceedings of the 26th FOCS. 281\u2013288","author":"Celis Pedro","key":"e_1_2_1_16_1","unstructured":"Pedro Celis , Per-\u00c5ke Larson , and J. Ian Munro . 1985. Robin Hood hashing . In Proceedings of the 26th FOCS. 281\u2013288 . Pedro Celis, Per-\u00c5ke Larson, and J. Ian Munro. 1985. Robin Hood hashing. In Proceedings of the 26th FOCS. 281\u2013288."},{"key":"e_1_2_1_17_1","first-page":"366","article-title":"M\u00e9moire sur les nombres premiers","volume":"1","author":"Chebyshev Pafnuty Lvovich","year":"1852","unstructured":"Pafnuty Lvovich Chebyshev . 1852 . M\u00e9moire sur les nombres premiers . J. Math\u00e9m. Pures Appliq. 1 (1852), 366 \u2013 390 . Pafnuty Lvovich Chebyshev. 1852. M\u00e9moire sur les nombres premiers. J. Math\u00e9m. Pures Appliq. 1 (1852), 366\u2013390.","journal-title":"J. Math\u00e9m. Pures Appliq."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a030"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676499"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380230305"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 16th SEA (LIPIcs)","volume":"75","author":"Dinklage Patrick","year":"2017","unstructured":"Patrick Dinklage , Johannes Fischer , Dominik K\u00f6ppl , Marvin L\u00f6bel , and Kunihiko Sadakane . 2017 . Compression with the tudocomp Framework . In Proceedings of the 16th SEA (LIPIcs) , Vol. 75 . 13:1\u201313:22. arXiv:1702.07577. Patrick Dinklage, Johannes Fischer, Dominik K\u00f6ppl, Marvin L\u00f6bel, and Kunihiko Sadakane. 2017. Compression with the tudocomp Framework. In Proceedings of the 16th SEA (LIPIcs), Vol. 75. 13:1\u201313:22. arXiv:1702.07577."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321820"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/355611.362546"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-02432-5_16"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11918-2_3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19929-0_14"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67428-5_16"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_45"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0333-1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.1999.755681"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 5th SWAT. 392\u2013403","author":"Gasieniec Leszek","year":"1996","unstructured":"Leszek Gasieniec , Marek Karpinski , Wojciech Plandowski , and Wojciech Rytter . 1996 . Efficient algorithms for Lempel-Ziv encoding (extended abstract) . In Proceedings of the 5th SWAT. 392\u2013403 . Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski, and Wojciech Rytter. 1996. Efficient algorithms for Lempel-Ziv encoding (extended abstract). In Proceedings of the 5th SWAT. 392\u2013403."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90135-K"},{"key":"e_1_2_1_35_1","volume-title":"Donald Ervin Knuth, and Oren Patashnik","author":"Graham Ronald L.","year":"1994","unstructured":"Ronald L. Graham , Donald Ervin Knuth, and Oren Patashnik . 1994 . Concrete Mathematics : A Foundation for Computer Science. Addison-Wesley . Ronald L. Graham, Donald Ervin Knuth, and Oren Patashnik. 1994. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley."},{"key":"e_1_2_1_36_1","volume-title":"An Introduction to the Theory of Numbers","author":"Hardy Godfrey Harold","unstructured":"Godfrey Harold Hardy and Edward Maitland Wright . 2008. An Introduction to the Theory of Numbers ( 6 th ed.). Oxford University Press . Godfrey Harold Hardy and Edward Maitland Wright. 2008. An Introduction to the Theory of Numbers (6th ed.). Oxford University Press.","edition":"6"},{"volume-title":"Proceedings of the 7th ALENEX. 141\u2013154","author":"Gregory","key":"e_1_2_1_37_1","unstructured":"Gregory L. Heileman and Wenbin Luo. 2005. How caching affects hashing . In Proceedings of the 7th ALENEX. 141\u2013154 . Gregory L. Heileman and Wenbin Luo. 2005. How caching affects hashing. In Proceedings of the 7th ALENEX. 141\u2013154."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_24"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9836-6"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3418033"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00032-7"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0249"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.1998.672136"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48452-3_1"},{"volume-title":"Art of Computer Programming, Volume 2: Seminumerical Algorithms","author":"Knuth Donald E.","key":"e_1_2_1_46_1","unstructured":"Donald E. Knuth . 1981. Art of Computer Programming, Volume 2: Seminumerical Algorithms . Addison Wesley . Donald E. Knuth. 1981. Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison Wesley."},{"volume-title":"The Art of Computer Programming, Volume 3: Sorting and Searching","author":"Knuth Donald E.","key":"e_1_2_1_47_1","unstructured":"Donald E. Knuth . 1998. The Art of Computer Programming, Volume 3: Sorting and Searching . Addison Wesley . Donald E. Knuth. 1998. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison Wesley."},{"volume-title":"Proceedings of the 26th DCC. 3\u201312","author":"K\u00f6ppl D.","key":"e_1_2_1_48_1","unstructured":"D. K\u00f6ppl and K. Sadakane . 2016. Lempel-Ziv computation in compressed space (LZ-CICS) . In Proceedings of the 26th DCC. 3\u201312 . D. K\u00f6ppl and K. Sadakane. 2016. Lempel-Ziv computation in compressed space (LZ-CICS). In Proceedings of the 26th DCC. 3\u201312."},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 19th SEA (LIPIcs).","author":"K\u00f6ppl Dominik","year":"2020","unstructured":"Dominik K\u00f6ppl , Simon J. Puglisi , and Rajeev Raman . 2020 . Fast and simple compact hashing via bucketing . In Proceedings of the 19th SEA (LIPIcs). Dominik K\u00f6ppl, Simon J. Puglisi, and Rajeev Raman. 2020. Fast and simple compact hashing via bucketing. In Proceedings of the 19th SEA (LIPIcs)."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.csl.2009.12.001"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055501"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71703-4_34"},{"key":"e_1_2_1_53_1","volume-title":"Proceedings of the 25th ESA (LIPIcs)","volume":"87","author":"Maier Tobias","year":"2017","unstructured":"Tobias Maier and Peter Sanders . 2017 . Dynamic space efficient hashing . In Proceedings of the 25th ESA (LIPIcs) , Vol. 87 . 58:1\u201358:14. Tobias Maier and Peter Sanders. 2017. Dynamic space efficient hashing. In Proceedings of the 25th ESA (LIPIcs), Vol. 87. 58:1\u201358:14."},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 17th ACNS (LNCS)","volume":"11464","author":"Migliore Vincent","year":"2019","unstructured":"Vincent Migliore , Beno\u00eet G\u00e9rard , Mehdi Tibouchi , and Pierre-Alain Fouque . 2019 . Masking Dilithium\u2014efficient implementation and side-channel evaluation . In Proceedings of the 17th ACNS (LNCS) , Vol. 11464 . 344\u2013362. Vincent Migliore, Beno\u00eet G\u00e9rard, Mehdi Tibouchi, and Pierre-Alain Fouque. 2019. Masking Dilithium\u2014efficient implementation and side-channel evaluation. In Proceedings of the 17th ACNS (LNCS), Vol. 11464. 344\u2013362."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.26"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.04.002"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00036-4"},{"key":"e_1_2_1_58_1","article-title":"Fully functional static and dynamic succinct trees","volume":"10","author":"Navarro Gonzalo","year":"2014","unstructured":"Gonzalo Navarro and Kunihiko Sadakane . 2014 . Fully functional static and dynamic succinct trees . ACM Trans. Algor. 10 , 3 (2014), 16:1\u201316:39. Gonzalo Navarro and Kunihiko Sadakane. 2014. Fully functional static and dynamic succinct trees. ACM Trans. Algor. 10, 3 (2014), 16:1\u201316:39.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/1087482.1087483"},{"key":"e_1_2_1_60_1","first-page":"1","article-title":"Conversion from RLBWT to LZ77","volume":"128","author":"Nishimoto Takaaki","year":"2019","unstructured":"Takaaki Nishimoto and Yasuo Tabei . 2019 . Conversion from RLBWT to LZ77 . In Proceedings of the CPM (LIPIcs) , Vol. 128. 9: 1 \u2013 9 :12. Takaaki Nishimoto and Yasuo Tabei. 2019. Conversion from RLBWT to LZ77. In Proceedings of the CPM (LIPIcs), Vol. 128. 9:1\u20139:12.","journal-title":"Proceedings of the CPM (LIPIcs)"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.01.014"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/110827831"},{"key":"e_1_2_1_63_1","article-title":"On the -independence required by linear probing and minwise independence","volume":"12","author":"Patrascu Mihai","year":"2016","unstructured":"Mihai Patrascu and Mikkel Thorup . 2016 . On the -independence required by linear probing and minwise independence . ACM Trans. Algor. 12 , 1 (2016), 8:1\u20138:27. Mihai Patrascu and Mikkel Thorup. 2016. On the -independence required by linear probing and minwise independence. ACM Trans. Algor. 12, 1 (2016), 8:1\u20138:27.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2016.30"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054118430025"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-008-9050-3"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109693"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_2_1_69_1","first-page":"1785","article-title":"Packed compact tries: A fast and efficient data structure for online string processing. IEICE","volume":"9","author":"Takagi Takuya","year":"2017","unstructured":"Takuya Takagi , Shunsuke Inenaga , Kunihiko Sadakane , and Hiroki Arimura . 2017 . Packed compact tries: A fast and efficient data structure for online string processing. IEICE Trans. Fundam. Electron., Commun. Comput. Sci. 100-A , 9 (2017), 1785 \u2013 1793 . Takuya Takagi, Shunsuke Inenaga, Kunihiko Sadakane, and Hiroki Arimura. 2017. Packed compact tries: A fast and efficient data structure for online string processing. IEICE Trans. Fundam. Electron., Commun. Comput. Sci. 100-A, 9 (2017), 1785\u20131793.","journal-title":"Trans. Fundam. Electron., Commun. Comput. Sci. 100-A"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1984.1659158"},{"key":"e_1_2_1_71_1","volume-title":"Proceedings of the 25th COLING. 1091\u20131102","author":"Yoshinaga Naoki","year":"2014","unstructured":"Naoki Yoshinaga and Masaru Kitsuregawa . 2014 . A self-adaptive classifier for efficient text-stream processing . In Proceedings of the 25th COLING. 1091\u20131102 . Naoki Yoshinaga and Masaru Kitsuregawa. 2014. A self-adaptive classifier for efficient text-stream processing. In Proceedings of the 25th COLING. 1091\u20131102."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055934"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3481638","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3481638","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:12Z","timestamp":1750193292000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3481638"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,30]]},"references-count":71,"alternative-id":["10.1145\/3481638"],"URL":"https:\/\/doi.org\/10.1145\/3481638","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2021,10,30]]}}}