A compressed index is a data structure representing a text within compressed space and supporting fast count and locate queries: count/return all positions where a pattern occurs. The first compressed indexes operate within a space bounded by the text's entropy. Entropy, however, is insensitive to long repetitions. For this reason, in recent years more powerful compressed indexes have emerged; these are based on  the Lempel-Ziv factorization, the run-length BWT, context-free grammars and, more recently, string attractors. Labeled trees add a whole new dimension to the problem: one needs not only to compress the labels, but also the tree 's topology. On this side, less is known. Jacobson showed how to represent the topology of a tree with n nodes in 2n+o(n) bits of space (succinct) while also supporting constant-time navigation queries. Ferragina et al. presented the first entropy-compressed labeled tree representation (the XBWT) able to count, but not locate , paths labeled with a given pattern. Grammars and the Lempel-Ziv factorization have been extended to trees, but those representations do not support indexing queries. In this paper, we show for the first time how to support the powerful locate queries on compressed trees. We start by proposing suitable generalizations of  [  run-length  BWT , high-order entropy, and string attractors to cardinal trees (tries) . We show that  the number r \leq n of XBWT-runs upper-bounds the size of the smallest tree attractor and lower-bounds the trie's high-order worst-case entropyH. We finally present the first trie index able to locate in pre-order nodes reached by a path labeled with a given pattern. Our index locates path occurrences in constant time each and takes 2n + o(n) + O(r log n) \leq 2n + o(n)  + O(H log n) bitsof space: the reporting timeis optimal and the locate machinery fits within compressed space on top of the succinct topology .
In this paper, we consider the problem of compressing a trie while supporting the powerfullocate queries: to return the pre-order identifiers of all nodes reached by a path labeled with a given query pattern. Our result builds on top of the XBWT tree transform of Ferragina et al. FOCS 2005 and generalizes ther-index locate machinery of Gagie et al.[SODA 2018, JACM 2020 based on the run-length encoded Burrows-Wheeler transform (BWT). Our first contribution is to propose a suitable generalization of the run-length BWT to tries . We show that this natural generalization enjoys several of the useful properties of its counterpart on strings: in particular, the transform natively supports counting occurrences of a query pattern on the trie's paths and its size r captures the trie's repetitiveness and lower-bounds a natural notion of trie entropy. Our main contribution is a much deeper insight into the combinatorial structure of this object. In detail, we show that a data structure of O(r \log n) + 2n + o(n) bits, where n is the number of nodes, allows locating the occ occurrences of a pattern of length m in nearly-optimal O(m\log\sigma + occ) time, where \sigma is the alphabet's size. Our solution consists in sampling O(r) nodes that can be used as "anchor points" during the locate process. Once obtained the pre-order identifier of the first pattern occurrence (in co-lexicographic order), we show that a constant number of constant-time jumps between those anchor points lead to the identifier of the next pattern occurrence, thus enabling locating in optimal O(1) time per occurrence .
R
A compressed index is a data structure representing a text within compressed space and supporting fast count and locate queries: count/return all positions where a pattern occurs. The first compressed indexes operate within a space bounded by the text's entropy. Entropy, however, is insensitive to long repetitions. For this reason, in recent years more powerful compressed indexes have emerged; these are based on
In this paper, we consider the problem of compressing a trie while supporting the powerful
A
locate
A
queries: to return
R
Lempel-Ziv factorization, the run-length BWT, context-free grammars and, more recently, string attractors. Labeled trees add a whole new dimension to the problem: one needs not only to compress the labels, but also the tree 's topology. On this side, less is known. Jacobson showed how to represent the topology of a tree with n nodes in 2n+o(n) bits of space (succinct) while also supporting constant-time navigation queries.
pre-order identifiers of all nodes reached by a path labeled with a given query pattern. Our result builds on top of the XBWT tree transform of
R
presented the first entropy-compressed labeled tree representation (the XBWT) able to count, but not locate , paths labeled with a given pattern. Grammars and the Lempel-Ziv factorization have been extended to trees, but those representations do not support indexing queries. In this paper, we show for the first time how to support the powerful locate queries on compressed trees. We start by proposing suitable generalizations of
FOCS 2005
A
and generalizes the
A
r-index
A
locate machinery of Gagie et al.
A
SODA 2018, JACM 2020
A
based on the
A
encoded Burrows-Wheeler transform (BWT). Our first contribution is to propose a suitable generalization of the run-length
R
, high-order entropy, and string attractors to cardinal trees (tries)
to tries
A
this natural generalization enjoys several of the useful properties of its counterpart on strings: in particular, the transform natively supports counting occurrences of a query pattern on the trie's paths and its size r captures
D
number r \leq n of XBWT-runs upper-bounds the size of the smallest tree attractor and lower-bounds the
R
high-order worst-case entropyH. We finally present the first trie index able to locate in pre-order nodes reached by a path labeled with a given pattern. Our index locates path occurrences in constant time each and takes 2n + o(n) +
repetitiveness and lower-bounds a natural notion of trie entropy. Our main contribution is a much deeper insight into the combinatorial structure of this object. In detail, we show that a data structure of
R
log n) \leq
\log n) +
A
bits, where n is the number of nodes, allows locating the occ occurrences of a pattern of length m in nearly-optimal O(m\log\sigma
R
O(H log n) bitsof space: the reporting timeis optimal and the locate machinery fits within compressed space on top of the succinct topology
occ) time, where \sigma is the alphabet's size. Our solution consists in sampling O(r) nodes that can be used as "anchor points" during the locate process. Once obtained the pre-order identifier of the first pattern occurrence (in co-lexicographic order), we show that a constant number of constant-time jumps between those anchor points lead to the identifier of the next pattern occurrence, thus enabling locating in optimal O(1) time per occurrence