{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:17Z","timestamp":1760202737576},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2017,7,26]],"date-time":"2017-07-26T00:00:00Z","timestamp":1501027200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s00453-017-0348-7","type":"journal-article","created":{"date-parts":[[2017,7,26]],"date-time":"2017-07-26T13:43:34Z","timestamp":1501076614000},"page":"2012-2047","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Lempel\u2013Ziv-78 Compressed String Dictionaries"],"prefix":"10.1007","volume":"80","author":[{"given":"Julian","family":"Arz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Fischer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,26]]},"reference":[{"issue":"3","key":"348_CR1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. J. Mol. Biol. 215(3), 403\u2013410 (1990)","journal-title":"J. Mol. Biol."},{"issue":"7","key":"348_CR2","doi-asserted-by":"crossref","first-page":"1070","DOI":"10.1016\/j.ic.2011.03.001","volume":"209","author":"D Arroyuelo","year":"2011","unstructured":"Arroyuelo, D., Navarro, G.: Space-efficient construction of Lempel\u2013Ziv compressed text indexes. Inf. Comput. 209(7), 1070\u20131102 (2011)","journal-title":"Inf. Comput."},{"issue":"1\u20132","key":"348_CR3","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1007\/s00453-010-9443-8","volume":"62","author":"D Arroyuelo","year":"2012","unstructured":"Arroyuelo, D., Navarro, G., Sadakane, K.: Stronger Lempel\u2013Ziv based compressed text indexing. Algorithmica 62(1\u20132), 54\u2013101 (2012)","journal-title":"Algorithmica"},{"key":"348_CR4","doi-asserted-by":"crossref","unstructured":"Arz, J., Fischer, J.: LZ-compressed string dictionaries. In: Proceedings of the DCC, pp. 322\u2013331. IEEE Press (2014)","DOI":"10.1109\/DCC.2014.36"},{"issue":"4","key":"348_CR5","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/2629339","volume":"11","author":"D Belazzougui","year":"2015","unstructured":"Belazzougui, D., Navarro, G.: Optimal lower and upper bounds for representing sequences. ACM Trans. Algorithms 11(4), 31 (2015)","journal-title":"ACM Trans. Algorithms"},{"issue":"8","key":"348_CR6","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1002\/spe.587","volume":"34","author":"P Boldi","year":"2004","unstructured":"Boldi, P., Codenotti, B., Santini, M., Vigna, S.: Ubicrawler: a scalable fully distributed web crawler. Softw. Pract. Exp. 34(8), 711\u2013726 (2004)","journal-title":"Softw. Pract. Exp."},{"key":"348_CR7","unstructured":"B\u00f6ttcher, S., Lohrey, M., Maneth, S., Rytter, W. (eds): Abstracts collection\u2014structure-based compression of complex massive data. No. 08261 in Dagstuhl Seminar Proceedings, Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Germany (2008)"},{"key":"348_CR8","doi-asserted-by":"crossref","unstructured":"Brisaboa, N.R., C\u00e1novas, R., Claude, F., Mart\u00ednez-Prieto, M.A., Navarro, G.: Compressed string dictionaries. In: Proceedings of the 10th International Symposium on Experimental Algorithms (SEA 2011), Springer, Lecture Notes in Computer Science, vol. 6630, pp. 136\u2013147 (2011)","DOI":"10.1007\/978-3-642-20662-7_12"},{"key":"348_CR9","unstructured":"Clark, D.R.: Compact Pat Trees. PhD thesis, Waterloo, ON, Canada (1998)"},{"key":"348_CR10","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Venturini, R.: Compressed permuterm index. In: Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2007), ACM, pp. 535\u2013542 (2007)","DOI":"10.1145\/1277741.1277833"},{"key":"348_CR11","doi-asserted-by":"crossref","unstructured":"Fischer, J., Gawrychowski, P.: Alphabet-dependent string searching with wexponential search trees. In: Proceedings of the CPM, Springer, LNCS, vol. 9133, pp. 160\u2013171 (2015)","DOI":"10.1007\/978-3-319-19929-0_14"},{"key":"348_CR12","doi-asserted-by":"crossref","unstructured":"Fischer, J., I, T., K\u00f6ppl, D.: Lempel Ziv computation in small space (LZ-CISS). In: Proceedings of the CPM, Springer, LNCS, vol. 9133, pp. 172\u2013184 (2015)","DOI":"10.1007\/978-3-319-19929-0_15"},{"issue":"3","key":"348_CR13","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"ML Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with $${O}(1)$$ O ( 1 ) worst case access time. J. ACM 31(3), 538\u2013544 (1984)","journal-title":"J. ACM"},{"key":"348_CR14","doi-asserted-by":"crossref","unstructured":"Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: Proceedings of the SEA, Springer, LNCS, vol. 8504, pp. 326\u2013337 (2014)","DOI":"10.1007\/978-3-319-07959-2_28"},{"key":"348_CR15","first-page":"3","volume":"19","author":"R Grossi","year":"2014","unstructured":"Grossi, R., Ottaviano, G.: Fast compressed tries through path decompositions. ACM J. Exp. Algorithmics 19, 3\u20134 (2014)","journal-title":"ACM J. Exp. Algorithmics"},{"key":"348_CR16","unstructured":"Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithm (SODA 2003), ACM\/SIAM, pp. 841\u2013850 (2003)"},{"issue":"4","key":"348_CR17","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1137\/0121057","volume":"21","author":"TC Hu","year":"1971","unstructured":"Hu, T.C., Tucker, A.C.: Optimal computer search trees and variable-length alphabetical codes. SIAM J. Appl. Math. 21(4), 514\u2013532 (1971)","journal-title":"SIAM J. Appl. Math."},{"issue":"9","key":"348_CR18","doi-asserted-by":"crossref","first-page":"1098","DOI":"10.1109\/JRPROC.1952.273898","volume":"40","author":"DA Huffman","year":"1952","unstructured":"Huffman, D.A.: A method for the construction of minimum-redundancy codes. Proc. IRE 40(9), 1098\u20131101 (1952)","journal-title":"Proc. IRE"},{"key":"348_CR19","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS 1989), IEEE Computer Society, pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"issue":"4","key":"348_CR20","doi-asserted-by":"crossref","first-page":"969","DOI":"10.1007\/s00453-013-9836-6","volume":"71","author":"J Jansson","year":"2015","unstructured":"Jansson, J., Sadakane, K., Sung, W.: Linked dynamic tries with applications to LZ-compression in sublinear time and space. Algorithmica 71(4), 969\u2013988 (2015)","journal-title":"Algorithmica"},{"key":"348_CR21","volume-title":"Sorting and Searching, The Art of Computer Programming","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: Sorting and Searching, The Art of Computer Programming, vol. 3, 2nd edn. Addison Wesley, Reading (1998)","edition":"2"},{"issue":"3","key":"348_CR22","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1137\/S0097539797331105","volume":"29","author":"SR Kosaraju","year":"1999","unstructured":"Kosaraju, S.R., Manzini, G.: Compression of low entropy strings with Lempel\u2013Ziv algorithms. SIAM J. Comput. 29(3), 893\u2013911 (1999)","journal-title":"SIAM J. Comput."},{"key":"348_CR23","doi-asserted-by":"crossref","unstructured":"Larsson, N.J., Moffat, A.: Offline dictionary-based compression. In: Proceedings of the Data Compression Conference (DCC 1999), IEEE Computer Society, pp. 296\u2013305 (1999)","DOI":"10.1109\/DCC.1999.755679"},{"issue":"6","key":"348_CR24","first-page":"22","volume":"3","author":"S Maneth","year":"2013","unstructured":"Maneth, S., Navarro, G.: Indexes and computation over compressed structured data (Dagstuhl Seminar 13232). Dagstuhl Rep. 3(6), 22\u201337 (2013)","journal-title":"Dagstuhl Rep."},{"key":"348_CR25","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.is.2015.08.008","volume":"56","author":"MA Mart\u00ednez-Prieto","year":"2016","unstructured":"Mart\u00ednez-Prieto, M.A., Brisaboa, N.R., C\u00e1novas, R., Claude, F., Navarro, G.: Practical compressed string dictionaries. Inf. Syst. 56, 73\u2013108 (2016)","journal-title":"Inf. Syst."},{"key":"348_CR26","volume-title":"Algorithms and Data Structures: The Basic Toolbox","author":"K Mehlhorn","year":"2008","unstructured":"Mehlhorn, K., Sanders, P.: Algorithms and Data Structures: The Basic Toolbox. Springer, Berlin (2008)"},{"key":"348_CR27","unstructured":"M\u00fcller, I., Ratsch, C., F\u00e4rber, F.: Adaptive string dictionary compression in in-memory column-store database systems. In: Proceedings of the 17th International Conference on Extending Database Technology (EDBT), OpenProceedings.org, pp. 283\u2013294 (2014)"},{"key":"348_CR28","doi-asserted-by":"crossref","unstructured":"Munro, J.I.: Tables. In: Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 1996), Springer, Lecture Notes in Computer Science, vol. 1180, pp. 37\u201342 (1996)","DOI":"10.1007\/3-540-62034-6_35"},{"key":"348_CR29","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1216370.1216372","volume":"39","author":"G Navarro","year":"2007","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Comput. Surv. 39, 2 (2007)","journal-title":"ACM Comput. Surv."},{"key":"348_CR30","doi-asserted-by":"crossref","unstructured":"Navarro, G., Providel, E.: Fast, small, simple rank\/select on bitmaps. In: Proceedings of the SEA, Springer, LNCS, vol. 7276, pp. 295\u2013306 (2012)","DOI":"10.1007\/978-3-642-30850-5_26"},{"issue":"4","key":"348_CR31","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/s10791-008-9050-3","volume":"11","author":"LMS Russo","year":"2008","unstructured":"Russo, L.M.S., Oliveira, A.L.: A compressed self-index using a Ziv\u2013Lempel dictionary. Inf. Retr. 11(4), 359\u2013388 (2008)","journal-title":"Inf. Retr."},{"issue":"4","key":"348_CR32","first-page":"53","volume":"7","author":"LMS Russo","year":"2011","unstructured":"Russo, L.M.S., Navarro, G., Oliveira, A.L.: Fully compressed suffix trees. ACM Trans. Algorithms 7(4), 53 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"348_CR33","doi-asserted-by":"crossref","unstructured":"Vigna, S.: Broadword implementation of rank\/select queries. In: Proceedings of the 7th International Workshop on Experimental Algorithms (WEA 2008), Springer, Lecture Notes in Computer Science, vol. 5038, pp. 154\u2013168 (2008)","DOI":"10.1007\/978-3-540-68552-4_12"},{"issue":"3","key":"348_CR34","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1093\/comjnl\/42.3.193","volume":"42","author":"HE Williams","year":"1999","unstructured":"Williams, H.E., Zobel, J.: Compressing integers for fast file access. Comput. J. 42(3), 193\u2013201 (1999)","journal-title":"Comput. J."},{"key":"348_CR35","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","author":"IH Witten","year":"1999","unstructured":"Witten, I.H., Moffat, A., Bell, T.C.: Managing Gigabytes: Compressing and Indexing Documents and Images, 2nd edn. Morgan Kaufmann, San Francisco (1999)","edition":"2"},{"key":"348_CR36","unstructured":"Yata, S.: Dictionary compression using nested prefix\/Patricia tries (in Japanese). In: Proceedings of the 17th Annual Meeting on Natural Language Processing (NLP2001), pp. 576\u2013578 (2011). http:\/\/www.anlp.jp\/proceedings\/annual_meeting\/2011\/pdf_dir\/F2-6.pdf"},{"key":"348_CR37","doi-asserted-by":"crossref","unstructured":"Zhou, D., Andersen, D.G., Kaminsky, M.: Space-efficient, high-performance rank and select structures on uncompressed bit sequences. In: Proceedings of the SEA, Springer, LNCS, vol. 7933, pp. 151\u2013163 (2013)","DOI":"10.1007\/978-3-642-38527-8_15"},{"issue":"5","key":"348_CR38","doi-asserted-by":"crossref","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. Inf. Theory 24(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0348-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0348-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0348-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,1]],"date-time":"2019-10-01T13:05:13Z","timestamp":1569935113000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0348-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,26]]},"references-count":38,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["348"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0348-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7,26]]}}}