The Trie Measure, Revisited
Jarno N. Alanko, Ruben Becker, Davide Cenzato, Travis Gagie, Sung-Hwan Kim, Bojana Kodric, Nicola Prezza · 2025
Read The Trie Measure, Revisited by Jarno N. Alanko, Ruben Becker, Davide Cenzato, Travis Gagie, Sung-Hwan Kim, Bojana Kodric, Nicola Prezza (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-10703.txt.
Introduction
Jarno Alanko and six co-authors revisit the trie measure problem in a two thousand twenty-five algorithms paper. Given many subsets of an integer universe, the task is choosing a prefix-free encoding that minimizes the total edges in the binary tries storing the subsets.
The general problem equals cheapest merging of sets by binary unions and is NP-hard. The authors therefore study structured encodings: they give efficient algorithms for the best fixed-length shifted encoding, an optimal ordered encoding, and a shifted ordered encoding provably no worse than either. Implementations accompany the theory, and experiments show how the encodings behave in practice on real data.
Catalog record
| CREATOR | Jarno N. Alanko, Ruben Becker, Davide Cenzato, Travis Gagie, Sung-Hwan Kim, Bojana Kodric, Nicola Prezza |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-10703
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Trie Measure, Revisited Jarno N. Alanko, Ruben Becker, Davide Cenzato, Travis Gagie, Sung-Hwan Kim, Bojana Kodric, Nicola Prezza Abstract In this paper, we study the following problem: given n n subsets S 1 , … , S n S_{1},\dots,S_{n} of an integer universe U = { 0 , … , u − 1 } U=\{0,\dots,u-1\} , having total cardinality N = ∑ i = 1 n | S i | N=\sum_{i=1}^{n}|S_{i}| , find a prefix-free encoding enc : U → { 0 , 1 } + \enc:U\rightarrow\{0,1\}^{+} minimizing the so-called trie measure , i.e., the total number of edges in the n n binary tries 𝒯 1 , … , 𝒯 n \mathcal{T}_{1},\dots,\mathcal{T}_{n} , where 𝒯 i \mathcal{T}_{i} is the trie packing the encoded integers { enc ( x ) : x ∈ S i } \{\enc(x):x\in S_{i}\} . We first observe that this problem is equivalent to that of merging u u sets with the cheapest sequence of binary unions, a problem which in [Ghosh et al., ICDCS 2015] is shown to be NP-hard. Motivated by the hardness of the general problem, we focus on particular families of prefix-free encodings. We start by studying the fixed-length shifted encoding of [Gupta et al., Theoretical Computer Science 2007]. Given a parameter 0 ≤ a < u 0\leq a<u , this encoding sends each x ∈ U x\in U to ( x + a ) mod u (x+a)\modulo u , interpreted as a bit-string of log u \log u bits. We develop the first efficient algorithms that find the value of a a minimizing the trie measure when this encoding is used. Our two algorithms run in O ( u + N log u ) O(u+N\log u) and O ( N log 2 u ) O(N\log^{2}u) time, respectively. We proceed by studying ordered encodings (a.k.a. monotone or alphabetic ), and describe an algorithm finding the optimal such encoding in O ( N + u 3 ) O(N+u^{3}) time. Within the same running time, we show how to compute the best shifted ordered encoding , provably no worse than both the optimal shifted and optimal ordered encodings. We provide implementations of our algorithms and discuss how these encodings perform in practice. University of Helsinki, [email protected] https://orcid.org/0000-0002-8003-9225 Ca’ Foscari University of Venice, [email protected]://orcid.org/0000-0002-3495-3753 Ca’ Foscari University of Venice, [email protected]://orcid.org/0000-0002-0098-3620 Dalhousie University, Halifax, Nova Scotia, [email protected] https://orcid.org/0000-0003-3689-327X Ca’ Foscari University of Venice, [email protected]://orcid.org/0000-0002-1117-5020 Ca’ Foscari University of Venice, [email protected]://orcid.org/0000-0001-7242-0096 Ca’ Foscari University of Venice, [email protected]://orcid.org/0000-0003-3553-4953 ccs Theory of computation Data compression ccs Theory of computation Design and analysis of algorithms ccs Theory of computation Dynamic programming ccs Theory of computation Discrete optimization keywords Succinct data structures, degenerate strings, integer encoding † † funding: Ruben Becker, Davide Cenzato, Sung-Hwan Kim, Bojana Kodric, Nicola Prezza : Funded by the European Union (ERC, REGINDEX, 101039208). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. Travis Gagie : Funded by NSERC Discovery Grant RGPIN-07185-2020. † † runningauthor: J. Alanko et al. † † copyright: Jarno Alanko et al. † † supplement: Software: https://github.com/regindex/trie-measure † † editors: Paola Bonizzoni and Veli Mäkinen † † event-title: 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025) † † event-shorttitle: CPM 2025 † † event-acronym: CPM † † year: 2025 † † event-date: June 17–19, 2025 † † event-location: Milan, Italy † † series-volume: 331 † † articleno: 20 1 Introduction Consider the problem of encoding a set of integers S\subseteq U=\{0,\dots,u-1\} (without loss of generality, we assume u to be a power of two), so as to minimize the overall number of bits used to represent S . In their seminal work on data-aware measures, Gupta et al. [ 10 ] proposed and analyzed an encoding for sets of integers based on the idea of packing the integers (seen as strings of \log u bits) into a binary trie: this allows to avoid storing multiple times shared prefixes among the encodings of the integers. The number of edges in such a trie is known as the trie measure of the set. See Figure 1 for an example. 7 6 0 1 5 4 0 1 0 1 3 2 0 1 1 0 0 1 0 1 0 1 Figure 1: Example of trie encoding the set of integers \{3,4,6\}\subseteq\{0,1,\dots,7\} over universe of size u=8 . Black edges belong to the trie. Gray edges do not belong to the trie and are shown only for completeness. Each integer is encoded using \log 8=3 bits (logarithms are in base 2). The trie has 8 edges, so the trie measure for this set using the standard integer encoding is 8. Gupta et al. also showed that this measure approaches worst-case entropy on expectation when the integers are shifted by a uniformly-random quantity modulo u , i.e. when building the trie over the set S+a\coloneq\{x+a\modulo u:x\in S\} for a uniform a\in U . See Figure 2 . 6 5 0 1 4 3 0 1 0 1 2 1 0 1 0 7 0 1 0 1 0 1 Figure 2: A trie that stores the same set of integers \{3,4,6\}\subseteq\{0,1,\dots,7\} of Figure 1 , but with the shifted integer encoding mapping each x\in U to (the binary string of \log u bits) (x+1)\modulo 8 . The trie has 6 edges, so the shifted trie measure with shift a=1 is 6. In this paper, we revisit this problem in two natural directions: (1) we move from one set to a sequence of sets, and (2) we study more general prefix-free integer encodings. More formally, given n subsets S_{1},\dots,S_{n} of U , having total cardinality N=\sum_{i=1}^{n}|S_{i}| , we study the problem of finding a prefix-free encoding \enc:U\rightarrow\{0,1\}^{+} minimizing the trie measure of these sets, i.e. the total number of edges in the n binary tries \mathcal{T}_{1},\dots,\mathcal{T}_{n} , where \mathcal{T}_{i} is the trie packing the encoded integers \{\enc(x):x\in S_{i}\} . Solving the problem on set sequences finds applications in data structures for rank/select queries on set sequences—also known in the literature as degenerate strings —, an important toolbox in indexes for labeled graphs [ 8 , 6 , 5 , 7 ] . Such applications stem from the recent work of Alanko et al. [ 1 ] , who showed how to solve rank and select queries on set sequences with a data structure — the subset wavelet tree — implicitly encoding sets as tries. While [ 1 ] only considered the standard binary (balanced) encoding, their technique works for any prefix-free encoding. As a result, our work can directly be applied to optimize the space of their data structure. Another application is the offline set intersection problem where the goal to preprocess subsets of the universe, so that later given a set of indices of the sets, one can compute the intersection of the sets space-time efficiently. Arroyuelo and Castillo [ 2 ] presented an adaptive approach that uses a trie representation of sets and they showed that it can benefit