A Self-Index on Block Trees

⋆

Gonzalo Navarro

arXiv:1606.06617v4 [] 10 Oct 2017

Department of Computer Science, University of Chile, Beauchef 851, Santiago, Chile,
gnavarro@dcc.uchile.cl

Abstract. The Block Tree is a recently proposed data structure that
reaches compression close to Lempel-Ziv while supporting efficient direct
access to text substrings. In this paper we show how a self-index can be
built on top of a Block Tree so that it provides efficient pattern searches
while using space proportional to that of the original data structure.
More precisely, if a Lempel-Ziv parse cuts a text of length n into z nonoverlapping phrases, then our index uses O(z lg(n/z)) words and finds
the occ occurrences of a pattern of length m in time O(m lg n + occ lgǫ n)
for any constant ǫ > 0.

1

Introduction

The Block Tree (BT) [1] is a novel data structure for representing a sequence,
which reaches a space close to its LZ77-compressed [26] space. Given a string
S[1..n] over alphabet [1..σ], on which the LZ77 parser produces z phrases (and
thus an LZ77 compressor uses z lg n + O(z lg σ) bits, where lg denotes the logarithm in base 2), the BT on S uses O(z lg(n/z) lg n) bits (also said to be
O(z lg(n/z)) space). This is also the best asymptotic space obtained with grammar compressors [24,4,25,15,16]. In exchange for using more space than LZ77
compression, the BT offers fast extraction of substrings: a substring of length ℓ
can be extracted in time O((1 + ℓ/ lgσ n) lg(n/z)). In this paper we consider the
LZ77 variant where sources and phrases do not overlap, thus z = Ω(lg n).
Kreft and Navarro [18] introduced a self-index based on LZ77 compression,
which proved to be extremely space-efficient on highly repetitive text collections
[6]. A self-index on S is a data structure that offers direct access to any substring
of S (and thus it replaces S), and at the same time offers indexed searches. Their
self-index uses 3z lg n + O(z lg σ) + o(n) bits (that is, about 3 times the size of
the compressed text) and finds all the occ occurrences of a pattern of length m
in time O(m2 h + (m + occ) lg z), where h ≤ z is the maximum number of times
a symbol is successively copied along the LZ77 parsing. A string of length ℓ is
extracted in O(hℓ) time.
Experiments on repetitive text collections [18,6] show that this LZ77-index
is smaller than any other alternative and is competitive when searching for patterns, especially on the short ones where the term m2 h is small and occ is large,
so that the low time to report each occurrence dominates. On longer patterns,
⋆

Funded in part by Fondecyt Grant 1-170048.

2

G. Navarro

however, the index is significantly slower. The term h can reach the hundreds
on repetitive collections, and thus it poses a significant penalty (and a poor
worst-case bound).
In this paper we design the BT-index, a self-index that builds on top of BTs
instead of on LZ77 compression. Given a BT of w = O(z lg(n/z)) leaves (which
can be represented in w lg n + O(w) bits), the BT-index uses 3w lg n + O(w)
bits, and it searches for a pattern of length m in time O(m2 lg(n/z) lg lg z +
m lg z lg lg z + occ(lg(n/z) lg lg n + lg z)), which is in general a better theoretical
bound than that of the LZ77-index. If we allow the space to be any O(w) =
O(z lg(n/z)) words, then the time can be reduced to O(m2 lg(n/z) + m lgǫ z +
occ(lg lg n + lgǫ z)) for any constant ǫ > 0. In regular texts, the O(lg(n/z)) factor
is around 3–4, and it raises to 8–10 on highly repetitive texts; both are much
lower than the typical values of h. Thus we expect the BT-index to be faster than
the LZ77-index especially for longer patterns, where the O(m2 ) factor dominates.
The self-indexes that build on grammar compression [7,8] can use the same
asymptotic space of our BT-index, and their best search time is O(m2 lg lg n +
m lg z + occ lg z). Belazzougui et al. [1], however, show that in practice BTs are
faster to access S than grammar-compressed representations, and use about the
same space if the text is highly repetitive. Thus we expect that our self-index will
be better in practice than those based on grammar compression, again especially
when the pattern is long and there are no too many occurrences to report.
There are various other indexes in the literature using O(z lg(n/z)) bits [11,2]
or slightly more [10,22,2] that offer better time complexities. However, they have
not been implemented as far as we know, and it is difficult to predict how will
they behave in practice.

