{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T07:57:59Z","timestamp":1775116679026,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T00:00:00Z","timestamp":1775088000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T00:00:00Z","timestamp":1775088000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"JSPS"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1007\/s00224-026-10262-1","type":"journal-article","created":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T07:14:51Z","timestamp":1775114091000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["NP-Completeness on the Length of Double-Arrays and the Sparse Matrix Problem with at Least Logarithmic Alphabets\/Widths"],"prefix":"10.1007","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6856-5185","authenticated-orcid":false,"given":"Hideo","family":"Bannai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6964-6182","authenticated-orcid":false,"given":"Keisuke","family":"Goto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5462-122X","authenticated-orcid":false,"given":"Shunsuke","family":"Kanda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8721-4444","authenticated-orcid":false,"given":"Dominik","family":"K\u00f6ppl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,2]]},"reference":[{"key":"10262_CR1","unstructured":"Aho, A.V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools. Addison-Wesley series in computer science \/ World student series edition. Addison-Wesley (1986). ISBN 0-201-10088-6. https:\/\/www.worldcat.org\/oclc\/12285707"},{"issue":"9","key":"10262_CR2","doi-asserted-by":"publisher","first-page":"1066","DOI":"10.1109\/32.31365","volume":"15","author":"J-I Aoe","year":"1989","unstructured":"Aoe, J.-I.: An efficient digital search algorithm by using a double-array structure. IEEE Trans. Softw. Eng. 15(9), 1066\u20131077 (1989). https:\/\/doi.org\/10.1109\/32.31365","journal-title":"IEEE Trans. Softw. Eng."},{"issue":"3","key":"10262_CR3","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1109\/69.506713","volume":"8","author":"J Aoe","year":"1996","unstructured":"Aoe, J., Morimoto, K., Shishibori, M., Park, K.-H.: A trie compaction algorithm for a large set of keys. IEEE Trans. Knowl. Data Eng. 8(3), 476\u2013491 (1996)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"10262_CR4","unstructured":"Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability, vol. 185 of Frontiers in Artificial Intelligence and Applications (2009). IOS Press. ISBN 978-1-58603-929-5"},{"issue":"1","key":"10262_CR5","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1016\/j.ipm.2012.08.003","volume":"49","author":"NR Brisaboa","year":"2013","unstructured":"Brisaboa, N.R., Ladra, S., Navarro, G.: DACs: Bringing direct access to variable-length codes. Inf. Process. Manage. 49(1), 392\u2013404 (2013). https:\/\/doi.org\/10.1016\/j.ipm.2012.08.003","journal-title":"Inf. Process. Manage."},{"issue":"1","key":"10262_CR6","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0164-1212(95)00086-0","volume":"35","author":"C-C Chang","year":"1996","unstructured":"Chang, C.-C., Buehrer, D.J.: An improvement to Ziegler\u2019s sparse matrix compression algorithm. J. Syst. Softw. 35(1), 67\u201371 (1996). https:\/\/doi.org\/10.1016\/0164-1212(95)00086-0","journal-title":"J. Syst. Softw."},{"issue":"1","key":"10262_CR7","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1002\/SPE.4380210104","volume":"21","author":"C-C Chang","year":"1991","unstructured":"Chang, C.-C., Tzong-Chen, W.: A letter-oriented perfect hashing scheme based upon sparse table compression. Softw. Pract. Exp. 21(1), 35\u201349 (1991). https:\/\/doi.org\/10.1002\/SPE.4380210104","journal-title":"Softw. Pract. Exp."},{"issue":"4","key":"10262_CR8","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/BF01990533","volume":"33","author":"C-C Chang","year":"1993","unstructured":"Chang, C.-C., Kowng, H.-C., Tzong-Chen, W.: A refinement of a compression-oriented addressing scheme. BIT Numer. Math. 33(4), 529\u2013535 (1993). https:\/\/doi.org\/10.1007\/BF01990533","journal-title":"BIT Numer. Math."},{"key":"10262_CR9","doi-asserted-by":"publisher","unstructured":"Dillinger, P.C., H\u00fcbschle-Schneider, L., Sanders, P., Walzer, S.: Fast succinct retrieval and approximate membership using ribbon. In: Proceedings of SEA, vol. 233 of LIPIcs, pp. 4:1\u20134:20 (2022). https:\/\/doi.org\/10.4230\/LIPICS.SEA.2022.4","DOI":"10.4230\/LIPICS.SEA.2022.4"},{"issue":"2","key":"10262_CR10","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/321812.321820","volume":"21","author":"P Elias","year":"1974","unstructured":"Elias, P.: Efficient storage and retrieval by content and address of static files. J. ACM 21(2), 246\u2013260 (1974). https:\/\/doi.org\/10.1145\/321812.321820","journal-title":"J. ACM"},{"key":"10262_CR11","unstructured":"Even, S., Lichtenstein, D.I., Shiloah, Y.: Remarks on Ziegler\u2019s method for matrix compression. unpublished (1977)"},{"issue":"9","key":"10262_CR12","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1145\/367390.367400","volume":"3","author":"E Fredkin","year":"1960","unstructured":"Fredkin, E.: Trie memory. Commun. ACM 3(9), 490\u2013499 (1960). https:\/\/doi.org\/10.1145\/367390.367400","journal-title":"Commun. ACM"},{"issue":"8","key":"10262_CR13","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1080\/00207160410001714600","volume":"81","author":"M Fuketa","year":"2004","unstructured":"Fuketa, M., Morita, K., Sumitomo, T., Kashiji, S., Atlam, E., Aoe, J.-I.: A new compression method of double array for compact dictionaries. Int. J. Comput. Math. 81(8), 943\u2013953 (2004)","journal-title":"Int. J. Comput. Math."},{"key":"10262_CR14","unstructured":"Gallant, A.: aho-corasick: A fast implementation of Aho-Corasick in Rust (0.7.18). (2021). https:\/\/github.com\/BurntSushi\/aho-corasick"},{"issue":"1","key":"10262_CR15","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/0022-0000(80)90004-5","volume":"20","author":"J Gallant","year":"1980","unstructured":"Gallant, J., Maier, D., Storer, J.A.: On finding minimal length superstrings. J. Comput. Syst. Sci. 20(1), 50\u201358 (1980). https:\/\/doi.org\/10.1016\/0022-0000(80)90004-5","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"10262_CR16","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976). https:\/\/doi.org\/10.1016\/0304-3975(76)90059-1","journal-title":"Theor. Comput. Sci."},{"key":"10262_CR17","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. A Series of books in the mathematical sciences. Bell Laboratories (1979)"},{"key":"10262_CR18","first-page":"1","volume":"19","author":"R Grossi","year":"2015","unstructured":"Grossi, R., Ottaviano, G.: Fast compressed tries through path decompositions. J. Exp. Algorithmics (JEA) 19, 1\u20131 (2015)","journal-title":"J. Exp. Algorithmics (JEA)"},{"key":"10262_CR19","doi-asserted-by":"publisher","unstructured":"Ignatiev, A., Morgado, A., Marques-Silva, J.: PySAT: A python toolkit for prototyping with SAT oracles. In: Proceedings of SAT, vol. 10929 of LNCS, pp. 428\u2013437 (2018). https:\/\/doi.org\/10.1007\/978-3-319-94144-8_26","DOI":"10.1007\/978-3-319-94144-8_26"},{"issue":"1","key":"10262_CR20","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.: A compression method of double-array structures using linear functions. Knowl. Inf. Syst. 48(1), 55\u201380 (2016). https:\/\/doi.org\/10.1007\/S10115-015-0873-0","journal-title":"Knowl. Inf. Syst."},{"issue":"3","key":"10262_CR21","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.1007\/s10115-016-0999-8","volume":"51","author":"S Kanda","year":"2017","unstructured":"Kanda, S., Morita, K., Fuketa, M.: Compressed double-array tries for string dictionaries supporting fast lookup. Knowl. Inf. Syst. 51(3), 1023\u20131042 (2017). https:\/\/doi.org\/10.1007\/s10115-016-0999-8","journal-title":"Knowl. Inf. Syst."},{"issue":"1","key":"10262_CR22","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1002\/spe.2516","volume":"48","author":"S Kanda","year":"2018","unstructured":"Kanda, S., Fujita, Y., Morita, K., Fuketa, M.: Practical rearrangement methods for dynamic double-array dictionaries. Softw., Pract. Exper. 48(1), 65\u201383 (2018). https:\/\/doi.org\/10.1002\/spe.2516","journal-title":"Softw., Pract. Exper."},{"issue":"6","key":"10262_CR23","doi-asserted-by":"publisher","first-page":"1332","DOI":"10.1002\/spe.3190","volume":"53","author":"S Kanda","year":"2023","unstructured":"Kanda, S., Akabe, K., Oda, Y.: Engineering faster double-array Aho-Corasick automata. Softw. Practi Experience 53(6), 1332\u20131361 (2023). https:\/\/doi.org\/10.1002\/spe.3190","journal-title":"Softw. Practi Experience"},{"key":"10262_CR24","unstructured":"K\u00f6ppl, D., Limouzy, V., Marino, A., Olbrich, J., Punzi, G., Uno, T.: Sparse matrix compression of matrices with double logarithmic widths. Technical Report 28, Local Proceedings of the LA Symposium Winter 2025 (2026)"},{"key":"10262_CR25","unstructured":"Liu, H., Nuo, M., Ma, L.-L., Wu, J., He, Y.: Compression methods by code mapping and code dividing for Chinese dictionary stored in a double-array trie. In: Proceedings of IJCNLP, pp. 1189\u20131197 (2011)"},{"key":"10262_CR26","doi-asserted-by":"publisher","unstructured":"Manea, F., Richardsen, J., Schmid, M.L.: Subsequences with generalised gap constraints: Upper and lower complexity bounds. In: Proceedings of CPM, vol. 296 of LIPIcs, pp. 22:1\u201322:17 (2024). https:\/\/doi.org\/10.4230\/LIPICS.CPM.2024.22","DOI":"10.4230\/LIPICS.CPM.2024.22"},{"issue":"1","key":"10262_CR27","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.-I.: Fast insertion methods of a double-array structure. Softw. Pract. Experience 31(1), 43\u201365 (2001). https:\/\/doi.org\/10.1002\/1097-024x(200101)31:1<43::aid-spe356>3.0.co;2-r","journal-title":"Softw. Pract. Experience"},{"issue":"4","key":"10262_CR28","doi-asserted-by":"publisher","first-page":"27:1","DOI":"10.1145\/2873068","volume":"15","author":"J-Y Norimatsu","year":"2016","unstructured":"Norimatsu, J.-Y., Yasuhara, M., Tanaka, T., Yamamoto, M.: A fast and compact language model implementation using double-array structures. ACM Trans. Asian Low Resour. Lang. Inf. Process. 15(4), 27:1-27:27 (2016). https:\/\/doi.org\/10.1145\/2873068","journal-title":"ACM Trans. Asian Low Resour. Lang. Inf. Process."},{"issue":"13","key":"10262_CR29","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1002\/spe.545","volume":"33","author":"M Oono","year":"2003","unstructured":"Oono, M., Atlam, E.-S., Fuketa, M., Morita, K., Aoe, J.-I.: A fast and compact elimination method of empty elements from a double-array structure. Softw. Pract. Experience 33(13), 1229\u20131249 (2003). https:\/\/doi.org\/10.1002\/spe.545","journal-title":"Softw. Pract. Experience"},{"issue":"12","key":"10262_CR30","doi-asserted-by":"publisher","first-page":"1276","DOI":"10.1109\/43.44508","volume":"8","author":"P Sadayappan","year":"1989","unstructured":"Sadayappan, P., Visvanathan, V.: Efficient sparse matrix factorization for circuit simulation on vector supercomputers. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 8(12), 1276\u20131285 (1989). https:\/\/doi.org\/10.1109\/43.44508","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."},{"key":"10262_CR31","doi-asserted-by":"publisher","unstructured":"Song, X., Salcianu, A., Song, Y., Dopson, D., Zhou, D.: Fast wordpiece tokenization. In: Proceedings of EMNLP, pp. 2089\u20132103 (2021). https:\/\/doi.org\/10.18653\/V1\/2021.EMNLP-MAIN.160","DOI":"10.18653\/V1\/2021.EMNLP-MAIN.160"},{"issue":"11","key":"10262_CR32","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1145\/359168.359175","volume":"22","author":"RE Tarjan","year":"1979","unstructured":"Tarjan, R.E., Yao, A.C.-C.: Storing a sparse table. Commun. ACM 22(11), 606\u2013611 (1979). https:\/\/doi.org\/10.1145\/359168.359175","journal-title":"Commun. ACM"},{"issue":"5","key":"10262_CR33","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.-I.: An efficient deletion method for a minimal prefix double array. Softw. Pract. Experience 37(5), 523\u2013534 (2007a). https:\/\/doi.org\/10.1002\/spe.778","journal-title":"Softw. Pract. Experience"},{"issue":"1","key":"10262_CR34","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.-I.: A compact static double-array keeping character codes. Inf. Process. Manag. 43(1), 237\u2013247 (2007). https:\/\/doi.org\/10.1016\/j.ipm.2006.04.004","journal-title":"Inf. Process. Manag."},{"key":"10262_CR35","doi-asserted-by":"crossref","unstructured":"Yata, S., Morita, K., Fuketa, M., Aoe, J.-I.: Fast string matching with space-efficient word graphs. In: Proceedings of the 4th International Conference on Innovations in Information Technology (IIT), pp. 79\u201383 (2008)","DOI":"10.1109\/INNOVATIONS.2008.4781726"},{"key":"10262_CR36","doi-asserted-by":"publisher","unstructured":"Yoshinaga, N.: Back to patterns: Efficient Japanese morphological analysis with feature-sequence trie. In: Proceedings of ACL, pp. 13\u201323 (2023). https:\/\/doi.org\/10.18653\/V1\/2023.ACL-SHORT.2","DOI":"10.18653\/V1\/2023.ACL-SHORT.2"},{"key":"10262_CR37","unstructured":"Yoshinaga, N., Kitsuregawa, M.: A self-adaptive classifier for efficient text-stream processing. In: Proceedings of COLING, pp. 1091\u20131102 (2014)"},{"key":"10262_CR38","unstructured":"Ziegler, S.F.: Small faster table driven parser. Technical report, Madison Academic Computing Center, University of Wisconsin, unpublished (1977)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10262-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-026-10262-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10262-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T07:14:54Z","timestamp":1775114094000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-026-10262-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10262"],"URL":"https:\/\/doi.org\/10.1007\/s00224-026-10262-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]},"assertion":[{"value":"7 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"23"}}