{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:26:48Z","timestamp":1725496008232},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540770497"},{"type":"electronic","value":"9783540770503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-77050-3_35","type":"book-chapter","created":{"date-parts":[[2007,11,26]],"date-time":"2007-11-26T08:39:22Z","timestamp":1196066362000},"page":"424-435","source":"Crossref","is-referenced-by-count":4,"title":["Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space"],"prefix":"10.1007","author":[{"given":"Jesper","family":"Jansson","sequence":"first","affiliation":[]},{"given":"Kunihiko","family":"Sadakane","sequence":"additional","affiliation":[]},{"given":"Wing-Kin","family":"Sung","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"35_CR1","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0020-0190(93)90068-K","volume":"46","author":"A. Andersson","year":"1993","unstructured":"Andersson, A., Nilsson, S.: Improved behaviour of tries by adaptive branching. Information Processing Letters\u00a046, 295\u2013300 (1993)","journal-title":"Information Processing Letters"},{"issue":"9","key":"35_CR2","doi-asserted-by":"publisher","first-page":"1066","DOI":"10.1109\/32.31365","volume":"15","author":"J. Aoe","year":"1989","unstructured":"Aoe, J.: An efficient digital search algorithm by using a double array structure. IEEE Transactions on Software Engineering\u00a015(9), 1066\u20131077 (1989)","journal-title":"IEEE Transactions on Software Engineering"},{"key":"35_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11602613_113","volume-title":"Algorithms and Computation","author":"D. Arroyuelo","year":"2005","unstructured":"Arroyuelo, D., Navarro, G.: Space-efficient construction of LZ-index. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, Springer, Heidelberg (2005)"},{"key":"35_CR4","doi-asserted-by":"crossref","unstructured":"Beame, P., Fich, F.E.: Optimal bounds for the predecessor problem. In: Proc. of the 31\n                    st\n                   Annual ACM Symposium on the Theory of Computing (STOC 1999), pp. 295\u2013304 (1999)","DOI":"10.1145\/301250.301323"},{"issue":"2","key":"35_CR5","first-page":"64","volume":"19","author":"R.P. Brent","year":"1987","unstructured":"Brent, R.P.: A linear algorithm for data compression. Australian Computer Journal\u00a019(2), 64\u201368 (1987)","journal-title":"Australian Computer Journal"},{"key":"35_CR6","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1002\/rsa.20067","volume":"27","author":"L. Devroye","year":"2005","unstructured":"Devroye, L., Szpankowski, W.: Probabilistic behavior of asymmetric level compressed tries. Random Structures and Algorithms\u00a027, 185\u2013200 (2005)","journal-title":"Random Structures and Algorithms"},{"key":"35_CR7","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1145\/367390.367400","volume":"3","author":"E. Fredkin","year":"1960","unstructured":"Fredkin, E.: Trie memory. Communications of the ACM\u00a03, 490\u2013500 (1960)","journal-title":"Communications of the ACM"},{"key":"35_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-540-27801-6_12","volume-title":"Combinatorial Pattern Matching","author":"R.F. Geary","year":"2004","unstructured":"Geary, R.F., Rahman, N., Raman, R., Raman, V.: A simple optimal representation for balanced parentheses. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 159\u2013172. Springer, Heidelberg (2004)"},{"key":"35_CR9","doi-asserted-by":"crossref","unstructured":"Hagerup, T.: Sorting and searching on the word ram. In: Proceedings of Symposium on Theory Aspects of Computer Science, pp. 366\u2013398 (1998)","DOI":"10.1007\/BFb0028575"},{"key":"35_CR10","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms and Computation","author":"W.-K. Hon","year":"2003","unstructured":"Hon, W.-K., Lam, T.-W., Sadakane, K., Sung, W.-K.: Constructing compressed suffix arrays with large alphabets. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol.\u00a02906, Springer, Heidelberg (2003)"},{"issue":"4","key":"35_CR11","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"D.R. Morrison","year":"1968","unstructured":"Morrison, D.R.: PATRICIA - Practical Algorithm To Retrieve Information Coded In Alphanumeric. Journal of the ACM\u00a015(4), 514\u2013534 (1968)","journal-title":"Journal of the ACM"},{"issue":"3","key":"35_CR12","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"J.I. Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM Journal on Computing\u00a031(3), 762\u2013776 (2001)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"35_CR13","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/S1570-8667(03)00066-2","volume":"2","author":"G. Navarro","year":"2004","unstructured":"Navarro, G.: Indexing text using the Ziv-Lempel trie. Journal of Discrete Algorithmcs (JDA)\u00a02(1), 87\u2013114 (2004)","journal-title":"Journal of Discrete Algorithmcs (JDA)"},{"issue":"6","key":"35_CR14","doi-asserted-by":"publisher","first-page":"1083","DOI":"10.1109\/49.772439","volume":"17","author":"S. Nilsson","year":"1999","unstructured":"Nilsson, S., Karlsson, G.: IP-address lookup using lc-tries. Journal on Selected Areas in Communications IEEE\u00a017(6), 1083\u20131092 (1999)","journal-title":"Journal on Selected Areas in Communications IEEE"},{"issue":"1","key":"35_CR15","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. Journal of ACM\u00a028(1), 16\u201324 (1981)","journal-title":"Journal of ACM"},{"key":"35_CR16","first-page":"1230","volume-title":"Proc. ACM-SIAM SODA","author":"K. Sadakane","year":"2006","unstructured":"Sadakane, K., Grossi, R.: Squeezing Succinct Data Structures into Entropy Bounds. In: Proc. ACM-SIAM SODA, pp. 1230\u20131239. ACM Press, New York (2006)"},{"key":"35_CR17","doi-asserted-by":"crossref","unstructured":"Welch, T.A.: A technique for high-performance data compression. IEEE Computer, 8\u201319 (1984)","DOI":"10.1109\/MC.1984.1659158"},{"key":"35_CR18","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D.E. Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst case range queries are possible in space \u03b8(n). Information Processing Letters\u00a017, 81\u201384 (1983)","journal-title":"Information Processing Letters"},{"key":"35_CR19","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/0022-0000(84)90020-5","volume":"28","author":"D.E. Willard","year":"1984","unstructured":"Willard, D.E.: New trie data structures which support very fast search operations. Journal of Computer and System Sciences\u00a028, 379\u2013394 (1984)","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"35_CR20","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"IT-24","author":"J. Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory\u00a0IT-24(5), 530\u2013536 (1978)","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77050-3_35.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:55:56Z","timestamp":1619520956000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77050-3_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540770497","9783540770503"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77050-3_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}