2

Block Trees

Given a string S[1..n] over an alphabet [1..σ], whose LZ77 parse produces z
phrases, a Block Tree (BT) is defined as follows. At the top level, numbered
l = 0, we split S into z blocks of length b0 = n/z. Each block is then recursively
split into two, so that if bl is the length of the blocks at level l it holds bl+1 = bl /2,
until reaching blocks of one symbol after lg(n/z) levels. At each level, every
pair of consecutive blocks S[i..j] that does not appear earlier as a substring of
S[1..i − 1] is marked. Blocks that are not marked are replaced by a pointer ptr
to their first occurrence in S (which, by definition, must be a marked block or
overlap a pair of marked blocks). For every level l ≥ 0, a bitvector Dl with one
bit per block sets to 1 the positions of marked blocks. In level l + 1 we consider
and subdivide only the blocks that were marked in level l. In this paper, this
subdivision is carried out up to the last level, where the marked blocks store
their corresponding symbol.
We can regard the BT as a binary tree (with the first lg z levels chopped out),
where the internal nodes are the marked nodes and have two children, and the
leaves are the unmarked nodes. Thus we store one pointer ptr per leaf. We also
spend one bit per node in the bitvectors Dl . If we call w the number of unmarked

A Self-Index on Block Trees

3

blocks (leaves), then the BT has w − z marked blocks (internal nodes), and it
uses w lg n + O(w) bits.
To extract a single symbol S[i], we see if i is in a marked block at level 0,
that is, if D0 [⌈i/b0 ⌉] = 1. If so, we map i to a position in the next level, which
only contains the marked blocks of this level:
i ← (rank1 (D0 , ⌈i/b0 ⌉) − 1) · b0 + ((i − 1) mod b0 ) + 1.
Function rankc (D, p) counts the number of occurrences of bit c in D[1..p]. A
bitvector D can be represented in |D|+o(|D|) bits so that rankc can be computed
in constant time [5]. Therefore, if i falls in a marked block, we translate the
problem to the next level in constant time. If, instead, i is not in a marked
block, we take the pointer ptr stored for that block, and replace i ← i − ptr,
assuming ptr stores the distance towards the first occurrence of the unmarked
block. Now i is again on a marked block, and we can move on to the next level
as described. The total time to extract a symbol is then O(lg(n/z)).

3

A Self-Index

Our self-index structure is made up of two main components: the first finds all
the pattern positions that cross block boundaries, whereas the second finds the
positions that are copied onto unmarked blocks. The main property that we
exploit is the following. We will say that a block is explicit in level l if all the
blocks containing it in lower levels are marked. Note that the explicit blocks in
level l are either marked or unmarked, and the descendants of those unmarked
are not explicit in higher levels.
Lemma 1. The occurrences of a given string P of length at least 2 in S either
overlap two explicit blocks at some level, or are completely inside an unmarked
block at some level.
Proof. We proceed by induction on the BT block size. Consider the level l = 0,
where all the blocks are explicit. If the occurrence overlaps two blocks or it is
completely inside an unmarked block, we are done. If, instead, it is completely
inside a marked block, then this block is split into two blocks that are explicit in
the next level. Consider that we concatenate all the explicit blocks of the next
level. Then we have a new sequence where the occurrence appears, and we use a
smaller block size, so by the inductive hypothesis, the property holds. The base
case is the leaf level, where the blocks are of length 1.
⊓
⊔
We exploit the lemma in the following way. We will define an occurrence of
P as primary if it overlaps two consecutive blocks at some level. The occurrences
that are completely contained in an unmarked block are secondary (this idea is a
variant of the classical one used in all the LZ-based indexes [17]). Secondary occurrences are found by detecting primary or other secondary occurrences within
the area from where an unmarked block is copied. We will use a data structure
to find the primary occurrences and another to detect the copies.

4

G. Navarro

Lemma 2. The described method correctly identifies all the occurrences of a
string P in S.
Proof. We proceed again by induction on the block length. Consider level l = 0.
If a given occurrence overlaps two explicit blocks at this level, then it is primary
and will be found. Otherwise, if it is inside a marked block at this level, then it
also appears at the next level and it will be found by the inductive hypothesis.
Finally, if it is inside an unmarked block, then it points to a marked block at the
same level and will be detected as a copy of the occurrence already found in the
source. The base case is the last level, where all the blocks are of length 1. ⊓
⊔
3.1

