NP-Completeness for the Space-Optimality of Double-Array Tries
Open accessAbstract
Indexing a set of strings for prefix search or membership queries is a fundamental task with many applications such as information retrieval or database systems. A classic abstract data type for modelling such an index is a trie. Due to the fundamental nature of this problem, it has sparked much interest, leading to a variety of trie implementations with different characteristics. A trie implementation that has been well-used in practice is the double-array (trie) consisting of merely two integer arrays. While a traversal takes constant time per node visit, the needed space consumption in computer words can be as large as the product of the number of nodes and the alphabet size. Despite that several heuristics have been proposed on lowering the space requirements, we are unaware of any theoretical guarantees. In this paper, we study the decision problem whether there exists a double-array of a given size. To this end, we first draw a connection to the sparse matrix compression problem, which makes our problem NP-complete for alphabet sizes linear to the number of nodes. We further propose a reduction from the restricted directed Hamiltonian path problem, leading to NP-completeness even for logarithmic-sized alphabets.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Trie-size minimisation under a single global attribute permutation is classical and NP-hard, including for double-array tries.
“Trie-size minimisation under a single global attribute permutation is classical and NP-hard, including for double-array tries [13]; per-record freedom is what the RAG setting hands you and what makes MPT a different object.”
From Prefix Sharing Is a Sorting Problem (2026) · cites this paper as [13]
The Abstract reports that deciding whether a double-array trie has a representation of a given size is NP-complete. The Introduction describes the optimization as choosing a space-saving layout for a trie, not minimizing trie size under a single global attribute permutation. The cited paper therefore supports the double-array hardness point but not the specified permutation problem. (LLM, conf=0.88)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 16
- Jun'ichi Aoe. An efficient digital search algorithm by using a double-array structure. IEEE Transactions on Software Engineering, 15(9):1066-1077, 1989.
- Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors. Handbook of Satisfiability, volume 185 of Frontiers in Artificial Intelligence and Applications. IOS Press, 2009.
- Jan Daciuk, Jakub Piskorski, and Strahil Ristov. Natural language dictionaries implemented as finite automata. In Carlos Martín-Vide, editor, Scientific Applications Of Language Methods, volume 2, chapter 4. World Scientific, 2010.
- Edward Fredkin. Trie memory. Communications of the ACM, 3(9):490-499, 1960.
- John Gallant, David Maier, and James A. Storer. On finding minimal length superstrings. Journal of Computer and System Sciences, 20(1):50-58, 1980.
- Shunsuke Kanda, Koichi Akabe, and Yusuke Oda. Engineering faster double-array Aho- Corasick automata. Software: Practice and Experience, 53(6):1332-1361, 2023.
- Shunsuke Kanda, Yuma Fujita, Kazuhiro Morita, and Masao Fuketa. Practical rearrangement methods for dynamic double-array dictionaries. Software: Practice and Experience, 48(1):65-83, 2018.
- Shunsuke Kanda, Masao Fuketa, Kazuhiro Morita, and Jun-ichi Aoe. A compression method of double-array structures using linear functions. Knowl. Inf. Syst., 48(1):55-80, 2016. doi: 10.1007/S10115-015-0873-0. · DOI
- Shunsuke Kanda, Kazuhiro Morita, and Masao Fuketa. Compressed double-array tries for string dictionaries supporting fast lookup. Knowledge and Information Systems, 51(3):1023-1042, 2017.
- Huidan Liu, Minghua Nuo, Long-Long Ma, Jian Wu, and Yeping He. Compression methods by code mapping and code dividing for chinese dictionary stored in a double-array trie. In Proceedings of the 5th International Joint Conference on Natural Language Processing (IJCNLP), pages 1189-1197, 2011.
- Jun'ya Norimatsu, Makoto Yasuhara, Toru Tanaka, and Mikio Yamamoto. A fast and compact language model implementation using double-array structures. ACM Transactions on Asian and Low-Resource Language Information Processing, 15(4):27, 2016.
- Xinying Song, Alex Salcianu, Yang Song, Dave Dopson, and Denny Zhou. Fast wordpiece tokenization. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 2089-2103, 2021.
- Susumu Yata, Masaki Oono, Kazuhiro Morita, Masao Fuketa, Toru Sumitomo, and Jun- ichi Aoe. A compact static double-array keeping character codes. Inf. Process. Manag., 43(1):237-247, 2007. doi:10.1016/j.ipm.2006.04.004. · DOI
- Susumu Yata, Masaki Oono, Kazuhiro Morita, Masao Fuketa, Toru Sumitomo, and Jun'ichi Aoe. A compact static double-array keeping character codes. Information Processing & Management, 43(1):237-247, 2007.
- Naoki Yoshinaga. Back to patterns: Efficient Japanese morphological analysis with feature- sequence trie. In Proc. ACL, pages 13-23, 2023. doi:10.18653/V1/2023.ACL-SHORT.2. · DOI
- Naoki Yoshinaga and Masaru Kitsuregawa. A self-adaptive classifier for efficient text-stream processing. In Proceedings of the 24th International Conference on Computational Linguistics (COLING), pages 1091-1102, 2014.
Cited by
Sorted by citations
Prefix Sharing Is a Sorting Problem
He, R. (2026) · arXiv · doi:10.48550/arxiv.2609.13692
- Authors
- Bannai, H., Goto, K., Kanda, S., & Köppl, D.
- Affiliations
- Tokyo Medical and Dental University (JP)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2024
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2403.04951
- OpenAlex
- W4392730451
- Cited by
- 0
- References
- 0
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Japan Society for the Promotion of Science (21K17701, 20H04141, JP21H05847)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- NP-completeness, string indexing, sparse matrix compression, decision problems, alphabet size, prefix search, membership queries
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
