{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T17:44:26Z","timestamp":1775151866399,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,10,4]],"date-time":"2016-10-04T00:00:00Z","timestamp":1475539200000},"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":["Knowl Inf Syst"],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s10115-016-0999-8","type":"journal-article","created":{"date-parts":[[2016,10,4]],"date-time":"2016-10-04T16:40:12Z","timestamp":1475599212000},"page":"1023-1042","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Compressed double-array tries for string dictionaries supporting fast lookup"],"prefix":"10.1007","volume":"51","author":[{"given":"Shunsuke","family":"Kanda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhiro","family":"Morita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masao","family":"Fuketa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,10,4]]},"reference":[{"issue":"9","key":"999_CR1","doi-asserted-by":"publisher","first-page":"1066","DOI":"10.1109\/32.31365","volume":"15","author":"J Aoe","year":"1989","unstructured":"Aoe J (1989) An efficient digital search algorithm by using a double-array structure. IEEE Trans Softw Eng 15(9):1066\u20131077","journal-title":"IEEE Trans Softw Eng"},{"issue":"9","key":"999_CR2","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1002\/spe.4380220902","volume":"22","author":"J Aoe","year":"1992","unstructured":"Aoe J, Morimoto K (1992) An efficient implementation of trie structures. Softw Pract Exp 22(9):695\u2013721","journal-title":"Softw Pract Exp"},{"key":"999_CR3","doi-asserted-by":"publisher","unstructured":"Arroyuelo D, C\u00e1novas R, Navarro G, Sadakane K (2010) Succinct trees in practice. In: Proceedings of the 11st meeting on algorithm engineering and experimentation (ALENEX), pp. 84\u201397","DOI":"10.1137\/1.9781611972900.9"},{"key":"999_CR4","doi-asserted-by":"publisher","unstructured":"Arz J, Fischer J (2014) LZ-compressed string dictionaries. In: Proceedings of the data compression conference (DCC), pp. 322\u2013331","DOI":"10.1109\/DCC.2014.36"},{"key":"999_CR5","volume-title":"Modern information retrieval","author":"R Baeza-Yates","year":"2011","unstructured":"Baeza-Yates R, Ribeiro-Neto B (2011) Modern information retrieval, 2nd edn. Addison Wesley, Boston","edition":"2"},{"issue":"4","key":"999_CR6","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s10791-008-9048-x","volume":"11","author":"H Bast","year":"2008","unstructured":"Bast H, Mortensen CW, Weber I (2008) Output-sensitive autocompletion search. Inf Retr 11(4):269\u2013286","journal-title":"Inf Retr"},{"issue":"4","key":"999_CR7","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00453-004-1146-6","volume":"43","author":"D Benoit","year":"2005","unstructured":"Benoit D, Demaine ED, Munro JI, Raman R, Raman V, Rao SS (2005) Representing trees of higher degree. Algorithmica 43(4):275\u2013292","journal-title":"Algorithmica"},{"issue":"8","key":"999_CR8","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1002\/spe.587","volume":"34","author":"P Boldi","year":"2004","unstructured":"Boldi P, Codenotti B, Santini M, Vigna S (2004) Ubicrawler: a scalable fully distributed web crawler. Softw Pract Exp 34(8):711\u2013726","journal-title":"Softw Pract Exp"},{"issue":"1","key":"999_CR9","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1016\/j.ipm.2012.08.003","volume":"49","author":"NR Brisaboa","year":"2013","unstructured":"Brisaboa NR, Ladra S, Navarro G (2013) DACs: bringing direct access to variable-length codes. Inf Process Manag 49(1):392\u2013404","journal-title":"Inf Process Manag"},{"key":"999_CR10","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. MIT press, Cambridge","edition":"3"},{"issue":"10","key":"999_CR11","doi-asserted-by":"publisher","first-page":"1027","DOI":"10.1002\/spe.4380211004","volume":"21","author":"JA Dundas","year":"1991","unstructured":"Dundas JA (1991) Implementing dynamic minimal-prefix tries. Softw Pract Exp 21(10):1027\u20131040","journal-title":"Softw Pract Exp"},{"key":"999_CR12","doi-asserted-by":"publisher","unstructured":"Ferragina P, Grossi R, Gupta A, Shah R, Vitter JS (2008) On searching compressed string collections cache-obliviously. In: Proceedings of the 27th symposium on principles of database systems (PODS), ACM, pp. 181\u2013190","DOI":"10.1145\/1376916.1376943"},{"issue":"1","key":"999_CR13","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/1613676.1613680","volume":"57","author":"P Ferragina","year":"2009","unstructured":"Ferragina P, Luccio F, Manzini G, Muthukrishnan S (2009) Compressing and indexing labeled trees, with applications. J ACM 57(1):4","journal-title":"J ACM"},{"issue":"9","key":"999_CR14","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1145\/367390.367400","volume":"3","author":"E Fredkin","year":"1960","unstructured":"Fredkin E (1960) Trie memory. Commun ACM 3(9):490\u2013499","journal-title":"Commun ACM"},{"issue":"5","key":"999_CR15","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1016\/j.ipm.2014.04.004","volume":"50","author":"M Fuketa","year":"2014","unstructured":"Fuketa M, Kitagawa H, Ogawa T, Morita K, Aoe J (2014) Compression of double array structures for fixed length keywords. Inf Process Manag 50(5):796\u2013806","journal-title":"Inf Process Manag"},{"key":"999_CR16","unstructured":"Fuketa M, Morita K, Aoe J (2014) Comparisons of efficient implementations for DAWG. In: Proceedings of the 7th international conference on computer science and information technology (ICCSIT)"},{"key":"999_CR17","unstructured":"Gonz\u00e1lez R, Grabowski S, M\u00e4kinen V, Navarro G (2005) Practical implementation of rank and select queries. In: Poster proceedings of the 4th workshop on experimental and efficient a lgorithms (WEA), pp. 27\u201338"},{"issue":"1","key":"999_CR18","first-page":"3","volume":"19","author":"R Grossi","year":"2014","unstructured":"Grossi R, Ottaviano G (2014) Fast compressed tries through path decompositions. ACM J Exp Algorithm 19(1):3\u20134","journal-title":"ACM J Exp Algorithm"},{"key":"999_CR19","volume-title":"Information retrieval: computational and theoretical aspects","author":"HS Heaps","year":"1978","unstructured":"Heaps HS (1978) Information retrieval: computational and theoretical aspects. Academic Press Inc, Orlando"},{"issue":"4","key":"999_CR20","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1137\/0121057","volume":"21","author":"TC Hu","year":"1971","unstructured":"Hu TC, Tucker AC (1971) Optimal computer search trees and variable-length alphabetical codes. SIAM J Appl Math 21(4):514\u2013532","journal-title":"SIAM J Appl Math"},{"issue":"1","key":"999_CR21","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s10115-015-0873-0","volume":"48","author":"S Kanda","year":"2016","unstructured":"Kanda S, Fuketa M, Morita K, Aoe J (2016) A compression method of double-array structures using linear functions. Knowl Inf Syst 48(1):55\u201380","journal-title":"Knowl Inf Syst"},{"key":"999_CR22","first-page":"315","volume-title":"Proceedings of the 4th international workshop on experimental and efficient algorithms (WEA), LNCS 3503","author":"DK Kim","year":"2005","unstructured":"Kim DK, Na JC, Kim JE, Park K (2005) Efficient implementation of rank and elect functions for succinct representation. Proceedings of the 4th international workshop on experimental and efficient algorithms (WEA), LNCS 3503. Springer, New York, pp 315\u2013327"},{"key":"999_CR23","volume-title":"The art of computer programming, 3: sorting and searching","author":"DE Knuth","year":"1998","unstructured":"Knuth DE (1998) The art of computer programming, 3: sorting and searching, 2nd edn. Addison Wesley, Redwood City","edition":"2"},{"key":"999_CR24","unstructured":"Kudo T, Hanaoka T, Mukai J, Tabata Y, Komatsu H (2011) Efficient dictionary and language model compression for input method editors. In: Proceedings of the 1st workshop on advances in text input methods (WTIM), pp. 19\u201325"},{"key":"999_CR25","unstructured":"Kudo T, Yamamoto K, Matsumoto Y (2004) Applying conditional random fields to Japanese morphological analysis. In: Proceedings of the conference on empirical methods in natural language processing (EMNLP), pp. 230\u2013237"},{"key":"999_CR26","doi-asserted-by":"publisher","unstructured":"Larsson NJ, Moffat A (1999) Offline dictionary-based compression. In: Proceedings of the data compression conference (DCC), pp. 296\u2013305","DOI":"10.1109\/DCC.1999.755679"},{"key":"999_CR27","unstructured":"Maeda A, Mizushima K (2008) A compressed-array representation of automata and its application to programming language (in Japanese). In: Proceedings of the 49th IPSJ programming symposium, pp. 49\u201354"},{"key":"999_CR28","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.is.2015.08.008","volume":"56","author":"MA Mart\u00ednez-Prieto","year":"2016","unstructured":"Mart\u00ednez-Prieto MA, Brisaboa N, C\u00e1novas R, Claude F, Navarro G (2016) Practical compressed string dictionaries. Inf Syst 56:73\u2013108","journal-title":"Inf Syst"},{"issue":"1","key":"999_CR29","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1002\/1097-024X(200101)31:1<43::AID-SPE356>3.0.CO;2-R","volume":"31","author":"K Morita","year":"2001","unstructured":"Morita K, Fuketa M, Yamakawa Y, Aoe J (2001) Fast insertion methods of a double-array structure. Softw Pract Exp 31(1):43\u201365","journal-title":"Softw Pract Exp"},{"issue":"3","key":"999_CR30","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"JI Munro","year":"2001","unstructured":"Munro JI, Raman V (2001) Succinct representation of balanced parentheses and static trees. SIAM J Comput 31(3):762\u2013776","journal-title":"SIAM J Comput"},{"issue":"3","key":"999_CR31","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/2601073","volume":"10","author":"G Navarro","year":"2014","unstructured":"Navarro G, Sadakane K (2014) Fully functional static and dynamic succinct trees. ACM Trans Algorithms 10(3):16","journal-title":"ACM Trans Algorithms"},{"key":"999_CR32","doi-asserted-by":"publisher","unstructured":"Okanohara D, Sadakane K (2007) Practical entropy-compressed rank\/select dictionary. In: Proceedings of the 9th meeting on algorithm engineering and expermiments (ALENEX), pp. 60\u201370","DOI":"10.1137\/1.9781611972870.6"},{"issue":"13","key":"999_CR33","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1002\/spe.545","volume":"33","author":"M Oono","year":"2003","unstructured":"Oono M, Atlam ES, Fuketa M, Morita K, Aoe J (2003) A fast and compact elimination method of empty elements from a double-array structure. Softw Pract Exp 33(13):1229\u20131249","journal-title":"Softw Pract Exp"},{"key":"999_CR34","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-072-8","volume-title":"A concise introduction to data compression","author":"D Salomon","year":"2008","unstructured":"Salomon D (2008) A concise introduction to data compression. Springer, London"},{"issue":"3","key":"999_CR35","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1093\/comjnl\/42.3.193","volume":"42","author":"HE Williams","year":"1999","unstructured":"Williams HE, Zobel J (1999) Compressing integers for fast file access. Comput J 42(3):193\u2013201","journal-title":"Comput J"},{"key":"999_CR36","volume-title":"Managing gigabytes: compressing and indexing documents and images","author":"IH Witten","year":"1999","unstructured":"Witten IH, Moffat A, Bell TC (1999) Managing gigabytes: compressing and indexing documents and images. Morgan Kaufmann, San Francisco"},{"key":"999_CR37","doi-asserted-by":"crossref","unstructured":"Yasuhara M, Tanaka T, Norimatsu J, Yamamoto M (2013) An efficient language model using double-array structures. In: Proceedings of the conference on empirical methods in natural language processing (EMNLP), pp. 222\u2013232","DOI":"10.18653\/v1\/D13-1023"},{"key":"999_CR38","doi-asserted-by":"publisher","unstructured":"Yata S, Morita K, Fuketa M, Aoe J (2008) Fast string matching with space-efficient word graphs. In: Proceedings of the 4th international conference on innovations in information technology (IIT), pp. 79\u201383","DOI":"10.1109\/INNOVATIONS.2008.4781726"},{"issue":"5","key":"999_CR39","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1002\/spe.778","volume":"37","author":"S Yata","year":"2007","unstructured":"Yata S, Oono M, Morita K, Fuketa M, Aoe J (2007) An efficient deletion method for a minimal prefix double array. Softw Pract Exp 37(5):523\u2013534","journal-title":"Softw Pract Exp"},{"issue":"1","key":"999_CR40","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/j.ipm.2006.04.004","volume":"43","author":"S Yata","year":"2007","unstructured":"Yata S, Oono M, Morita K, Fuketa M, Sumitomo T, Aoe J (2007) A compact static double-array keeping character codes. Inf Process Manag 43(1):237\u2013247","journal-title":"Inf Process Manag"},{"key":"999_CR41","doi-asserted-by":"publisher","unstructured":"Yata S, Oono M, Morita K, Sumitomo T, Aoe J (2006) Double-array compression by pruning twin leaves and unifying common suffixes. In: Proceedings of the 1st international conference on computing and informatics (ICOCI), pp. 1\u20134","DOI":"10.1109\/ICOCI.2006.5276476"},{"key":"999_CR42","unstructured":"Yoshinaga N, Kitsuregawa M (2014) A self-adaptive classifier for efficient text-stream processing. In: Proceedings of the 24th international conference on computational linguistics (COLING), pp. 1091\u20131102"},{"issue":"5","key":"999_CR43","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J Ziv","year":"1978","unstructured":"Ziv J, Lempel A (1978) Compression of individual sequences via variable-rate coding. IEEE Trans Inf Theory 24(5):530\u2013536","journal-title":"IEEE Trans Inf Theory"}],"container-title":["Knowledge and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10115-016-0999-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-016-0999-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10115-016-0999-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T22:41:21Z","timestamp":1749595281000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10115-016-0999-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,4]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["999"],"URL":"https:\/\/doi.org\/10.1007\/s10115-016-0999-8","relation":{},"ISSN":["0219-1377","0219-3116"],"issn-type":[{"value":"0219-1377","type":"print"},{"value":"0219-3116","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,4]]}}}