The Data Strucures

We describe the data structures used by our index. Overall, they require 3w lg n+
O(w) bits, and replace the pointers ptr used by the original structure. We also
retain the bitvectors Dl , which add up to O(w) bits.
Primary occurrences. Our structure to find the primary occurrences is a twodimensional discrete grid G storing points (x, y) as follows. Let B be a marked
block at some level l, which is divided into B = Bleft · Bright at level l + 1. Note
that blocks Bleft and Bright can be marked or unmarked. Then we collect the
rev
(i.e., Bleft read backwards) in the multiset Y and the block
reverse block Bleft
Bright in the multiset X. In addition, for the blocks B1 . . . Bz of level l = 0, we
also add Birev to Y and the suffix Bi+1 . . . Bz to X, for all 1 ≤ i < z.
We then lexicographically sort X and Y , to obtain the strings X1 , X2 , . . . and
Y1 , Y2 , . . .. The grid has a point at (x, y) for each pair hXx , Yy i that was added
together in the previous process.
If a primary occurrence is not contained in any block, then it spans a sequence
Bi . . . Bj of blocks at level l = 0. We will then find it as the concatenation
of a suffix Bi with a prefix of Bi+1 . . . Bz . Otherwise, let B be the smallest
(or deepest) marked block that contains the occurrence. Let B be split into
Bleft · Bright in the BT. Then the occurrence will span a suffix of Bleft and a
prefix of Bright (otherwise, B is not minimal or the occurrence is not primary).
Therefore, each primary occurrence will be found at exactly one pair hXx , Yy i.
The grid G is of size w × w, since there are w − 1 pairs hXx , Yy i: one per
internal BT node (of which there are w − z), plus z − 1 for the blocks of level 0.
We represent G using a wavelet tree [14,13,21], so that it takes w lg w + o(w) bits
and can report all the y-coordinates of the p points lying inside any rectangle of
the grid in time O((p + 1) lg w). We spend other w lg n bits in an array T [1..w]
that gives the position j in S corresponding to each point (x, y), sorted by ycoordinate.
Secondary occurrences. Let Sl [1..nl ] be the subsequence of S formed by the
explicit blocks at level l. If an unmarked block Bi [1..bl ] at level l points to its
first occurrence at Sl [k..k + bl − 1], we say that [k..k + bl − 1] is the source of Bi .

A Self-Index on Block Trees

5

Algorithm 1: Extracting symbols from our encoded BT.
1
2
3
4
5
6
7
8
9
10
11

Proc Extract(i)
l←0
b ← n/z
while b > 1 do
j ← ⌈i/b⌉
if Dl [j] = 0 then
r ← rank0 (Dl , j)
p ← select1 (Fl , πl (r))
s ← (j − 1) · b + 1
i ← (p − πl (r)) + (i − s)
j ← ⌈i/b⌉

14

i ← (rank1 (Dl , j) − 1) · b + ((i − 1) mod b) + 1
l ←l+1
b ← b/2

15

Return the symbol stored at position i in the last level

12
13

For each level l with wl unmarked blocks, we store two structures to find the
secondary occurrences. The first is a bitvector Fl [1..nl + wl ] built as follows: We
traverse from Sl [1] to Sl [nl ]. For each Sl [k], we add a 0 to Fl , and then as many
1s as sources start at position k. The second structure is a permutation πl on
[wl ] where πl (i) = j iff the source of the ith unmarked block of level l is signaled
by the jth 1 in Fl .
Each bitvector Fl can be represented in wl lg(nl /wl ) + O(wl ) bits so that
operation select1 (Fl , r) can be computed in constant time [23]. This operation
finds the position of the rth 1 in Fl . On the other hand, we represent πl using a
structure [20] that uses wl lg wl + O(wl ) bits and computes any πl (i) P
in constant
time and any πl−1 (j) in time O(lg wl ). Added over all the levels, since l wl = w,
these structures use w lg n + O(w) bits.
3.2

Extraction

Let us describe how we extract a symbol S[i] = S0 [i] using our representation.
We first compute the block j ← ⌈i/b0 ⌉ where i falls. If D0 [j] = 1, we are already
done on this level. If, instead, D0 [j] = 0, then the block j is not marked. Its rank
among the unmarked blocks of this level is r0 = rank0 (D0 , j). The position of
the 1 in F0 corresponding to its source is p0 = select1 (F0 , π0 (r0 )). This means
that the source of the block j starts at S0 [p0 − π0 (r0 )]. Since block j starts at
position s0 = (j − 1) · b0 + 1, we set i ← (p0 − π0 (r0 )) + (i − s0 ) and recompute
j ← ⌈i/b0 ⌉, knowing that the new symbol S0 [i] is the same as the original one.
Now that i is inside a marked block j, we move to the next level. To compute
the position of i in the next level, we do i ← (rank1 (D0 , j) − 1) · b0 + ((i − 1)
mod b0 )+1, and continue in the same way to extract S1 [i]. In the last level we find
the symbol stored explicitly. The total time to extract a symbol is O(lg(n/z)).

6

G. Navarro

Algorithm 2: General search procedure.
1
2
3
4
5
6
7
8
9

Proc Search(P, m)
if m = 1 then
m←2
P = P [1]∗
for k = 1 to m − 1 do
[x1 , x2 ] ← binary search for P [k + 1..m] in X1 , . . . , Xw
(or [1, w] if P [k + 1..m] = ∗)
[y1 , y2 ] ← binary search for P [1..k]rev in Y1 , . . . , Yw
for (x, y) ∈ G ∩ [x1 , x2 ] × [y1 , y2 ] do
Primary(T [y] − k, m)

Algorithm 1 gives the pseudocode.

3.3

Queries

Primary occurrences. To search for a pattern P [1..m], we first find its primary
occurrences using G as follows. For each partition P< = P [1..k] and P> =
P [k + 1..m], for 1 ≤ k < m, we binary search Y for P<rev and X for P> . To
compare P<rev with a string Yi , since Yi is not stored, we extract the consecutive
symbols of S[T [i] − 1], S[T [i] − 2], and so on, until the lexicographic comparison
can be decided. Thus each comparison requires O(m lg(n/z)) time. To compare
P> with a string Xi , since Xi is also not stored, we extract the only point of the
range [i, i] × [1, w] (or, in terms of the wavelet tree, we extract the y-coordinate
of the ith element in the root sequence), in time O(lg w). This yields the point
Yj . Then we compare P> with the successive symbols of S[T [j]], S[T [j] + 1], and
so on. Such a comparison then costs O(lg w + m lg(n/z)). The m binary searches
require m lg w binary search steps, for a total cost of O(m2 lg w lg(n/z)+m lg2 w).
Note that the length of the strings to compare can be obtained implicitly
from T [i] (or, equivalently, T [j]). If T [i] − 1 (or T [j] − 1) is a multiple of (n/z)/2l
but not of (n/z)/2l+1 , then the string is a block of level l and its length is
(n/z)/2l (except if l = 0, in which case Yj is the full suffix S[T [j]..n]). This is
easily found in constant time using arithmetic operations.
Each couple of binary searches identifies ranges [x1 , x2 ]×[y1 , y2 ], inside which
we extract every point. The m range searches cost O(m lg w) time. Further,
each point (x, y) extracted costs O(lg w) and it identifies a primary occurrence
at S[T [y] − k..T [y] − k + m − 1]. Therefore the total cost with occp primary
occurrences is O(m2 lg w lg(n/z) + m lg2 w + occp lg w).
Algoritm 2 gives the general search procedure, using procedure Primary to
report the primary occurrences and all their associated secondary ones.
Patterns P of length m = 1 can be handled as P [1]∗, where ∗ stands for any
character. Thus we take [x1 , x2 ] = [1, w] and carry out the search as a normal

A Self-Index on Block Trees

7

pattern of length m = 2. To make this work also for the last position in S, we
assume as usual that S is terminated by a special character $.
To speed up the binary searches, we can sample one out of lg w strings from
Y and insert them into a Patricia tree [19], which would use O(w) extra space.
The up to σ children in each node are stored in perfect hash functions, so that in
O(m) time we can find the Patricia tree node v representing the pattern prefix or
suffix sought. Then the range [y1 , y2 ] includes all the sampled leaves descending
from v, and up to lg w strings preceding and following the range. The search
is then completed with binary searches in O(lg lg w) steps. In case the pattern
prefix or suffix is not found in the Patricia tree, we end up in a node v that does
not have the desired child and we have to find the consecutive pair of children v1
and v2 that surround the nonexistent child. A predecessor search structure per
node finds these children in time O(lg lg σ) = O(lg lg z) = O(lg lg w). Then we
finish with a binary search between the rightmost leaf of v1 and the leftmost leaf
of v2 , also in O(lg lg w) steps. Each binary search step takes O(m lg(n/z)) time to
read the desired substring from S. At the end of the Patricia search, we must also
read one string and verify that the range is correct, but this cost is absorbed
in the binary searches. Overall, the search for each cut of the pattern costs
O(m lg(n/z) lg lg w). We proceed similarly with X, where there is an additional
cost of O(lg w lg lg w) to find the position where to extract each string from. The
total cost over all the m − 1 searches is then O(m(m lg(n/z) + lg w) lg lg w).
Secondary occurrences. Let S[i..i + m − 1] be a primary occurrence. This is
already a range [i0 ..i0 + m − 1] = [i..i + m − 1] at level l = 0. We track the
range down to positions [il ..il + m − 1] at all the levels l > 0, using the position
tracking mechanism described in Section 3.2 for the case of marked nodes:
il+1 = (rank1 (Dl , ⌈il /bl ⌉) − 1) · bl + ((il − 1) mod bl ) + 1.
Note that we only need to consider levels l where the block length is bl ≥ m, as
with shorter blocks there cannot be secondary occurrences. So we only consider
the levels l = 0 to l = lg(n/z)− lg m. Further, we should ensure that the block or
the two blocks where [il ..il + m − 1] lies are marked before projecting the range
to the next level, that is, Dl [⌈il /bl ⌉] = Dl [⌈(il + m − 1)/bl ⌉] = 1. Still, note that
we can ignore this test, because there cannot be sources spanning concatenated
blocks that were not contiguous in the previous levels.
For each valid range [il ..il + m − 1], we determine the sources that contain
the range, as their target will contain a secondary occurrence. Those sources
must start between positions k = il + m − bl and k ′ = il . We find the positions
p = select0 (Fl , k) and p′ = select0(Fl , k ′ + 1), thus the blocks of interest are
πl−1 (t), from t = p − k + 1 to t = p′ − k ′ − 1. Since Fl is represented as a
sparse bitvector [23], operation select0 is solved with binary search on select1 ,
in time O(lg wl ) = O(lg w). This can be accelerated to O(lg lg nl ) by sampling
one out of lg nl 1s in Fl , building a predecessor structure on the samples, and
then completing the binary search within two samples. The extra space of the
predecessor structures adds up to O(w) bits.

8

G. Navarro

To report the occurrence inside each such block q = πl−1 (t), we first find its
position in the corresponding unmarked block in its level. The block starts at
Sl [(select0 (Dl , q) − 1) · bl + 1], and the offset of the occurrence inside the block is
il −(select1 (Fl , t)−t) (operation selectc on Dl is answered in constant time using
o(|Dl |) further bits [5]). Therefore, the copied occurrence is at Sl [i′l ..i′l + m − 1],
where
i′l = ((select0 (Dl , q) − 1) · bl + 1) + (il − (select1 (Fl , t) − t)).
We then project the position i′l upwards until reaching the level l = 0, where
the positions correspond to those in S. To project Sl [i′l ] to Sl−1 , we compute the
block number j = ⌈i′l /bl−1 ⌉, and set
i′l−1 ← (select1 (Dl−1 , j) − 1) · bl−1 + ((i′l − 1) mod bl−1 ) + 1.
Each new secondary occurrence we report at S[i..i + m − 1] must be also
processed to find further secondary occurrences at unmarked blocks copying it
at any level. This can be done during the upward tracking to find its position in
S, as we traverse all the relevant ranges [i′l ..i′l + m − 1].
Algorithm 3 describes the procedure to report the primary occurrence S[i..i+
m − 1] and all its associated secondary occurrences.
Considering the time to compute πl−1 at its source, the upward tracking to
find its position in S, and the tests to find further secondary occurrences at
each level of the upward tracking, each secondary occurrence is reported in time
O(lg(n/z) lg lg n). Each primary occurrence, in turn, is obtained in time O(lg w)
and then we spend O(lg(n/z) lg lg n) time to track it down to all the levels to
find possible secondary occurrences. Therefore, the occ primary and secondary
occurrences are reported in time O(occ(lg(n/z) lg lg n + lg w)).
Total query cost. As described, the total query cost to report the occ occurrences
is O(m2 lg(n/z) lg lg w + m lg w lg lg w + occ(lg(n/z) lg lg n + lg w)). Since w =
O(z lg(n/z)) and z = Ω(lg n), it holds lg w = Θ(lg z). A simplified formula is
O(m2 lg n lg lg z + occ lg n lg lg n). The space is 3w lg n + O(w) bits.
Theorem 3. Given a string S[1..n] that can be parsed into z non-overlapping
Lempel-Ziv phrases and represented with a BT of w = O(z lg(n/z)) pointers,
there exists a data structure using 3w lg n + O(w) bits that so that any substring of length ℓ can be extracted in time O(ℓ lg(n/z)) and the occ occurrences
of a pattern P [1..m] can be obtained in time O(m2 lg(n/z) lg lg z + m lg z lg lg z +
occ(lg(n/z) lg lg n+lg z)). This can be written as O(m2 lg n lg lg z+occ lg n lg lg n).
If we are interested in a finer space result, we can see that the space is actually
2w lg n + w lg w + O(w) bits. This can be reduced to w lg n + 2w lg w + O(w)
by storing the array T [1..w] in w lg w + O(w) bits as follows. We have that
each such position is either the start of a block at level l = 0 or the middle
of a marked block. If we store the bitvectors D0 to Dlg(n/z) concatenated into
D = 1z D0 · · · Dlg(n/z) , then the first z 1s represent the blocks at level l = 0 and

A Self-Index on Block Trees

9

Algorithm 3: Reporting primary and secondary occurrences.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Proc Primary(i, m)
l←0
b ← n/z
while b/2 ≥ m and Dl [⌈i/b⌉] = Dl [⌈(i + m − 1)/b⌉] = 1 do
i ← (rank1 (Dl , ⌈i/b⌉) − 1) · b + ((i − 1) mod b) + 1
l ←l+1
b ← b/2
Secondary(l, i, m)
Proc Secondary(l, i, m)
b ← (n/z)/2l
while l ≥ 0 do
k ←i+m−b
k′ ← i
p ← select0 (Fl , k)
p′ ← select0 (Fl , k′ )
for t ← p − k + 1 to p′ − k′ − 1 do
q ← πl−1 (t)
i′ ← ((select0 (Dl , q) − 1) · b + 1) + (i − (select1 (Fl , t) − t))
Secondary(l, i′ , m)
b ←2·b
l ←l−1
if l ≥ 0 then
j ← ⌈i/b⌉
i ← (select1 (Dl , j) − 1) · b + ((i − 1) mod b) + 1
Report occurrence at position i

the other 1s represent the marked blocks of each level. We can therefore store
T [k] = p to refer to the pth 1 in D, so that T uses w lg w bits. From the position
select1 (D, p) in D, we can determine in constant time if it is among the first z,
which corresponds to a level-0 block, or that it corresponds to some Dl [i] (by
using rank on another bitvector of O(w) bits that marks the lg(n/z) starting
positions of the bitvectors Dl in D, or with a small fusion tree storing those
positions). If T [k] points to Dl [i], we know that the suffix starts at Sl [il ], for
il = (i − 1/2) · bl + 1. We then project this position up to S. Thus we obtain any
position of T in time O(lg(n/z)), which does not affect the complexities.

4

Using Linear Space

If we do not care about the constant multiplying the space, we can have a BTindex using O(w lg n) bits and speed up searches considerably. First, we can
obtain the m − 1 ranges in the sets X and Y , corresponding to prefixes/suffixes
of P , in overall time O(m lg(mn/z)), by using the fingerprinting technique described by Gagie et al. [12, Lem. 9]. The lemma states that, if one can extract a

10

G. Navarro

substring of length ℓ from S in time fe (ℓ) and can compute a fingerprint of it in
time fh (ℓ), then one can obtain the lexicographic ranges in X of the m − 1 suffixes of P in time O(m lg(σ)/ω + m(fh (m)+ lg m)+ fe (m)), where ω = Ω(lg n) is
the number of bits in the computer word. Similarly, we obtain the ranges in Y of
the suffixes of the reversed pattern. They also show [12, Thm. 2] how to extract
any substring S[i..i + ℓ − 1] in time O(h + m lg(σ)/ω) using a structure analogous
to block trees of height h. These can be translated verbatim to block-trees using
O(w lg n) bits that extract substrings in time O(lg(n/z) + m lg(σ)/ω). Finally,
they show [12, Lem. 7] how to compute a fingerprint in time O(h) with the same
structure analogous to a block tree of height h, so we can similarly extend the
block tree to use O(w) words and compute the fingerprint in time O(lg(n/z)).
Second, we can use faster two-dimensional range search data structures that
still require linear space [3] to report the p points in time O((p + 1) lgǫ w)
for any constant ǫ > 0 [3]. This reduces the cost per primary occurrence to
O(lg(n/z) lg lg n + lgǫ w).
Finally, we can replace the predecessor searches that implement select0 on the
bitvectors Fl by a completely different mechanism. Note that all those searches
we perform in our upward or downward path refer to the same occurrence position S[i..i + m − 1], because we do not find unmarked blocks in the path. Thus,
instead of looking for sources covering the occurrence at every step in the path,
we use a single structure where all the sources from all the levels l are mapped to
S. Such sources [j..j + bl − 1] are sorted by their starting positions j in an array
R[1..w]. We create a range maximum query data structure [9] on R, able to find
in constant time the maximum endpoint j + bl − 1 of the blocks in any range of
R. A predecessor search structure on the j values gives us the rightmost position
R[r] where the blocks start at i or to its left. A range maximum query on R[1..r]
then finds the block R[k] with the rightmost endpoint in R[1..r]. If even R[k]
does not cover the position j + bl − 1, then no source covers the occurrence.
If it does, we process it as a secondary occurrence and recurse on the ranges
R[1..k − 1] and R[k + 1..r]. It is easy to see that each valid secondary occurrence
is identified in O(1) time.
Note that, if we store the starting position j ′ of the target of source [j..j +
bl − 1], then we directly have the position of the secondary occurrence in S,
S[i′ ..i′ + m − 1] with i′ = j ′ + (i − j). Thus we do not even need to traverse
paths upwards or downwards, since the primary occurrences already give us
positions in S. The support for inverse permutations πl−1 becomes unnecessary.
Then the cost per secondary occurrence is reduced to a predecessor search. A
similar procedure is described for the LZ77-index [18].
The total time then becomes O(m lg(mn/z) + m lgǫ z + occ(lg lg(n/z) +
ǫ
lg z)) = O(m lg n + occ(lg lg n + lgǫ z)).
Theorem 4. A string S[1..n] where the LZ77 parse produces z non-overlapping
phrases can be represented in O(z lg(n/z)) space so that any substring of length
ℓ can be extracted in time O(lg(n/z) + ℓ/ lgσ n) and the occ occurrences of a
pattern P [1..m] can be obtained in time O(m lg n + occ(lg lg n + lgǫ z)), for any
constant ǫ > 0. This can be written as O(m lg n + occ lgǫ n).

A Self-Index on Block Trees

5

11

Conclusions

We have proposed a way to build a self-index on the Block Tree (BT) [1] data
structure, which we call BT-index. The BT obtains a compression related to
the LZ77-parse of the string. If the parse uses z non-overlapping phrases, then
the BT uses O(z lg(n/z)) space, whereas an LZ77-compressor uses O(z) space.
Our BT-index, within the same asymptotic space of a BT, finds all the occ
occurrences of a pattern P [1..m] in time O(m lg n + occ lgǫ n) for any constant
ǫ > 0.
The next step is to implement the BT-index, or a sensible simplification of it,
and determine how efficient it is compared to current implementations [18,7,8,6].
As discussed in the Introduction, there are good reasons to be optimistic about
the practical performance of this self-index, especially when searching for relatively long patterns.

Acknowledgements
Many thanks to Simon Puglisi and an anonymous reviewer for pointing out
several fatal typos in the formulas, and to Travis Gagie for useful suggestions.

References
1. Belazzougui, D., Gagie, T., Gawrychowski, P., Kärkkäinen, J., Ordóñez, A., Puglisi,
S.J., Tabei, Y.: Queries on LZ-bounded encodings. In: Proc. 25th Data Compression Conference (DCC). pp. 83–92 (2015)
2. Bille, P., Ettienne, M.B., Gørtz, I.L., Vildhøj, H.W.: Time-space trade-offs for
Lempel-Ziv compressed indexing. In: Proc. 28th Annual Symposium on Combinatorial Pattern Matching (CPM). pp. 16:1–16:17. LIPIcs 78 (2017)
3. Chan, T.M., Larsen, K.G., Pătraşcu, M.: Orthogonal range searching on the RAM,
revisited. In: Proc. 27th ACM Symposium on Computational Geometry (SoCG).
pp. 1–10 (2011)
4. Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A.,
Shelat, A.: The smallest grammar problem. IEEE Transactions on Information
Theory 51(7), 2554–2576 (2005)
5. Clark, D.: Compact PAT Trees. Ph.D. thesis, University of Waterloo, Canada
(1996)
6. Claude, F., Fariña, A., Martı́nez-Prieto, M., Navarro, G.: Universal indexes for
highly repetitive document collections. Information Systems 61, 1–23 (2016)
7. Claude, F., Navarro, G.: Self-indexed grammar-based compression. Fundamenta
Informaticae 111(3), 313–337 (2010)
8. Claude, F., Navarro, G.: Improved grammar-based compressed indexes. In: Proc.
19th International Symposium on String Processing and Information Retrieval
(SPIRE). pp. 180–192. LNCS 7608 (2012)
9. Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum
queries on static arrays. SIAM Journal on Computing 40(2), 465–492 (2011)
10. Gagie, T., Gawrychowski, P., Kärkkäinen, J., Nekrich, Y., Puglisi, S.J.: A faster
grammar-based self-index. In: Proc. 6th International Conference on Language and
Automata Theory and Applications (LATA). pp. 240–251. LNCS 7183 (2012)

12

G. Navarro

11. Gagie, T., Gawrychowski, P., Kärkkäinen, J., Nekrich, Y., Puglisi, S.J.: LZ77based self-indexing with faster pattern matching. In: Proc. 11th Latin American
Symposium on Theoretical Informatics (LATIN). pp. 731–742 (2014)
12. Gagie, T., Navarro, G., Prezza, N.: Optimal-time text indexing in BWT-runs
bounded space. CoRR abs/1705.10382 (2017)
13. Golynski, A., Raman, R., Rao, S.S.: On the redundancy of succinct data structures.
In: Proc. 11th Scandinavian Workshop on Algorithm Theory (SWAT). pp. 148–159.
LNCS 5124 (2008)
14. Grossi, R., Gupta, A., Vitter, J.S.: High-order entropy-compressed text indexes.
In: Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).
pp. 841–850 (2003)
15. Jez, A.: Approximation of grammar-based compression via recompression. Theoretical Computer Science 592, 115–134 (2015)
16. Jez, A.: A really simple approximation of smallest grammar. Theoretical Computer
Science 616, 141–150 (2016)
17. Kärkkäinen, J., Ukkonen, E.: Lempel-Ziv parsing and sublinear-size index structures for string matching. In: Proc. 3rd South American Workshop on String Processing (WSP). pp. 141–155 (1996)
18. Kreft, S., Navarro, G.: On compressing and indexing repetitive sequences. Theoretical Computer Science 483, 115–133 (2013)
19. Morrison, D.: PATRICIA – practical algorithm to retrieve information coded in
alphanumeric. Journal of the ACM 15(4), 514–534 (1968)
20. Munro, J.I., Raman, R., Raman, V., Rao, S.S.: Succinct representations of permutations and functions. Theoretical Computer Science 438, 74–88 (2012)
21. Navarro, G.: Wavelet trees for all. Journal of Discrete Algorithms 25, 2–20 (2014)
22. Nishimoto, T., I, T., Inenaga, S., Bannai, H., Takeda, M.: Dynamic index, LZ
factorization, and LCE queries in compressed space. CoRR abs/1504.06954 (2015)
23. Okanohara, D., Sadakane, K.: Practical entropy-compressed rank/select dictionary.
In: Proc. 9th Workshop on Algorithm Engineering and Experiments (ALENEX).
pp. 60–70 (2007)
24. Rytter, W.: Application of Lempel-Ziv factorization to the approximation of
grammar-based compression. Theoretical Computer Science 302(1-3), 211–222
(2003)
25. Sakamoto, H.: A fully linear-time approximation algorithm for grammar-based
compression. Journal of Discrete Algorithms 3(24), 416–430 (2005)
26. Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE
Transactions on Information Theory 23(3), 337–343 (1977)

