Space-Efficient Construction of Compressed Indexes in
Deterministic Linear Time

arXiv:1607.04346v2 [cs.DS] 14 Nov 2016

J. Ian Munro∗

Gonzalo Navarro†

Yakov Nekrich‡

Abstract
We show that the compressed suffix array and the compressed suffix tree of a string T can
be built in O(n) deterministic time using O(n log σ) bits of space, where n is the string length
and σ is the alphabet size. Previously described deterministic algorithms either run in time that
depends on the alphabet size or need ω(n log σ) bits of working space. Our result has immediate
applications to other problems, such as yielding the first deterministic linear-time LZ77 and
LZ78 parsing algorithms that use O(n log σ) bits.

∗

Cheriton School of Computer Science, University of Waterloo. Email imunro@uwaterloo.ca.
CeBiB — Center of Biotechnology and Bioengineering, Department of Computer Science, University of Chile.
Email gnavarro@dcc.uchile.cl. Funded with Basal Funds FB0001, Conicyt, Chile.
‡
Cheriton School of Computer Science, University of Waterloo. Email: yakov.nekrich@googlemail.com.
†

1

Introduction

In the string indexing problem we pre-process a string T , so that for any query string P all
occurrences of P in T can be found efficiently. Suffix trees and suffix arrays are two most popular
solutions of this fundamental problem. A suffix tree is a compressed trie on suffixes of T ; it enables
us to find all occurrences of a string P in T in time O(|P | + occ) where occ is the number of times
P occurs in T and |P | denotes the length of P . In addition to indexing, suffix trees also support a
number of other, more sophisticated, queries. The suffix array of a string T is the lexicographically
sorted array of its suffixes. Although suffix arrays do not support all queries that can be answered
by the suffix tree, they use less space and are more popular in practical implementations. While
the suffix tree occupies O(n log n) bits of space, the suffix array can be stored in n log n bits.
During the last twenty years there has been a significant increase in interest in compressed
indexes, i.e., data structures that keep T in compressed form and support string matching queries.
The compressed suffix array (CSA) [21, 14, 39] and the compressed suffix tree (CST) [40] are
compressed counterparts of the suffix array and the suffix tree respectively. A significant part of
compressed indexes relies on these two data structures or their variants. Both CSA and CST can
be stored in O(n log σ) bits or less; we refer to e.g. [7] or [33] for an overview of compressed indexes.
It is well known that both the suffix array and the suffix tree can be constructed in O(n)
time [30, 43, 44, 25]. The first algorithm that constructs the suffix tree in linear time independently
of the alphabet size was presented by Farach [13]. There are also algorithms that directly construct
the suffix array of T in O(n) time [24, 26]. If the (uncompressed) suffix tree is available, we can
obtain CST and CSA in O(n) time. However this approach requires O(n log n) bits of working space.
The situation is different if we want to construct compressed variants of these data structures using
only O(n log σ) bits of space. Within this space the algorithm of Hon et al. [23] constructs the
CST in O(n logε n) time for an arbitrarily small constant ε > 0. In the same paper the authors
also showed that CSA can be constructed in O(n log log σ) time. The algorithm of Okanohara
and Sadakane constructs the CSA in linear time, but needs O(n log σ log log n) bits of space [37].
Belazzougui [2] described randomized algorithms that build both CSA and CST in O(n) time
and O(n log σ) bits of space. His approach also provides deterministic algorithms with runtime
O(n log log σ) [3]. In this paper we show that randomization is not necessary in order to construct
CSA and CST in linear time. Our algorithms run in O(n) deterministic time and require O(n log σ)
bits of space.
Suffix trees, in addition to being an important part of many compressed indexes, also play
an important role in many string algorithms. One prominent example is Lempel-Ziv parsing of a
string using O(n log σ) bits. The best previous solutions for this problem either take O(n log log σ)
deterministic time or O(n) randomized time [27, 10]. For instance Köppl and Sadakane [27] showed
how we can obtain LZ77- and LZ78-parsing for a string T in O(n) deterministic time and O(n log σ)
bits, provided that the CST of T is constructed. Thus our algorithm, combined with their results,
leads to the first linear-time deterministic LZ-parsing algorithm that needs O(n log σ) bits of space.
Overview. The main idea of our approach is the use of batch processing. Certain operations,
such as rank and select queries on sequences, are a bottleneck of previous deterministic solutions.
Our algorithms are divided into a large number of small tasks that can be executed independently.
Hence, we can collect large batches of queries and answer all queries in a batch. This approach
speeds up the computation because, as will be shown later, answering all queries in a batch takes less
time than answering the same set of queries one-by-one. For example, our algorithm for generating
the Burrows-Wheeler Transform of a text T works as follows. We cut the original text into slices
1

of ∆ = logσ n symbols. The BWT sequence is constructed by scanning all slices in the right-to-left
order. All slices are processed at the same time. That is, the algorithm works in ∆ steps and
during the j-th step, for 0 ≤ j ≤ ∆ − 1, we process all suffixes that start at position i∆ − j − 1
for all 1 ≤ i ≤ n/∆. Our algorithm maintains the sorted list of suffixes and keeps information
about those suffixes in a symbol sequence B. For every suffix Si = T [i∆ − j − 1..] processed during
the step j, we must find its position in the sorted list of suffixes. Then the symbol T [i∆ − j − 2]
is inserted at the position that corresponds to Si in B. Essentially we can find the position of
every new suffix Si by answering a rank query on the sequence B. Details are given in Section 2.
Next we must update the sequence by inserting the new symbols into B. Unfortunately we need
Ω(log n/ log log n) time in general to answer rank queries on a dynamic sequence [17]. Even if we
do not have to update the sequence, we need Ω(log log σ) time to answer a rank query [8]. In our
case, however, the scenario is different: There is no need to answer queries one-by-one. We must
provide answers to a large batch of n/∆ rank queries with one procedure. In this paper we show
that the lower bounds for rank queries can be circumvented in the batched scenario: we can answer
the batch of queries in O(n/∆) time, i.e., in constant time per query. We also demonstrate that a
batch of n/∆ insertions can be processed in O(n/∆) time. This result is of independent interest.
Data structures that answer batches of rank queries and support batched updates are described
in Sections 3, A.2, and A.3. This is the most technically involved aspect of our result. In Section 3 we
show how answers to a large batch of queries can be provided. In Section A.2 we describe a special
labeling scheme that assigns monotonously increasing labels to elements of a list. We conclude this
portion in Section A.3 where we show how the static data structure can be dynamized. Next we turn
to the problem of constructing the compressed suffix tree. First we describe a data structure that
answers partial rank queries in constant time and uses O(n log log σ) additional bits in Section A.4;
unlike previous solutions, our data structure can be constructed in O(n) deterministic time. This
result is plugged into the algorithm of Belazzougui [2] to obtain the suffix tree topology in O(n)
deterministic time. Finally we show how the permuted LCP array (PLCP) can be constructed in
O(n) time, provided we already built the suffix array and the suffix tree topology; the algorithm is
described in Section 5. Our algorithm for constructing PLCP is also based on batch processing of
rank queries. To make this paper self-contained we provide some background on compressed data
structures and indexes in Section A.1.
We denote by T [i..] the suffix of T starting at position i and we denote by T [i..j] the substring
of T that begins with T [i] and ends with T [j], T [i..] = T [i]T [i + 1] . . . T [n − 1] and T [i..j] =
T [i]T [i + 1] . . . T [j − 1]T [j]. We assume that the text T ends with a special symbol $ and $
lexicographically precedes all other symbols in T . The alphabet size is σ and symbols are integers
in [0..σ − 1] (so $ corresponds to 0). In this paper, as in the previous papers on this topic, we use
the word RAM model of computation. A machine word consists of log n bits and we can execute
standard bit operations, addition and subtraction in constant time. We will assume for simplicity
that the alphabet size σ ≤ n1/4 . This assumption is not restrictive because for σ > n1/4 linear-time
algorithms that use O(n log σ) = O(n log n) bits are already known.

2

Linear Time Construction of the Burrows-Wheeler Transform

In this section we show how the Burrows-Wheeler transform (BWT) of a text T can be constructed
in O(n) time using O(n log σ) bits of space. Let ∆ = logσ n. We can assume w.l.o.g. that the text
length is divisible by ∆ (if this is not the case we can pad the text T with dn/∆e∆ − n $-symbols).
The BWT of T is a sequence B defined as follows: if T [k..] is the (i+1)-th lexicographically smallest

2

suffix, then B[i] = T [k − 1]1 . Thus the symbols of B are the symbols that precede the suffixes of
T , sorted in lexicographic order. We will say that T [k − 1] represents the suffix T [k..] in B. Our
algorithm divides the suffixes of T into ∆ classes and constructs B in ∆ steps. We say that a suffix
S is a j-suffix for 0 ≤ j < ∆ if S = T [i∆ − j − 1..] for some i, and denote by Sj the set of all
j-suffixes, Sj = { T [i∆ − j − 1..] | 1 ≤ i ≤ n/∆ }. During the j-th step we process all j-suffixes and
insert symbols representing j-suffixes at appropriate positions of the sequence B.
Steps 0 − 1. We sort suffixes in S0 and S1 by constructing a new text and representing it as a
sequence of n/∆ meta-symbols. Let T1 = T [n − 1]T [0]T [1] . . . T [n − 2] be the text T rotated by one
symbol to the right and let T2 = T [n − 2]T [n − 1]T [0] . . . T [n − 3] be the text obtained by rotating
T1 one symbol to the right. We represent T1 and T2 as sequences of length n/∆ over meta-alphabet
σ ∆ (each meta-symbol corresponds to a string of length ∆). Thus we view T1 and T2 as
T1 = T [n − 1] . . . T [∆ − 2] T [∆ − 1] . . . T [2∆ − 2] T [2∆ − 1] . . . T [3∆ − 2] T [3∆ − 1] . . . . . .
T2 = T [n − 2] . . . T [∆ − 3] T [∆ − 2] . . . T [2∆ − 3] T [2∆ − 2] . . . T [3∆ − 3] T [3∆ − 2] . . . . . .
Let T3 = T1 ◦ T2 denote the concatenation of T1 and T2 . To sort the suffixes of T3 , we sort
the meta-symbols of T3 and rename them with their ranks. Since meta-symbols correspond to
(log n)-bit integers, we can sort them in time O(n) using radix sort. Then we apply a linear-time
and linear-space suffix array construction algorithm [24] to T3 . We thus obtain a sorted list of
suffixes L for the meta-symbol sequence T3 . Suffixes of T3 correspond to the suffixes from S0 ∪ S1
in the original text T : the suffix T [i∆ − 1..] corresponds to the suffix of S0 starting with metasymbol T [i∆ − 1]T [i∆] . . . in T3 and the suffix T [i∆−2 . . .] corresponds to the suffix of S1 starting

with T [i∆ − 2]T [i∆ − 1] . . . . Since we assume that the special symbol $ is smaller than all other
symbols, this correspondence is order-preserving. Hence by sorting the suffixes of T3 we obtain the
sorted list L0 of suffixes in S0 ∪ S1 . Now we are ready to insert symbols representing j-suffixes
into B: Initially B is empty. Then the list L0 is traversed and for every suffix T [k..] that appears
in L0 we add the symbol T [k − 1] at the end of B.
When suffixes in S0 and S1 are processed, we need to record some information for the next step
of our algorithm. For every suffix S ∈ S1 we keep its position in the sorted list of suffixes. The
position of suffix T [i∆ − 2..] is stored in the entry W [i] of an auxiliary array W , which at the end
of the j-th step will contain the positions of the suffixes T [i∆ − j − 1..]. We also keep an auxiliary
array Acc of size σ: Acc[a] is equal to the number of occurrences of symbols i ≤ a − 1 in the current
sequence B.
Step j for j ≥ 2. Suppose that suffixes from S0 , . . ., Sj−1 are already processed. The symbols
that precede suffixes from these sets are stored in the sequence B; the k-th symbol B[k] in B is
the symbol that precedes the k-th lexicographically smallest suffix from ∪j−1
t=0 St . For every suffix
T [i∆ − j..], we know its position W [i] in B. Every suffix Si = T [i∆ − j − 1..] ∈ Sj can be
represented as Si = aSi0 for some symbol a and the suffix Si0 = T [i∆ − j..] ∈ Sj−1 . We look up the
position ti = W [i] of Si0 and answer rank query ri = ranka (ti , B). We need Ω(log logloglogσ n ) time to
answer a single rank query on a static sequence [8]. If updates are to be supported, then we need
Ω(log n/ log log n) time to answer such a query [17]. However in our case the scenario is different:
1

So B[0] has the lexicographically smallest suffix (i+1 = 1) and so on. The exact formula is B[i] = T [(k−1)mod n].
We will write B[i] = T [k − 1] to avoid tedious details.

3

we perform a batch of n/∆ queries to sequence B, i.e., we have to find ri for all ti . During Step
2 the number of queries is equal to |B|/2 where |B| denotes the number of symbols in B. During
step j the number of queries is |B|/j ≥ |B|/∆. We will show in Section 3 that such a large batch
of rank queries can be answered in O(1) time per query. Now we can find the rank pi of Si among
∪jt=1 St : there are exactly pi suffixes in ∪jt=1 St that are smaller than Si , where pi = Acc[a] + ri .
Correctness of this computation can be proved as follows.
Proposition 1 Let Si = aSi0 be an arbitrary suffix from the set Sj . For every occurrence of a
symbol a0 < a in the sequence B, there is exactly one suffix Sp < Si in ∪jt=1 St , such that Sp starts
with a0 . Further, there are exactly ri suffixes Sv in ∪jt=1 St such that Sv ≤ Si and Sv starts with a.
Proof : Suppose that a suffix Sp from St , such that j ≥ t ≥ 1, starts with a0 < a. Then Sp = a0 Sp0
for some Sp0 ∈ St−1 . By definition of the sequence B, there is exactly one occurrence of a0 in B for
every such Sp0 . Now suppose that a suffix Sv ∈ St , such that j ≥ t ≥ 1, starts with a and Sv ≤ Si .
Then Sv = aSv0 for Sv0 ∈ St−1 and Sv0 ≤ Si0 . For every such Sv0 there is exactly one occurrence of
the symbol a in B[1..ti ], where ti is the position of Si0 in B.

The above calculation did not take into account the suffixes from S0 . We compute the number of
suffixes Sk ∈ S0 such that Sk < Si using the approach of Step 0 − 1. Let T1 be the text obtained
by rotating T one symbol to the right. Let T 0 be the text obtained by rotating T j + 1 symbols to
the right. We can sort suffixes of S0 and Sj by concatenating T1 and T 0 , viewing the resulting text
T 00 as a sequence of 2n/∆ meta-symbols and constructing the suffix array for T 00 . When suffixes
in S0 ∪ Sj are sorted, we traverse the sorted list of suffixes; for every suffix Si ∈ Sj we know the
number qi of lexicographically smaller suffixes from S0 .
We then modify the sequence B: We sort new suffixes Si by oi = pi + qi . Next we insert the
symbol T [i∆ − j − 1] at position oi − 1 in B (assuming the first index of B is B[0]); insertions
are performed in increasing order of oi . We will show that this procedure also takes O(1) time per
update for a large batch of insertions. Finally we record the position of every new suffix from Sj
in the sequence B. Since the positions of suffixes from Sj−1 are not needed any more, we use the
entry W [i] of W to store the position of T [i∆ − j − 1..]. The array Acc is also updated.
When Step ∆ − 1 is completed, the sequence B contains n symbols and B[i] is the symbol that
precedes the (i+1)-th smallest suffix of T . Thus we obtained the BWT of T . Step 0 of our algorithm
uses O((n/∆) log n) = O(n log σ) bits. For all the following steps we need to maintain the sequence
B and the array W . B uses O(log σ) bits per symbol and W needs O((n/∆) log n) = O(n log σ)
bits. Hence our algorithm uses O(n log σ) bits of workspace. Procedures for querying and updating
B are described in the following section. Our result can be summed up as follows.
Theorem 1 Given a string T [0..n − 1] over an alphabet of size σ, we can construct the BWT of
T in O(n) deterministic time using O(n log σ) bits.

3

Batched Rank Queries on a Sequence

In this section we show how a batch of m rank queries for logn2 n ≤ m ≤ n can be answered in O(m)
time on a sequence B of length n. We start by describing a static data structure. A data structure
that supports batches of queries and batches of insertions will be described later. We will assume
σ ≥ log4 n; if this is not the case, the data structure from [15] can be used to answer rank queries
in time O(1).
4

Following previous work [19], we divide B into chunks of size σ (except for the last chunk that
contains at most σ symbols). For every symbol a we keep a binary sequence Ma = 1d1 01d2 0 . . . 1df
where f is the total number of chunks and di is the number of occurrences of a in the chunk. We
keep the following information for every chunk C. Symbols in a chunk C are represented as pairs
(a, i): we store a pair (a, i) if and only if C[i] = a. These pairs are sorted by symbols and pairs
representing the same symbol a are sorted by their positions in C; all sorted pairs from a chunk
are kept in a sequence R. The array F consists of σ entries; F [a] contains a pointer to the first
occurrence of a symbol a in R (or null if a does not occur in C). Let Ra denote the subsequence of
R that contains all pairs (a, ·) for some symbol a. If Ra contains at least log2 n pairs, we split Ra
into groups Ha,r of size Θ(log2 n). For every group, we keep its first pair in the sequence R0 . Thus
R0 is also a subsequence of R. For each pair (a0 , i0 ) in R0 we also store the partial rank of C[i0 ] in
C, rankC[i0 ] (i0 , C).
All pairs in Ha,r are kept in a data structure Da,r that contains the second components of pairs
(a, i) ∈ Ha,r . Thus Da,r contains positions of Θ(log2 n) consecutive symbols a. If Ra contains
less than log2 n pairs, then we keep all pairs starting with symbol a in one group Ha,0 . Every
Da,r contains O(log2 n) elements. Hence we can implement Da,r so that predecessor queries are
answered in constant time: for any integer q, we can find the largest x ∈ Ha,r satisfying x ≤ q in
O(1) time [18]. We can also find the number of elements x ∈ Ha,r satisfying x ≤ q in O(1) time.
This operation on Ha,r can be implemented using bit techniques similar to those suggested in [35];
details are to be given in the full version of this paper.
Queries on a Chunk. Now we are ready to answer a batch of queries in O(1) time per query.
First we describe how queries on a chunk can be answered. Answering a query ranka (i, C) on a
chunk C is equivalent to counting the number of pairs (a, j) in R such that j ≤ i. Our method
works in three steps. We start by sorting the sequence of all queries on C. Then we “merge” the
sorted query sequence with R0 . That is, we find for every ranka (i, C) the rightmost pair (a, j 0 ) in
R0 , such that j 0 ≤ i. Pair (a, j 0 ) provides us with an approximate answer to ranka (i, C) (up to an
additive O(log2 n) term). Then we obtain the exact answer to each query by searching in some
data structure Da,j . Since Da,j contains only O(log2 n) elements, the search can be completed in
O(1) time. A more detailed description follows.
Suppose that we must answer v queries ranka1 (i1 , C), ranka2 (i2 , C), . . ., rankav (iv , C) on a
chunk C. We sort the sequence of queries by pairs (aj , ij ) in increasing order. This sorting
step takes O(σ/ log2 n + v) time, where v is the number of queries: if v < σ/ log3 n, we sort in
O(v log n) = O(σ/ log2 n) time; if v ≥ σ/ log3 n, we sort in O(v) time using radix sort (e.g., with
√
radix σ). Then we simultaneously traverse the sorted sequence of queries and R0 ; for each query
pair (aj , ij ) we identify the pair (at , pt ) in R0 such that either (i) pt ≤ ij ≤ pt+1 and aj = at = at+1
or (ii) pt ≤ ij , aj = at , and at 6= at+1 . That is, we find the largest pt ≤ ij such that (aj , pt ) ∈ R0
for every query pair (aj , ij ). If (at , pt ) is found, we search in the group Hat ,pt that starts with the
pair (at , pt ). If the symbol aj does not occur in R0 , then we search in the leftmost group Haj ,0 .
Using Dat ,pt (resp. Dat ,0 ), we find the largest position xt ∈ Hat ,pt such that xt ≤ ij . Thus xt is
the largest position in C satisfying xt ≤ ij and C[xt ] = aj . We can then compute rankat (xt , C) as
follows: Let n1 be the partial rank of C[pt ], n1 = rankC[pt ] (pt , C). Recall that we explicitly store
this information for every position in R0 . Let n2 be the number of positions i ∈ Hat ,pt satisfying
i ≤ xt . We can compute n2 in O(1) time using Dat ,pt . Then rankaj (xt , C) = n1 + n2 . Since C[xt ]
is the rightmost occurrence of aj up to C[ij ], rankaj (ij , C) = rankaj (xt , C). The time needed to
traverse the sequence R0 is O(σ/ log2 n) for all the queries. Other computations take O(1) time per
5

query. Hence the sequence of v queries on a chunk is answered in O(v + σ/ log2 n) time.
Global Sequence. Now we consider the global sequence of queries ranka1 (i1 , B), . . ., rankam (im , B).
First we assign queries to chunks (e.g., by sorting all queries by (bi/σc + 1) using radix sort). We
2
answer the batch of queries on the
number of
Pj-th chunk in O(mj + σ/ log n) time where mj is the
queries on the j-th chunk. Since mj = m, all m queries are answered in O(m+n/ log2 n) = O(m)
time. Now we know the rank nj,2 = rankaj (i0j , C), where i0j = ij − bi/σcσ is the relative position of
B[ij ] in its chunk C.
The binary sequences Ma allows us reduce rank queries on B to rank queries on a chunk C.
All sequences Ma contain n + bn/σcσ bits; hence they use O(n) bits of space. We can compute
the number of occurrences of a in the first j chunks in O(1) time by answering one select query.
Consider a rank query rankaj (ij , B) and suppose that nj,2 is already known. We compute nj,1 ,
where nj,1 = select0 (bij /σc, Maj ) − bij /σc is the number of times aj occurs in the first bij /σc
chunks. Then we compute rankaj (ij , B) = nj,1 + nj,2 .
Theorem 2 We can keep a sequence B[0..n − 1] over an alphabet of size σ in O(n log σ) bits of
space so that a batch of m rank queries can be answered in O(m) time, where logn2 n ≤ m ≤ n.
The static data structure of Theorem 2 can be dynamized so that batched queries and batched
insertions are supported. Our dynamic data structures supports a batch of m queries in time O(m)
and a batch of m insertions in amortized time O(m) for any m that satisfies logn n ≤ m ≤ n. We
σ
describe the dynamic data structure in Sections A.2 and A.3.

4

Building the Suffix Tree

Belazzougui proved the following result [2]: if we are given the BWT B of a text T and if we can
report all the distinct symbols in a range of B in optimal time, then in O(n) time we can: (i)
enumerate all the suffix array intervals corresponding to internal nodes of the suffix tree and (ii)
for every internal node list the labels of its children and their intervals. Further he showed that,
if we can enumerate all the suffix tree intervals in O(n) time, then we can build the suffix tree
topology [40] in O(n) time. The algorithms need only O(n) additional bits of space. We refer to
Lemmas 4 and 1 and their proofs in [2] for details.
In Section A.4 we show that a partial rank data structure can be built in O(n) deterministic
time. This can be used to build the desired structure that reports the distinct symbols in a range,
in O(n) time and using O(n log log σ) bits. The details are given in Section A.5. Therefore, we
obtain the following result.
Lemma 1 If we already constructed the BWT of a text T , then we can build the suffix tree topology
in O(n) time using O(n log log σ) additional bits.
In Section 5 we show that the permuted LCP array of T can be constructed in O(n) time using
O(n log σ) bits of space. Thus we obtain our main result on building compressed suffix trees.
Theorem 3 Given a string T [0..n − 1] over an alphabet of size σ, we can construct the compressed
suffix tree of T in O(n) deterministic time using O(n log σ) additional bits.

6

5

Constructing the Permuted LCP Array

The permuted LCP array is defined as P LCP [i] = j if and only if SA[r] = i and the longest
common prefix of T [SA[r]..] and T [SA[r − 1]..] is of length j. In other words P LCP [i] is the length
of the longest common prefix of T [i..] and the suffix that precedes it in the lexicographic ordering.
In this section we show how the permuted LCP array P LCP [0..n − 1] can be built in linear time.

Preliminaries. For i = 0, 1, . . . , n let `i = P LCP [i]. It is easy to observe that `i ≤ `i+1 + 1:
if the longest common prefix of T [i..] and T [j..] is q, then the longest common prefix of T [i + 1..]
and T [j + 1..] is at least q − 1. Let ∆0 = ∆ log log σ for ∆ = logσ n. By the same argument
`i ≤ `i+∆0 +P
∆0 . To simplify the description we will further assume that `−1 = 0. It can also be
shown that n−1
i=0 (`i − `i−1 ) = O(n).
We will denote by B the BWT sequence of T ; B denotes the BWT of the reversed text T =
T [n − 1]T [n − 2] . . . T [1]T [0]. Let p be a factor (substring) of T and let c be a character. The
operation extendright(p, c) computes the suffix interval of pc in B and the suffix interval of pc in
B provided that the intervals of p and p are known. The operation contractleft(cp) computes
the suffix intervals of p and p provided that the suffix intervals of factors cp and cp are known2 . It
was demonstrated [42, 5] that both operations can be supported by answering O(1) rank queries
on B and B.
Belazzougui [2] proposed the following algorithm for consecutive computing of `0 , `1 , . . ., `n .
Suppose that `i−1 is already known. We already know the rank ri−1 of T [i − 1..], the interval of
T [i − 1..i + `i−1 − 1] in B, and the interval of T [i − 1..i + `i−1 − 1] in B. We compute the rank ri
of T [i..]. If ri−1 is known, we can compute ri in O(1) time by answering one select query on B;
see Section A.1. Then we find the interval [rs , re ] of T [i..i + `i−1 − 1] in B and the interval [rs0 , re0 ]
of T [i..i + `i−1 − 1] in B. These two intervals can be computed by contractleft. In the special
case when i = 0 or `i−1 = 0, we set [rs , re ] = [rs0 , re0 ] = [0, n − 1]. Then for j = 1, 2, . . . we find the
intervals for T [i..i + (`i−1 − 1) + j] and T [i..i + (`i−1 − 1) + j]. Every following pair of intervals is
found by operation extendright. We stop when the interval of T [i..i + `i−1 − 1 + j] is [rs,j , re,j ]
such that rs,j = ri . For all j 0 , such that 0 ≤ j 0 < j, we have rs,j 0 < ri . It can be shown that
`i = `i−1 + j − 1; see the proof of [2, Lemma 2]. Once `i is computed, we increment i and find the
next `i in the same way. All `i are computed by O(n) contractleft and extendright operations.
Implementing contractleft and extendright. We create the succinct representation of the
suffix tree topology both for T and T ; they will be denoted by T and T respectively. We keep
both B and B in the data structure that supports access in O(1) time. We also store B in the
data structure that answers select queries in O(1) time. The array Acc keeps information about
accumulated frequencies of symbols: Acc[i] is the number of occurrences of all symbols a ≤ i − 1
in B. Operation contractleft is implemented as follows. Suppose that we know the interval
[i, j] for a factor cp and the interval [i0 , j 0 ] for the factor cp. We can compute the interval [i1 , j1 ]
of p by finding l = selectc (i − Acc[c], B) and r = selectc (j − Acc[c], B). Then we find the lowest
common ancestor x of leaves l and r in the suffix tree T . We set i1 = leftmost leaf(x) and
j1 = rightmost leaf(x). Then we consider the number of distinct symbols in B[i1 ..j1 ]. If c is the
only symbol that occurs in B[i1 ..j1 ], then all factors p in T are preceded by c. Hence all factors
p in T are followed by c and [i01 , j10 ] = [i0 , j 0 ]. Otherwise we find the lowest common ancestor y of
leaves i0 and j 0 in T . Then we identify y 0 = parent(y) in T and let i01 = leftmost leaf(y 0 ) and
j10 = rightmost leaf(y 0 ). Thus contractleft can be supported in O(1) time.
2

Throughout this paper reverse strings are overscored. Thus p and pc are reverse strings of p and pc respectively.

7

Now we consider the operation extendright. Suppose that [i, j] and [i0 , j 0 ] are intervals of p and
p in B and B respectively. We compute the interval of pc by using the standard BWT machinery.
Let i01 = rankc (i0 − 1, B) + Acc[c] and j10 = rankc (j 0 , B) + Acc[c] − 1. We check whether c is the
only symbol in B[i0 ..j 0 ]. If this is the case, then all occurrences of p in T are preceded by c and all
occurrences of p in T are followed by c. Hence the interval of pc in B is [i1 , j1 ] = [i, j]. Otherwise
there is at least one other symbol besides c that can follow p. Let x denote the lowest common
ancestor of leaves i and j. If y is the child of x that is labeled with c, then the interval of pc is
[i1 , j1 ] where i1 = leftmost leaf(y) and j1 = rightmost leaf(y).
We can find the child y of x that is labeled with c by answering rank and select queries on two
additional sequences, L and D. The sequence L contains labels of children for all nodes of T ; labels
are ordered by nodes and labels of the same node are ordered lexicographically. We encode the
degrees of all nodes in a sequence D = 1d1 01d2 0 . . . 1dn , where di is the degree of the i-th node. We
compute v = select0 (x, D) − x, p1 = rankc (v, L), p2 = selectc (p1 + 1, L), and j = p2 − v. Then y is
the j-th child of x. The bottleneck of extendright are the computations of p1 , i01 , and j10 because
we need Ω(log logloglogσ n ) time to answer a rank query on L (resp. on B); all other calculations can
be executed in O(1) time.
Our Approach. Our algorithm follows the technique of [2] that relies on operations extendright
and contractleft for building the PLCP. We implement these two operations as described above;
hence we will have to perform Θ(n) rank queries on sequences L and B. Our method creates large
batches of queries; each query in a batch is answered in O(1) time using Theorem 2.
During the pre-processing stage we create the machinery for supporting operations extendright
and contractleft. We compute the BWT B of T and the BWT B for the reverse text T . We
also construct the suffix tree topologies T and T . When B is constructed, we record the positions
in B that correspond to suffixes T [i · ∆0 ..] for i = 0, . . . , bn/∆0 c. PLCP construction is divided into
three stages: first we compute the values of `i for selected evenly spaced indices i, i = j · ∆0 and
j = 0, 1,. . .,bn/∆0 c. We use a slow algorithm for computing lengths that takes O(∆0 ) extra time
for every `i . During the second stage we compute all remaining values of `i . We use the method
from [2] during Stage 2. The key to a fast implementation is “parallel” computation. We divide
all lengths into groups and assign each group of lengths to a job. At any time we process a list
containing at least 2n/ log2 n jobs. We answer rank queries in batches: when a job Ji must answer
a slow rank query on L or B, we pause Ji and add the rank query to the corresponding pool of
queries. When a pool of queries on L or the pool of queries on B contains n/ log2 n items, we
answer the batch of queries in O(n/ log2 n) time. The third stage starts when the number of jobs
becomes smaller than 2n/ log2 n. All lengths that were not computed earlier are computed during
Stage 3 using the slow algorithm. Stage 2 can be executed in O(n) time because rank queries are
answered in O(1) time per query. Since the number of lengths that we compute during the first
and the third stages is small, Stage 1 and Stage 3 also take time O(n). A more detailed description
follows.
Stage 1. Our algorithm starts by computing `i for i = j · ∆0 and j = 0, 1, . . . , bn/∆0 c. Let j = 0
and f = j∆0 . We already know the rank rf of Sf = T [j∆0 ..] in B (rf was computed and recorded
when B was constructed). We can also find the starting position f 0 of the suffix S 0 of rank rf − 1,
S 0 = T [f 0 ..]. Since f 0 can be found by employing the function LF at most ∆0 times, we can compute
f 0 in O(∆0 ) time; see Section A.13 . When f and f 0 are known, we scan T [f..] and T [f 0 ..] until the
3

A faster computation is possible, but we do not need it here.

8

∆0

∆0

∆0

`0 `1 . . . `∆0 −1

J0

J1

Ji

Ql

J1 : rank(j1, a1)

Qb

Ji : rank(ji, ai)

Figure 1: Computing lengths during Stage 2. Groups corresponding to paused jobs are shown
shaded by slanted lines. Only selected groups are shown. The i-th job Ji is paused because we
have to answer a rank query on B; the job J1 is paused because we have to answer a rank query
on L. When Ql or Qb contains n/ log2 n queries, we answer a batch of rank queries contained in
Ql or Qb .
first symbol T [f + pf ] 6= T [f 0 + pf ] is found. By definition of `j , `0 = pf − 1. Suppose that `s∆0 for
s = 0, . . ., j − 1 are already computed and we have to compute `f for f = j∆0 and some j ≥ 1. We
already know the rank rf of suffix T [f..]. We find f 0 such that the suffix T [f 0 ..] is of rank rf − 1
in time O(∆0 ). We showed above that `f ≥ `(j−1)∆0 − ∆0 . Hence the first of symbols in T [f..] and
T [f 0 ..] are equal, where of = max(0, `(j−1)∆0 − ∆0 ). We scan T [f + of ..] and T [f 0 + of ..] until the
first symbol T [f +of +pf ] 6= T [f 0 +of +pf ] is found. By definition, `f = of +pf . Hence
P we compute
`f in O(∆0 + pf ) time for f = j∆0 and j = 1, . . ., bn/∆0 c. It can be shown
that
f pf = O(n).
P
0
0
Hence the total time needed to compute all selected `f is O((n/∆ )∆ + f pf ) = O(n). For every
f = j∆0 we also compute the interval of T [j∆0 ..j∆0 + `f ] in B and the interval of T [j∆0 ..j∆0 + `f ]
in B. We show in Section A.6 that all needed intervals can be computed in O(n) time.
Stage 2. We divide `i into groups of size ∆0 − 1 and compute the values of `k in every group using
a job. The i-th group contains lengths `k+1 , `k+2 , . . ., `k+∆0 −1 for k = i∆0 and i = 0, 1, . . .. All `k
in the i-th group will be computed by the i-th job Ji . Every Ji is either active or paused. Thus
originally we start with a list of n/∆0 jobs and all of them are active. All active jobs are executed
at the same time. That is, we scan the list of active jobs, spend O(1) time on every active job, and
then move on to the next job. When a job must answer a rank query, we pause it and insert the
query into a query list. There are two query lists: Ql contain rank queries on sequence L and Qb
contains rank queries on B. When Ql or Qb contains n/ log2 n queries, we answer all queries in Ql
(resp. in Qb ). The batch of queries is answered using Theorem 2, so that every query is answered
in O(1) time. Answers to queries are returned to jobs, corresponding jobs are re-activated, and we
continue scanning the list of active jobs. When all `k for i∆0 ≤ k < (i + 1)∆0 are computed, the
i-th job is finished; we remove this job from the pool of jobs and decrement by 1 the number of
jobs. See Fig. 1.
Every job Ji computes `k+1 , `k+2 , . . ., `k+∆0 −1 for k = i∆0 using the algorithm of Belazzougui [2].
When the interval of T [i + `k ..] in B and the interval of T [i + `k ..] in B are known, we compute
`k+1 . The procedure for computing `k+1 must execute one operation contractleft and `k+1 −
9

`k + 1 operations extendright. Operations contractleft and extendright are implemented as
described above. We must answer two rank queries on B and one rank query on L for every
extendright. Ignoring the time for these three rank queries, extendright takes constant time.
Rank queries on B and L are answered in batches, so that each rank query takes O(1) time. Hence
every operation extendright needs O(1) time. The job Ji needs O(`i∆0 +j − `i∆0 + j) time to
compute `i∆0 +1 , `i∆0 +1 , . . ., `i∆0 +j . All Ji are executed in O(n) time.
Stage 3. “Parallel processing” of jobs terminates when the number of jobs in the pool becomes smaller than 2n/ log2 n. Since every job computes ∆0 values of `i , there are at most
2n(log log σ/(log n log σ)) < 2n/ log n unknown values of `i at this point. We then switch to the
method of Stage 1 to compute the values of unknown `i . All remaining `i are sorted by i and processed in order of increasing i. For every unknown `i we compute the rank r of T [i..] in B. For the
suffix S 0 of rank r−1 we find its starting position f 0 in T , S 0 = T [f 0 ..]. Then we scan T [f 0 +`i−1 −1..]
and T [i + `i−1 − 1..] until the first symbol T [f 0 + `i−1 + j − 1] 6= T [f + `i−1 + j − 1] is found. We set
`i = `i−1 + j − 2 and continue with the next unknown `i . We spend O(∆0 + `i ) additional time for
every remaining `i ; hence the total time needed to compute all `i is O(n + (n/ log n)∆0 ) = O(n).
Every job during Stage 2 uses O(log n) bits of workspace. The total number of jobs in the job
list does not exceed n/∆0 . The total number of queries stored at any time in lists Ql and Qb does
not exceed n/ log2 n. Hence our algorithm uses O(n log σ) bits of workspace.
Lemma 2 If the BWT of a string T and the suffix tree topology for T are already known, then we
can compute the permuted LCP array in O(n) time and O(n log σ) bits.

6

Conclusions

We have shown that the Burrows-Wheeler Transform (BWT), the Compressed Suffix Array (CSA),
and the Compressed Suffix Tree (CST) can be built in deterministic O(n) time by an algorithm
that requires O(n log σ) bits of working space. Belazzougui independently developed an alternative
solution, which also builds within the same time and space the simpler part of our structures,
that is, the BWT and the CSA, but not the CST. His solution, that uses different techniques, is
described in the updated version of his ArXiV report [3] that extends his conference paper [2].
Our results have many interesting applications. For example, we can now construct an FMindex [14, 15] in O(n) deterministic time using O(n log σ) bits. Previous results need O(n log log σ)
time or rely on randomization [23, 2]. Furthermore Theorem 5 enables us to support the function
LF in O(1) time on an FM-index. In Section A.7 we describe a new index based on these ideas.
Another application is that we can now compute the Lempel-Ziv 77 and 78 parsings [29, 46, 47]
of a string T [0..n − 1] in deterministic linear time using O(n log σ) bits: Köppl and Sadakane [27]
recently showed that, if one has a compressed suffix tree on T , then they need only O(n) additional
(deterministic) time and O(z log n) bits to produce the parsing, where z is the resulting number
of phrases. Since z ≤ n/ logσ n, the space is O(n log σ) bits. With the suffix tree, they need to
compute in constant time any Ψ(i) and to move in constant time from a suffix tree node to its i-th
child. The former is easily supported as the inverse of the LF function using constant-time select
queries on B [19]; the latter is also easily obtained with current topology representations using
parentheses [36].
Yet another immediate application of our algorithm are index data structures for dynamic
document collections. If we use our compressed index, described in Section A.7, and apply Transformation 2 from [32], then we obtain an index data structure for a dynamic collection of documents that uses nHk + o(n log σ) + O(n logs n ) bits where Hk is the k-th order entropy and s is
10

a parameter. This index can count how many times a query pattern P occurs in a collection in
O(|P | log log n + log log σ log log n) time; every occurrence can be then reported in time O(s). An
insertion or a deletion of some document Tu is supported in O(|Tu | logε n) and O(|Tu |(logε n + s))
deterministic time respectively.
We believe that our technique can also improve upon some of the recently presented results on
bidirectional FM-indices [42, 5] and other scenarios where compressed suffix trees are used [6].
Acknowledgment. The authors wish to thank an anonymous reviewer of this paper for careful
reading and helpful comments.

11

References
[1] J. Barbay, F. Claude, T. Gagie, G. Navarro, and Y. Nekrich. Efficient fully-compressed sequence representations. Algorithmica, 69(1):232–268, 2014.
[2] D. Belazzougui. Linear time construction of compressed text indices in compact space. In
Proc. Symposium on Theory of Computing (STOC), pages 148–193, 2014.
[3] D. Belazzougui. Linear time construction of compressed text indices in compact space. CoRR,
abs/1401.0936, 2014.
[4] D. Belazzougui, P. Boldi, R. Pagh, and S. Vigna. Monotone minimal perfect hashing: searching
a sorted table with o(1) accesses. In Proc. 20th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 785–794, 2009.
[5] D. Belazzougui, F. Cunial, J. Kärkkäinen, and V. Mäkinen. Versatile succinct representations
of the bidirectional Burrows-Wheeler transform. In Proc. 21st Annual European Symposium
on Algorithms (ESA), pages 133–144, 2013.
[6] D. Belazzougui, F. Cunial, J. Kärkkäinen, and V. Mäkinen. Linear-time string indexing and
analysis in small space. CoRR, abs/1609.06378, 2016.
[7] D. Belazzougui and G. Navarro. Alphabet-independent compressed text indexing. ACM Transactions on Algorithms, 10(4):23:1–23:19, 2014.
[8] D. Belazzougui and G. Navarro. Optimal lower and upper bounds for representing sequences.
ACM Transactions on Algorithms, 11(4):31:1–31:21, Apr. 2015.
[9] D. Belazzougui, G. Navarro, and D. Valenzuela. Improved compressed indexes for full-text
document retrieval. Journal of Discrete Algorithms, 18:3–13, 2013.
[10] D. Belazzougui and S. J. Puglisi. Range predecessor and Lempel-Ziv parsing. In Proc. 27th
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2053–2071, 2016.
[11] M. Bender, R. Cole, E. Demaine, M. Farach-Colton, and J. Zito. Two simplified algorithms for
maintaining order in a list. In Proc. 10th Annual European Symposium on Algorithms (ESA),
LNCS 2461, pages 152–164, 2002.
[12] P. Dietz and D. Sleator. Two algorithms for maintaining order in a list. In Proc. 19th Annual
ACM Symposium on Theory of Computing (STOC), pages 365–372, 1987.
[13] M. Farach. Optimal suffix tree construction with large alphabets. In Proc. 38th Annual
Symposium on Foundations of Computer Science (FOCS), pages 137–143, 1997.
[14] P. Ferragina and G. Manzini. Indexing compressed text. Journal of the ACM, 52(4):552–581,
2005.
[15] P. Ferragina, G. Manzini, V. Mäkinen, and G. Navarro. Compressed representations of sequences and full-text indexes. ACM Transactions on Algorithms, 3(2):article 20, 2007.

12

[16] J. Fischer and P. Gawrychowski. Alphabet-dependent string searching with wexponential
search trees. In Proc. 26th Annual Symposium on Combinatorial Pattern Matching (CPM),
LNCS 9133, pages 160–171, 2015.
[17] M. Fredman and M. Saks. The cell probe complexity of dynamic data structures. In Proc.
21st Annual ACM Symposium on Theory of Computing (STOC), pages 345–354, 1989.
[18] M. L. Fredman and D. E. Willard. Trans-dichotomous algorithms for minimum spanning trees
and shortest paths. Journal of Computing and System Sciences, 48(3):533–551, 1994.
[19] A. Golynski, J. I. Munro, and S. S. Rao. Rank/select operations on large alphabets: a tool for
text indexing. In Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA),
pages 368–373, 2006.
[20] R. Grossi, A. Orlandi, R. Raman, and S. S. Rao. More haste, less waste: Lowering the redundancy in fully indexable dictionaries. In Proc. 26th International Symposium on Theoretical
Aspects of Computer Science (STACS), pages 517–528, 2009.
[21] R. Grossi and J. S. Vitter. Compressed suffix arrays and suffix trees with applications to text
indexing and string matching. SIAM Journal on Computing, 35(2):378–407, 2005.
[22] T. Hagerup, P. B. Miltersen, and R. Pagh. Deterministic dictionaries. Journal of Algorithms,
41(1):69 – 85, 2001.
[23] W. Hon, K. Sadakane, and W. Sung. Breaking a time-and-space barrier in constructing fulltext indices. SIAM Journal on Computing, 38(6):2162–2178, 2009.
[24] J. Kärkkäinen, P. Sanders, and S. Burkhardt. Linear work suffix array construction. Journal
of the ACM, 53(6):918–936, 2006.
[25] D. K. Kim, J. S. Sim, H. Park, and K. Park. Constructing suffix arrays in linear time. Journal
of Discrete Algorithms, 3(2-4):126–142, 2005.
[26] P. Ko and S. Aluru. Space efficient linear time construction of suffix arrays. Journal of Discrete
Algorithms, 3(2-4):143–156, 2005.
[27] D. Köppl and K. Sadakane. Lempel-Ziv computation in compressed space (LZ-CICS). In Proc.
26th Data Compression Conference (DCC), pages 3–12, 2016.
[28] S. Lee and K. Park. Dynamic rank-select structures with applications to run-length encoded
texts. In Proc. 18th Annual Symposium on Combinatorial Pattern Matching ( CPM), pages
95–106, 2007.
[29] A. Lempel and J. Ziv. On the complexity of finite sequences. IEEE Transactions on Information Theory, 22(1):75–81, 1976.
[30] E. M. McCreight. A space-economical suffix tree construction algorithm. Journal of the ACM,
23(2):262–272, 1976.
[31] J. I. Munro, Y. Nekrich, and J. S. Vitter. Fast construction of wavelet trees. In Proc. 21st
International Symposium on String Processing and Information Retrieval (SPIRE), pages 101–
110, 2014.
13

[32] J. I. Munro, Y. Nekrich, and J. S. Vitter. Dynamic data structures for document collections
and graphs. In Proc. 34th ACM Symposium on Principles of Database Systems (PODS), pages
277–289, 2015.
[33] G. Navarro and V. Mäkinen. Compressed full-text indexes. ACM Computing Surveys, 39(1):article 2, 2007.
[34] G. Navarro and Y. Nekrich. Top-k document retrieval in optimal time and linear space. In
Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1066–1077,
2012.
[35] G. Navarro and Y. Nekrich. Optimal dynamic sequence representations. In Proc. 24th Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 865–876. SIAM, 2013.
[36] G. Navarro and K. Sadakane. Fully-functional static and dynamic succinct trees. ACM Transactions on Algorithms, 10(3):article 16, 2014.
[37] D. Okanohara and K. Sadakane. A linear-time burrows-wheeler transform using induced
sorting. In Proc. 16th International Symposium String Processing and Information Retrieval
(SPIRE), pages 90–101, 2009.
[38] M. Ružić. Constructing efficient dictionaries in close to sorting time. In Proc. 35th International
Colloquium on Automata, Languages and Programming (ICALP), pages 84–95, 2008.
[39] K. Sadakane. New text indexing functionalities of the compressed suffix arrays. Journal of
Algorithms, 48(2):294–313, 2003.
[40] K. Sadakane. Compressed suffix trees with full functionality. Theory of Computing Systems,
41(4):589–607, 2007.
[41] K. Sadakane. Succinct data structures for flexible text retrieval systems. Journal of Discrete
Algorithms, 5(1):12–22, 2007.
[42] T. Schnattinger, E. Ohlebusch, and S. Gog. Bidirectional search in a string with wavelet trees
and bidirectional matching statistics. Inf. Comput., 213:13–22, 2012.
[43] E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249–260, 1995.
[44] P. Weiner. Linear pattern matching algorithms. In Proc. 14th Annual Symposium on Switching
and Automata Theory (FOCS), pages 1–11, 1973.
[45] D. E. Willard. A density control algorithm for doing insertions and deletions in a sequentially
ordered file in good worst-case time. Information and Computation, 97(2):150–204, 1992.
[46] J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3):337–343, 1977.
[47] J. Ziv and A. Lempel. Compression of individual sequences via variable length coding. IEEE
Transactions on Information Theory, 24(5):530–536, 1978.

14

A.1

Preliminaries

Rank and Select Queries The following two kinds of queries play a crucial role in compressed
indexes and other succinct data structures. Consider a sequence B[0..n − 1] of symbols over an
alphabet of size σ. The rank query ranka (i, B) counts how many times a occurs among the first
i+1 symbols in B, ranka (i, B) = |{ j | B[j] = a and 0 ≤ j < i }|. The select query selecta (i, B) finds
the position in B where a occurs for the i-th time, selecta (i, B) = j where j is such that B[j] = a
and ranka (j, B) = i. The third kind of query is the access query, access(i, B), which returns the
(i + 1)-th symbol in B, B[i]. If insertions and deletions of symbols in B must be supported, then
both kinds of queries require Ω(log n/ log log n) time [17]. If the sequence B is static, then we can
answer select queries in O(1) time and the cost of rank queries is reduced to Θ(log logloglogσ n ) [8].4
One important special case of rank queries is the partial rank query, rankB[i] (i, B). Thus a partial
rank query asks how many times B[i] occurred in B[0..i]. Unlike general rank queries, partial rank
queries can be answered in O(1) time [8]. In Section A.4 we describe a data structure for partial
rank queries that can be constructed in O(n) deterministic time. Better results can be achieved in
the special case when the alphabet size is σ = logO(1) n; in this case we can represent B so that
rank, select, and access queries are answered in O(1) time [15].
Suffix Tree and Suffix Array. A suffix tree for a string T [0..n − 1] is a compacted tree on the
suffixes of T . The suffix array is an array SA[0..n − 1] such that SA[i] = j if and only if T [j..] is the
(i + 1)-th lexicographically smallest suffix of T . All occurrences of a substring p in T correspond to
suffixes of T that start with p; these suffixes occupy a contiguous interval in the suffix array SA.
Compressed Suffix Array. A compressed suffix array (CSA) is a compact data structure that
provides the same functionality as the suffix array. The main component of CSA is the function
Ψ, defined by the equality SA[Ψ(i + 1)] = (SA[i] + 1) mod n. It is possible to regenerate the suffix
array from Ψ. We refer to [33] and references therein for a detailed description of CSA and for
trade-offs between space usage and access time.
Burrows-Wheeler Transform and FM-index. The Burrows-Wheeler Transform (BWT) of
a string T is obtained by sorting all possible rotations of T and writing the last symbol of every
rotation (in sorted order). The BWT is related to the suffix array as follows: BW T [i] = T [(SA[i]−1)
mod n]. Hence, we can build the BWT by sorting the suffixes and writing the symbols that precede
the suffixes in lexicographical order. This method is used in Section 2.
The FM-index uses the BWT for efficient searching in T . It consists of the following three main
components:
• The BWT of T .
• The array Acc[0..σ − 1] where Acc[i] holds the total number of symbols a ≤ i − 1 in T (or
equivalently, the total number of symbols a ≤ i − 1 in B).
• A sampled array SAMb for a sampling factor b: SAMb contains values of SA[i] if and only if
SA[i] mod b = 0 or SA[i] = n − 1.
The search for a substring P of length m is performed backwards: for i = m − 1, m − 2, . . ., we
identify the interval of p[i..m] in the BWT. Let B denote the BWT of T . Suppose that we know the
4

If we aim to use n log σ + o(n log σ) bits, then either select or access must cost ω(1). If, however, (1 + )n log σ
bits are available, for any constant  > 0, then we can support both queries in O(1) time.

15

interval B[i1 ..j1 ] that corresponds to p[i + 1..m − 1]. Then the interval B[i2 ..j2 ] that corresponds
to p[i..m − 1] is computed as i2 = rankc (i1 − 1, B) + Acc[c] and j2 = rankc (i2 , B) + Acc[c] − 1,
where c = P [i]. Thus the interval of p is found by answering 2m rank queries. We observe that the
interval of p in B is exactly the same as the interval of p in the suffix array SA.
Another important component of an FM-index is the function LF , defined as follows: if SA[j] =
i + 1, then SA[LF (j)] = i. LF can be computed by answering rank queries on B. Using LF we
can find the starting position of the r-th smallest suffix, SA[r], in O(b) applications of LF , where
b is the sampling factor; we refer to [33] for details. It is also possible to compute the function Ψ
by using select queries the BWT [28]. Therefore the BWT can be viewed as a variant of the CSA.
Using Ψ we can consecutively obtain positions of suffixes T [i..] in the suffix array: Let ri denote
the position of T [i..] in SA. Since T [n − 1..] = $ is the smallest suffix, r0 = Ψ(0). For i ≥ 1,
ri = Ψ(ri−1 ) by definition of Ψ. Hence we can consecutively compute each ri in O(1) time if we
have constant-time select queries on the BWT.
Compressed Suffix Tree. A compressed suffix tree consists of the following components:
• The compressed suffix array of T . We can use the FM-index as an implementation.
• The suffix tree topology. This component can be stored in 4n + o(n) bits [40].
• The permuted LCP array, or PLCP. The longest common prefix array LCP is defined as
follows: LCP [r] = j if and only if the longest common prefix between the suffixes of rank r
and r − 1 is of length j. The permuted LCP array is defined as follows: P LCP [i] = j if and
only if the rank of T [i..] is r and LCP [r] = j. A careful implementation of P LCP occupies
2n + o(n) bits [40].

A.2

Monotone List Labelling with Batched Updates

A direct attempt to dynamize the data structure of Section 3 encounters one significant difficulty.
An insertion of a new symbol a into a chunk C changes the positions of all the symbols that follow
it. Since symbols are stored in pairs (aj , i) grouped by symbol, even a single insertion into C can
lead to a linear number of updates. Thus it appears that we cannot support the batch of updates
on C in less than Θ(|C|) time. In order to overcome this difficulty we employ a monotone labeling
method and assign labels to positions of symbols. Every position i in the chunk is assigned an
integer label lab(i) satisfying 0 ≤ lab(i) ≤ σ · nO(1) and lab(i1 ) < lab(i2 ) if and only if i1 < i2 .
Instead of pairs (a, i) the sequence R will contain pairs (a, lab(i)).
When a new element is inserted, we have to change the labels of some other elements in order to
maintain the monotonicity of the labeling. Existing labeling schemes [45, 11, 12] require O(log2 n)
or O(log n) changes of labels after every insertion. In our case, however, we have to process large
batches of insertions. We can also assume that at most log n batches need to be processed. In our
scenario O(1) amortized modifications per insertion can be achieved, as shown below.
In this section we denote by C an ordered set that contains between σ and 2σ elements. Let
x1 ≤ x2 ≤ . . . ≤ xt denote the elements of C. Initially we assign the label lab(xi ) = i · d to the i-th
smallest element xi , where d = 4n. We associate an interval [lab(xi ), lab(xi+1 ) − 1] with xi . Thus
initially the interval of xi is [id, (i + 1)d − 1]. We assume that C also contains a dummy element
x0 = −∞ and lab(−∞) = 0. Thus all labels are non-negative integers bounded by O(σ · n).
Suppose that the k-th batch of insertions consists of m new elements y1 ≤ y2 ≤ . . . ≤ ym . Since
at most log n batches of insertions must be supported, 1 ≤ k ≤ log n. We say that an element yj is
16

in an interval I = [lab(xs ), lab(xe )] if xs < yj < xe . We denote by new(I) the number of inserted
elements in I. The parameter ρ(I) for an interval I is defined as the ratio of old and new elements
e−s+1
in I = [lab(xs ), lab(xe )], ρ(I) = new(I)
. We identify the set of non-overlapping intervals I1 , . . ., Ir
such that every new element yt is in some interval Ij , and 1 ≤ ρ(Ij ) ≤ 2 for all j, 1 ≤ j ≤ r. (This is
always possible if m ≤ |C|; otherwise we simply merge the insertions with C in O(|C| + m) = O(m)
time and restart all the labels.) We can find I1 , . . ., Ir in O(m) time. For every Ij , 1 ≤ j ≤ r,
we evenly distribute the labels of old and new elements in the interval Ij0 ⊆ Ij . Suppose that f
new elements yp , . . ., yp+f −1 are inserted into interval Ij = [lab(xs ), lab(xe )] so that now there are
v = f + (e − s) + 1 elements in this interval. We assign the label lab(xs ) + dj · (i − 1) to the i-th
)−lab(xs )
smallest element in Ij where dj = lab(xev−1
. By our choice of Ij , f ≤ e−s+1 and the number of
elements in Ij increased at most by twofold. Hence the minimal distance between two consecutive
labels does not decrease by more than a factor of 2 after insertion of new elements into Ij . We
inserted f new elements into Ij and changed the labels of at most 2f old elements. Hence the
amortized number of labels that we must change after every insertion is O(1). The initial distance
between labels is d = 4n and this distance becomes at most two times smaller after every batch
of insertions. Hence the distance between consecutive labels is an integer larger than 2 during the
first log n batches.
One remaining problem with our scheme is the large range of the labels. Since labels are integers
bounded by 4|C|n, we need Θ(log σ + log n) bits per label. To solve this problem, we will split the
chunk C into blocks and assign the same label to all the symbols in a block. A label assigned to
the symbols in a block will be stored only once. Details are provided in Section A.3.

A.3

Batched Rank Queries and Insertions on a Sequence

In this section we describe a dynamic data structure that supports both batches of rank queries
and batches of insertions. First we describe how queries and updates on a chunk C are supported.
The linked list L contains all the symbols of C in the same order as they appear in C. Each
node of L stores a block of Θ(logσ n) symbols, containing at most (1/4) logσ n of them. We will
identify list nodes with the blocks they contain; however, the node storing block b also stores the
total number of symbols in all preceding blocks and a label lab(b) for the block. Labels are assigned
to blocks with the method described in Section A.2. The pointer to (the list node containing) block
b will be called pb ; these pointers use O(log σ) bits.
We also maintain a data structure that can answer rank queries on any block. The data
structure for a block supports queries and insertions in O(1) time using a look-up table: Since
σ ≤ n1/4 and the block size is (1/4) logσ n, we can keep pre-computed answers to all rank queries
for all possible blocks in a table T bl[0..n1/4 − 1][0..n1/4 − 1][0.. logσ n − 1]. The entry T bl[b][a][i]
contains the answer to the query ranka (i, b) on a block b. T bl contains O(n1/2 logσ n) = o(n) entries
and can be constructed in o(n) time. Updates can be supported by a similar look-up table or by
bit operations on the block b.
We also use sequences R and R0 , defined in Section 3, but we make the following modifications.
For every occurrence C[i] = a of a symbol a in C, the sequence R contains pair (a, pb ), where pb
is a pointer to the block b of L that contains C[i]. Pairs are sorted by symbol in increasing order,
and pairs with the same symbol are sorted by their position in C. Unlike in Section 3, the chunk C
can be updated and we cannot maintain the exact position i of C[i] for all symbols in C; we only
maintain the pointers pb in the pairs (a, pb ) ∈ R.
Note that we cannot use block pointers for searching in L (or in C). Instead, block labels are
17

monotonously increasing and lab(b1 ) < lab(b2 ) if the block b2 follows b1 in L. Hence block labels
will be used for searching and answering rank queries. Block labels lab(b) use Θ(log n) bits of space,
so we store them only once with the list nodes b and access them via the pointers pb .
Groups Ha,j are defined as in Section 3; each Ha,j contains all the pairs of R that are between
two consecutive elements of Ra0 for some a. The data structure Da,j that permits searching in Ha,j
is defined as follows. Suppose that Ha,j contains pairs (a, pb1 ), . . ., (a, pbf ). We then keep a Succinct SB-tree data structure [20] on lab(b1 ), . . ., lab(bf ). This data structure requires O(log log n)
additional bits per label. For any integer q, it can find the largest block label lab(bi ) < q in O(1)
time or count the number of blocks bi such that lab(bi ) < q in O(1) time (because our sets Ha,r
contain a logarithmic number of elements). The search procedure needs to access one block label,
which we read from the corresponding block pointer.
Queries. Suppose that we want to answer queries ranka1 (i1 , C), ranka2 (i2 , C), . . ., rankat (it , C)
on a chunk C. We traverse all the blocks of L and find for every ij the label lj of the block bj that
contains the ij -th symbol, lj = lab(bj ). We also compute rj,1 = rankaj (i0j , bj ) using T bl, where i0j
is the relative position of the ij -th symbol in bj . Since we know the total number of symbols in all
the blocks that precede bj , we can compute i0j in O(1) time.
We then represent the queries by pairs (aj , lj ) and sort these pairs stably in increasing order of
aj . Then we traverse the list of query pairs (aj , lj ) and the sequence R0 . For every query (aj , lj )
we find the rightmost pair (aj , pj ) ∈ R0 satisfying lab(pj ) ≤ lj . Let rj,2 denote the rank of (aj , pj )
in Raj , i.e., the number of pairs (aj , i) ∈ R preceding (aj , pj ). We keep this information for every
pair in R0 using O(log σ) additional bits. Then we use the succinct SB-tree Daj ,pj , which contains
information about the pairs in Haj ,pj (i.e., the pairs in the group starting with (aj , pj )). The
structure finds in constant time the largest lab(bg ) ∈ Daj ,pj such that lab(bg ) < lj , as well as the
number rj,3 of pairs from the beginning of Haj ,pj up to the pair with label lab(bg ). The answer to
the j-th rank query is then rankaj (ij , C) = rj,1 + rj,2 + rj,3 .
The total query time is then O(σ/ logσ n + t).
Insertions. Suppose that symbols a1 , . . ., at are to be inserted at positions i1 , . . ., it , respectively.
We traverse the list L and identify the nodes where new symbols must be inserted. We simultaneously update the information about the number of preceding elements, for all nodes. All this is
done in time O(σ/ logσ n + t). We also perform the insertions into the blocks. If, as a result, some
block contains more than (1/4) logσ n symbols, we split it into an appropriate number of blocks,
so that each block contains Θ(logσ n) but at most (1/4) logσ n symbols. Nodes for the new blocks
are allocated5 , linked to the list L, and assigned appropriate labels using the method described
in Section A.2. After t insertions, we create at most O(t/ logσ n) new blocks (in the amortized
sense, i.e., if we consider the insertions from the beginning). Each such new block b0 , coming from
splitting an existing block b, requires that we change all the corresponding pointers pb from the
pairs (az , pb ) in R (and R0 ), so that they become (az , pb0 ). To find those pairs efficiently, the list
node holding b also contains the O(logσ n) pointers to those pairs (using O(log σ) bits each); we
can then update the required pointers in O(t) total time.
The new blocks also require creating their labels. Those O(t/ logσ n) label insertions also trigger
O(t/ logσ n) changes of other labels, with the technique of Section A.2. If the label of a block b
was changed, we visit all pairs (az , pb ) in R that point to b. Each such (az , pb ) is kept in some
5
Constant-time allocation is possible because we use fixed-size nodes, leaving the maximum possible space,
(1/4) log n bits, for the block contents.

18

group Haz ,k and in some succinct SB-tree Daz ,k . We then delete the old label of b from Daz ,k and
insert the new modified label. The total number of updates is thus bounded by O(t). While not
mntioned in the original paper [20], one can easily perform constant-time insertions
and deletions
√
of labels in a succinct SB-tree: The structure is a two-level B-tree of arity log n holding encoded
Patricia trees on the bits of the keys, and storing at the leaves the positions of the keys in Ha,r
using O(log log n) bits each. To insert or delete a label we follow the usual B-tree procedures. The
insertion or deletion of a key in a B-tree node is done in constant time with a precomputed table
that, in the same spirit of T bl, yields the resulting Patricia
tree if we delete or insert a certain node;
√
this is possible because internal nodes store only O( log n log log n) = o(log n) bits. Similarly, we
can delete or insert a key at the leaves of the tree.
Apart from handling the block overflows, we must insert in R the pairs corresponding to the
new t symbols we are actually inserting. We perform t rank queries ranka1 (i1 , C), . . ., rankat (it , C),
just as described above, and sort the symbols to insert by those ranks using radix sort. We then
traverse R0 and identify the groups Ha1 ,j1 , . . ., Hat ,jt where new symbols must be inserted; the
counters of preceding pairs for the pairs in R0 is easily updated in the way. We allocate the pairs
(ak , pbk ) that will belong to Hai ,ji and insert the labels lab(bk ) in the corresponding data structures
Dak ,jk , for all 1 ≤ k ≤ t. If some groups Hat ,jt become larger than permitted, we split them as
necessary and insert the corresponding pairs in R0 . We can answer the rank queries, traverse R,
and update the groups Hak ,jk all in O(σ/ logσ n + t) time.
Global Sequence. In addition to chunk data structures, we keep a static bitvector Ma =
1d1 0 . . . 1ds for every symbol a; di denotes the number of times a occurs in the i-th chunk.
Given a global sequence of m ≥ n/ logσ n queries, ranka1 (i1 , B), . . ., rankam (im , B) on B, we
can assign them to chunks in O(m) time. Then we answer queries on chunks as shown above. If mj
queries are asked on chunk Cj , then these queries are processed in O(mj + σ/ logσ n) time. Hence
all queries on all chunks are answered in O(m + n/ logσ n) = O(m) time. We can answer a query
rankak (ik , B) by answering a rank query on the chunk that contains B[ik ] and O(1) queries on the
sequence Mak [19]. Queries on Mak are supported in O(1) time because the bitvector is static.
Hence the total time to answer m queries on B is O(m).
When a batch of symbols is inserted, we update the corresponding chunks as described above.
If some chunk contains more than 4σ symbols, we split it into several chunks of size Θ(σ) using
standard techniques. Finally we update the global sequences Ma , both because of the insertions
and due to the possible chunk splits. We simply rebuild the bitvectors Ma from scratch; this is
easily done in O(na / log n) time, where na is the number of bits in Ma ; see e.g. [31]. This adds up
to O(m/ log n) time.
Hence the total amortized cost for a batch of m ≥ n/∆ insertions is O(m).
Theorem 4 We can keep a sequence B[0..n − 1] over an alphabet of size σ in O(n log σ) bits of
space so that a batch of m rank queries can be answered in O(m) time and a batch of m insertions
is supported in O(m) amortized time, for logn n ≤ m ≤ n.
σ

A.4

Sequences with Partial Rank Operation

If σ = logO(1) n, then we can keep a sequence S in O(n log σ) bits so that select and rank queries
(including partial rank queries) are answered in constant time [15]. In the remaining part of this
section we will assume that σ ≥ log3 n.
19

Lemma 3 Let σ ≤ m ≤ n. We can support partial rank queries on a sequence C[0..m − 1] over an
alphabet of size σ in time O(1). The data structure needs O(m log log m) additional bits and can
be constructed in O(m) deterministic time.
Proof : Our method employs the idea of buckets introduced in [4]. Our structure does not use
monotone perfect hashing, however. Let Ia denote the set of positions where a symbol a occurs in
C, i.e., Ia contains all integers i satisfying C[i] = a. If Ia contains more than 2 log2 m integers, we
divide Ia into buckets Ba,s of size log2 m. Let pa,s denote the longest common prefix of all integers
(seen as bit strings) in the bucket Ba,s and let la,s denote the length of pa,s . For every element C[i]
in the sequence we keep the value of lC[i],t where BC[i],t is the bucket containing i. If IC[i] was not
divided into buckets, we assume lC[i],t = null, a dummy value. We will show below how the index
t of BC[i],t can be identified if lC[i],t is known. For every symbol C[i] we also keep the rank r of i
in its bucket BC[i],t . That is, for every C[i] we store the value of r such that i is the r-th smallest
element in its bucket BC[i],t . Both lC[i],t and r can be stored in O(log log m) bits. The partial rank
of C[i] in C can be computed from t and r, rankC[i] (i, C) = t log2 m + r.
It remains to describe how the index t of the bucket containing C[i] can be found. Our method
uses o(m) additional bits. First we observe that pa,i 6= pa,j for any fixed a and i 6= j; see [4] for
a proof. Let Tw denote the full binary trie on the interval [0..m − 1]. Nodes of Tw correspond to
all possible bit prefixes of integers 0, . . . , m − 1. We say that a bucket Ba,j is assigned to a node
u ∈ Tw if pa,j corresponds to the node u. Thus many different buckets can be assigned to the same
node u. But for any symbol a at most one bucket Ba,k is assigned to u. If a bucket is assigned to
a node u, then there are at least log2 m leaves below u. Hence buckets can be assigned to nodes
of height at least 2 log log m; such nodes will be further called bucket nodes. We store all buckets
assigned to bucket nodes of Tw using the structure described below.
We order the nodes u level-by-level starting at the top of the tree. Let mj denote the number of
buckets assigned to uj . The data structure Gj contains all symbols a such that some bucket Ba,ka
is assigned to uj . For every symbol a in Gj we can find in O(1) time the index ka of the bucket
Ba,ka that is assigned to uj . We implement Gj as deterministic dictionaries of Hagerup et al. [22].
Gj uses O(mj log σ) bits and can be constructed in O(mj log σ) time. We store Gj only for bucket
nodes uj such that mj > 0. We also keep an array W [1.. logm2 m ] whose entries correspond to bucket
nodes of Tw : W [j] contains a pointer to Gj or null if Gj does not exist.
Using W and Gj we can answer a partial rank query rankC[i] (i, C). Let C[i] = a. Although the
bucket Ba,t containing i is not known, we know the length la,t of the prefix pa,t . Hence pa,t can be
computed by extracting the first la,t bits of i. We can then find the index j of the node uj that
corresponds to pa,t , j = (2la,t − 1) + pa,t . We lookup the address of the data structure Gj in W [j].
Finally the index t of the bucket Ba,t is computed as t = GP
j [a].
A data structure Gj consumes O(mj log m) bits. Since j mj ≤ logm2 m , all Gj use O(m/ log m)
bits of space. The array W also uses O(m/ log m) bits. Hence our data structure uses O(log log m)
additional bits per symbol.

Theorem 5 We can support partial rank queries on a sequence B using O(n log log σ) additional
bits. The underlying data structure can be constructed in O(n) deterministic time.
Proof : We divide the sequence B into chunks of size σ (except for the last chunk that contains
n − (bn/σcσ) symbols). Global sequences Ma are defined in the same way as in Section 3. A partial
rank query on B can be answered by a partial rank query on a chunk and two queries on Ma . 
20

A.5

Reporting All Symbols in a Range

We prove the following lemma in this section.
Lemma 4 Given a sequence B[0..n − 1] over an alphabet σ, we can build in O(n) time a data
structure that uses O(n log log σ) additional bits and answers the following queries: for any range
[i..j], report occ distinct symbols that occur in B[i..j] in O(occ) time, and for every reported symbol
a, give its frequency in B[i..j] and its frequency in B[0..i − 1].
The proof is the same as that of Lemma 3 in [2], but we use the result of Theorem 5 to
answer partial rank queries. This allows us to construct the data structure in O(n) deterministic
time (while the data structure in [2] achieves the same query time, but the construction algorithm
requires randomization). For completeness we sketch the proof below.
Augmenting B with O(n) additional bits, we can report all distinct symbols occurring in B[i..j]
in O(occ) time using the idea originally introduced by Sadakane [41]. For every reported symbol
we can find in O(1) time its leftmost and its rightmost occurrences in B[i..j]. Suppose ia and ja
are the leftmost and rightmost occurrences of a in B[i..j]. Then the frequencies of a in B[i..j] and
B[0..i−1] can be computed as ranka (ja , B)−ranka (ia , B)+1 and ranka (ia , B)−1 respectively. Since
ranka (ia , B) and ranka (ja , B) are partial rank queries, they are answered in O(1) time. The data
structure that reports the leftmost and the rightmost occurrences can be constructed in O(n) time.
Details and references can be found in [9]. Partial rank queries are answered by the data structure
of Theorem 5. Hence the data structure of Lemma 4 can be built in O(n) deterministic time. We
can also use the data structure of Lemma 5 to determine whether the range B[i..j] contains only
one distinct symbol in O(1) time by using the following observation. If B[i..j] contains only one
symbol, then B[i] = B[j] and rankB[i] (j, B) − rankB[i] (i, B) = j − i + 1. Hence we can find out
whether B[i..j] contains exactly one symbol in O(1) time by answering two partial rank queries.
This observation will be helpful in Section 5.

A.6

Computing the Intervals

The algorithm for constructing PLCP, described in Section 5, requires that we compute the intervals
of T [j∆0 ..j∆0 + `i ] and T [j∆0 ..j∆0 + `i ] for i = j∆0 and j = 0, 1, . . . , n/∆0 . We will show in this
section how all necessary intervals can be computed in linear time when `i for i = j∆0 are known.
Our algorithm uses the suffix tree topology. We construct some additional data structures and
pointers for selected nodes of the suffix tree T . First, we will describe auxiliary data structures on
T . Then we show how these structures can be used to find all needed intervals in linear time.

Marking Nodes in a Tree. We use the marking scheme described in [34]. Let d = log n. A
node u of T is heavy if it has at least d leaf descendants and light otherwise. We say that a heavy
node u is a special or marked node if u has at least two heavy children. If a non-special heavy
node u has more than d children and among them is one heavy child, then we keep the index of
the heavy child in u.
We keep all children of a node u in the data structure Fu , so that the child of u that is labeled
by a symbol a can be found efficiently. If u has at most d + 1 children, then Fu is implemented as
a fusion tree [18]; we can find the child of u labeled by any symbol a in O(1) time. If u has more
than d + 1 children, then Fu is implemented as the van Emde Boas data structure and we can find
the child labeled by a in O(log log σ) time. If the node u is special, we keep labels of its heavy
children in the data structure Du . Du is implemented as a dictionary data structure [22] so that
21

we can find any heavy child of a special node in O(1) time. We will say that a node u is difficult
if u is light but the parent of u is heavy. We can quickly navigate from a node u ∈ T to its child
ui unless the node ui is difficult.
Proposition 2 We can find the child ui of u that is labeled with a symbol a in O(1) time unless
the node ui is difficult. If ui is difficult, we can find ui in O(log log σ) time.
Proof : Suppose that ui is heavy. If u is special, we can find ui in O(1) time using Du . If u is not
special and it has at most d + 1 children, then we find ui in O(1) time using Fu . If u is not special
and it has more than d + 1 children, then ui is the only heavy child of u and its index i is stored
with the node u. Suppose that ui is light and u is also light. Then u has at most d children and
we can find ui in O(1) time using Fu . If u is heavy and ui is light, then ui is a difficult node. In
this case we can find the index i of ui in O(log log σ) time using Fu .

Proposition 3 Any path from a node u to its descendant v contains at most one difficult node.
Proof : Suppose that a node u is a heavy node and its descendant v is a light node. Let u0 denote
the first light node on the path from u to v. Then all descendants of u0 are light nodes and u0 is
the only difficult node on the path from u to v. If u is light or v is heavy, then there are apparently
no difficult nodes between u and v.

Weiner Links. A Weiner link (or w-link) wlink(v, c) connects a node v of the suffix tree T
labeled by the path p to the node u, such that u is the locus of cp. If wlink(v, c) = u we will say
that u is the target node and v is the source of wlink(v, c) and c is the label of wlink(v, c). If the
target node u is labeled by cp, we say that the w-link is explicit. If u is labeled by some path cp0 ,
such that cp is a proper prefix of cp0 , then the Weiner link is implicit. We classify Weiner links using
the same technique that was applied to nodes of the suffix tree above. Weiner links that share the
same source node are called sibling links. A Weiner link from v to u is heavy if the node u has at
least d leaf descendants and light otherwise. A node v is w-special iff there are at least two heavy
w-links connecting v and some other nodes. For every special node v the dictionary Dv0 contains
the labels c of all heavy w-links wlink(v, c). For every c such that wlink(v, c) is heavy, we also
keep the target node u = wlink(v, c). Dv0 is implemented as in [22] so that queries are answered
in O(1) time. Suppose that v is the source node of at least d + 1 w-links, but u = wlink(v, c) is
the only heavy link that starts at v. In this case we say that wlink(v, c) is unique and we store
the index of u and the symbol c in v. Summing up, we store only heavy w-links that start in a
w-special node or unique w-links. All other w-links are not stored explicitly; if they are needed, we
compute them using additional data structures that will be described below.
Let B denote the BWT of T . We split B into intervals Gj of size 4d2 . For every Gj we keep the
dictionary Aj of symbols that occur in Gj . For each symbol a that occurs in Gj , the data structure
Gj,a contains all positions of a in Gj . Using Aj , we can find out whether a symbol a occurs in Gj .
Using Gj,a , we can find for any position i the smallest i0 ≥ i such that B[i0 ] = a and B[i0 ] is in Gj
(or the largest i00 ≤ i such that B[i00 ] = a and B[i00 ] is in Gj ). We implement both Aj and Gj,a
as fusion trees [18] so that queries are answered in O(1) time. Data structures Aj and Gj,a for a
fixed j need O(d2 log σ) bits. We also keep (1) the data structure from [19] that supports select
queries on B in O(1) time and rank queries on B in O(log log σ) time and (2) the data structure
from Theorem 5 that supports partial rank queries in O(1) time. All additional data structures on
the sequence B need O(n log σ) bits.
22

Proposition 4 The total number of heavy w-links that start in w-special nodes is O(n/d).
Proof : Suppose that u is a w-special node and let p be the label of u. Let c1 , . . ., cs denote the
labels of heavy w-links with source node u. This means that each c1 p, c2 p, . . ., cs p occurs at least d
times in T . Consider the suffix tree T of the reverse text T . T contains the node u that is labeled
with p. The node u has (at least) s children u1 , . . ., us . The edge connecting u and ui is a string
that starts with ci . In other words each ui is the locus of pci . Since ci p occurs at least d times in
T , pci occurs at least d times in T . Hence each ui has at least d descendants. Thus every w-special
node in T correspond to a special node in T and every heavy w-link outgoing from a w-special
node corresponds to some heavy child of a special node in T . Since the number of heavy children
of special nodes in a suffix tree is O(n/d), the number of heavy w-links starting in a w-special node
is also O(n/d).

Proposition 5 The total number of unique w-links is O(n/d).
Proof : A Weiner link wlink(v, a) is unique only if wlink(v, a) is heavy, all other w-links outgoing
from v are light, and there are at least d light outgoing w-links from v. Hence there are at least d
w-links for every explicitly stored target node of a unique Weiner link.

We say that wlink(v, a) is difficult if its target node u = wlink(v, a) is light and its source node
v is heavy.
Proposition 6 We can compute u = wlink(v, a) of u in O(1) time unless wlink(v, a) is difficult.
If the wlink(v, a) is difficult, we can compute u = wlink(v, a) in O(log log σ) time.
Proof : Suppose that u is heavy. If v is w-special, we can find u in O(1) time using Du . If v
is not w-special and it has at most d + 1 w-children, then we find ui in O(1) time using data
structures on B. Let [lv , rv ] denote the suffix range of v. The suffix range of u is [lu , ru ] where
lu = Acc[a] + ranka (lv − 1, B) + 1 and ru = Acc[a] + ranka (rv , B). We can find ranka (rv , B)
as follows. Since v has at most d light w-children, the rightmost occurrence of a in B[lv , rv ] is
within the distance d2 from rv . Hence we can find the rightmost ia ≤ rv such that B[ia ] = a by
searching in the interval Gj that contains rv or the preceding interval Gj−1 . When ia is found,
ranka (rv , B) = ranka (ia , B) can be computed in O(1) time because partial rank queries on B are
supported in time O(1). We can compute ranka (lv − 1, B) in the same way. When rank queries are
answered, we can find lu and ru in constant time. Then we can identify the node u by computing
the lowest common ancestor of lu -th and ru -th leaves in T .
If v is not special and it has more than d + 1 outgoing w-links, then u is the only heavy target
node of a w-link starting at v; hence, its index i is stored in the node v. Suppose that u is light
and v is also light. Then the suffix range [lv , rv ] of v has length at most d. B[lv , rv ] intersects at
most two intervals Gj . Hence we can find ranka (lv − 1, B) and ranka (rv , B) in constant time. Then
we can find the range [lu , ru ] of the node u and identify u in time O(1) as described above. If v is
heavy and u is light, then wlink(v, a) is a difficult w-link. In this case we need O(log log σ) time to
compute ranka (lv − 1, B) and ranka (rv , B). Then we find the range [lu , ru ] and the node u is found
as described above.

Proposition 7 Any sequence of nodes u1 , . . ., ut where ui = wlink(ui−1 , ai−1 ) for some symbol
ai−1 contains at most one difficult w-link.
23

Proof : Let π denote the path of w-links that contains nodes u1 , . . ., ut . Suppose that a node u1
is a heavy node and ut is a light node. Let ul denote the first light node on the path π. Then all
nodes on the path from ul to ut are light nodes and wlink(ul−1 , al−1 ) is the only difficult w-link
on the path from u1 to ut . If u1 is light or ut is heavy, then all nodes on π are light nodes (resp.
all nodes on π are heavy nodes). In this case there are apparently no difficult w-links between u1
and ut .

Pre-processing. Now we show how we can construct above described auxiliary data structures
in linear time. We start by generating the suffix tree topology and creating data structures Fu and
Du for all nodes u. For every node u in the suffix tree we create the list of its children ui and their
labels in O(n) time. For every tree node u we can find the number of its leaf descendants using
standard operations on the suffix tree topology. Hence, we can determine whether u is a heavy or
a light node and whether u is a special node. When this information is available, we generate the
data structures Fu and Du .
We can create data structures necessary for navigating along w-links in a similar way. We visit
all nodes u of T . Let lu and ru denote the indexes of leftmost and rightmost leaves in the subtree
of u. Let B denote the BWT of T . Using the method of Lemma 4, we can generate the list of
distinct symbols in B[lu ..ru ] and count how many times every symbol occurred in B[lu ..ru ] in O(1)
time per symbol. If a symbol a occurred more than d times, then wlink(u, a) is heavy. Using this
information, we can identify w-special nodes and create data structures Du0 . Using the method
of [38], we can construct Du0 in O(nu log log nu ) time. By Lemma 4 the total number of target
nodes in all Du0 is O(n/d); hence we can construct all Du0 in o(n) time. We can also find all nodes
u with a unique w-link. All dictionaries Du0 and all unique w-links need O((n/d) log n) = O(n) bits
of space.
Supporting a Sequence of extendright Operations.
Lemma 5 If we know the suffix interval of a right-maximal factor T [i..i + j] in B and the suffix
interval of T [i..i + j] in B, the we can find the intervals of T [i..i + j + t] and T [i..i + j + t] in
O(t + log log σ) time.
Proof : Let T and T denote the suffix tree for the text T and let T denote the suffix tree of the reverse
text T . We keep the data structure for navigating the suffix tree T , described in Proposition 2 and
the data structure for computing Weiner links described in Proposition 6. We also keep the same
data structures for T . Let [`0,s , `0,e ] denote the suffix interval of T [i..i + j]; let [`00,s , `00,e ] denote
the suffix interval of T [i..i + j]. We navigate down the tree following the symbols T [i + j + 1], . . .,
T [i + j + t]. Let a = T [i + j + k] for some k such that 1 ≤ k ≤ t and suppose that the suffix interval
[`k−1,s , `k−1,e ] of T [i..i + j + k − 1] and the suffix interval [`0k−1,s , `0k−1,e ] of T [i..i + j + k − 1] are
already known. First, we check whether our current location is a node of T . If B[`0k−1,s , `0k−1,e ]
contains only one symbol T [i + j + k], then the range of T [i..i + j + k] is identical with the range
of T [i..i + j + k − 1]. We can calculate the range of T [i..i + j + k] in a standard way by answering
two rank queries on B and O(1) arithmetic operations; see Section A.1. Since B[`0k−1,s , `0k−1,e ]
contains only one symbol, rank queries that we need to answer are partial rank queries. Hence
we can find the range of T [i..i + j + k] in time O(1). If B[`0k−1,s , `0k−1,e ] contains more than one
symbol, then there is a node u ∈ T that is labeled with T [i..i + j + k − 1]; u = lca(`k−1,s , `k−1,e )
where lca(f, g) denotes the lowest common ancestor of the f -th and the g-th leaves. We find the
child u0 of the node u in T that is labeled with a = T [i + j + k]. We also compute the Weiner
24

link u0 = wlink(u, a) for a node u0 = lca(`0k−1,s , `0k−1,e ) in T . Then `0k,s = leftmost leaf(u0 ) and
`0k,e = rightmost leaf(u0 ). We need to visit at most t nodes of T and at most t nodes of T in
order to find the desired interval. By Proposition 2 and Proposition 3, the total time needed to
move down in T is O(t + log log σ). By Proposition 6 and Proposition 7, the total time to compute
all necessary w-links in T is also O(t + log log σ).

Finding the Intervals. The algorithm for computing PLCP, described in Section 5, assumes
that we know the intervals of T [j∆0 ..j∆0 +`i ] and T [j∆0 ..j∆0 + `i ] for i = j∆0 and j = 0, 1, . . . , n/∆0 .
These values can be found as follows. We start by computing the intervals of T [0..`0 ] and T [0..`0 ].
Suppose that the intervals of T [j∆0 ..j∆0 + `i ] and T [j∆0 ..j∆0 + `i ] are known. We can compute
`(j+1)∆0 as shown in Section 5. We find the intervals of T [(j+1)∆0 ..j∆0 +`i ] and T [(j + 1)∆0 ..j∆0 + `i ]
in time O(∆0 ) by executing ∆0 operations contractleft. Each operation contractleft takes con0
0
stant time. Then we calculate the intervals of T [(j+1)∆0 ..(j+1)∆0 +`i+1 ] and T [(j + 1)∆
P ..(j + 1)∆ + `i+1 ]
0
in O(log log σ + (`i+1 − `i + ∆ )) time using Lemma 5. We know from Section 5 that (`i+1 − `i ) =
O(n). Hence we compute all necessary intervals in time O(n + (n/∆0 ) log log σ) = O(n).

A.7

Compressed Index

In this section we show how our algorithms can be used to construct a compact index in deterministic
linear time. We prove the following result.
Theorem 6 We can construct an index for a text T [0..n − 1] over an alphabet of size σ in O(n)
deterministic time using O(n log σ) bits of working space. This index occupies nHk + o(n log σ) +
O(n logd n ) bits of space for a parameter d > 0. All occurrences of a query substring P can be counted
in O(|P | + log log σ) time; all occ occurrences of P can be reported in O(|P | + log log σ + occ · d)
time. An arbitrary substring P of T can be extracted in O(|P | + d) time.
An uncompressed index by Fischer and Gawrychowski [16] also supports counting queries in
O(|P | + log log σ) time; however their data structure uses Θ(n log n) bits. We refer to [7] for the
latest results on compressed indexes.
Interval Rank Queries. We start by showing how a compressed data structure that supports
select queries can be extended to support a new kind of queries that we dub small interval rank
queries. An interval rank query ranka (i, j, B) asks for ranka (i0 , B) and ranka (j 0 , B), where i0 and j 0
are the leftmost and rightmost occurrences of the symbol a in B[i..j]; if a does not occur in B[i..j],
we return null. An interval query ranka (i, j, B) is a small interval query if j − i ≤ 2 log2 σ. Our
compressed index relies on the following result.
Lemma 6 Suppose that we are given a data structure that supports access queries on a sequence
C[0..m] in time tselect . Then, using O(m log log σ) additional bits, we can support small interval
rank queries on C in O(tselect ) time.
Proof : We split C into groups Gi so that every group contains log2 σ consecutive symbols of S,
Gi = C[i log2 σ..(i + 1) log2 σ − 1]. Let Ai denote the set of symbols that occur in Gi . We would
need log σ bits per symbol to store Ai . Therefore we keep only a dictionary A0i implemented as
a succinct SB-tree [20]. A succinct SB-tree needs O(log log m) bits per symbol; using SB-tree, we
can determine whether a query symbol a is in Ai in constant time if we can access elements of Ai .
We can identify every a ∈ Ai by its leftmost position in Gi . Since Gi consists of log2 σ consecutive
symbols, a position within Gi can be specified using O(log log σ) bits. Hence we can access any
25

symbol of Ai in O(1) time. For each a ∈ Ai we also keep a data structure Ia,i that stores all
positions where a occurs in Gi . Positions are stored as differences with the left border of Gi : if
C[j] = a, we store the difference j − i log2 σ. Hence elements of Ia,i can be stored in O(log log σ)
bits per symbol. Ia,i is also implemented as an SB-tree.
Using data structures A0i and Ia,i , we can answer small interval rank queries. Consider a group
Gt = C[t log2 σ..(t + 1) log2 σ − 1], an index i such that t log2 σ ≤ i ≤ (t + 1) log2 σ, and a symbol
a. We can find the largest j ≤ i such that C[j] = a and C[j] ∈ Gt : first we look for the symbol a
in A0t ; if a ∈ A0t , we find the predecessor of j in Ia,t . An interval C[i..j] of size d ≤ log2 σ intersects
at most two groups Gt and Gt−1 . We can find the rightmost occurrence of a symbol a in [i, j]
as follows. First we look for the rightmost occurrence j 0 ≤ j of a in Gt ; if a does not occur in
C[t log2 σ..j], we look for the rightmost occurrence j 0 ≤ t log2 σ − 1 of a in Gt−1 . We can find the
leftmost occurrence i0 of a in C[i..j] using a symmetric procedure. When i0 and j 0 are found, we
can compute ranka (i0 , C) and ranka (j 0 , C) in O(1) time by answering partial rank queries. Using
the result of Theorem 5 we can support partial rank queries in O(1) time and O(m log log σ) bits.
Our data structure takes O(m log log m) additional bits: Dictionaries A0i need O(log log m) bits
per symbol. Data structures Ia,t and the structure for partial rank queries need O(m log log σ) bits.
We can reduce the space usage from O(m log log m) to O(m log log σ) using the same method as in
Theorem 5.

Compressed Index. We mark nodes of the suffix tree T using the method of Section A.6, but
we set d = log σ. Nodes of T are classified into heavy, light, and special as defined in Section A.6.
For every special node u, we construct a dictionary data structure Du that contains the labels of
all heavy children of u. If there is child uj of u, such that the first symbol on the edge from to u
to uj is aj , then we keep a in Du . For every aj ∈ Du we store the index j of the child uj . If a
heavy node u has only one heavy child uj and more than d light children, then we also store data
structure Du for such a node u. If a heavy node has less d children and one heavy child, then we
keep the index of the heavy child using O(log d) = O(log log σ) bits.
The second component of our index is the Burrows-Wheeler Transform B of the reverse text
T . We keep the data structure that supports partial rank, select, and access queries on B. Using
e.g., the result from [1], we can support access queries in O(1) time while rank and select queries
are answered in O(log log σ) time. Moreover we construct a data structure, described in Lemma 6,
that supports rank queries on a small interval in O(1) time. We also keep the data structure of
Lemma 4 on B; using this data structure, we can find in O(1) time whether an arbitrary interval
B[l..r] contains exactly one symbol. Finally we explicitly store answers to selected rank queries.
Let B[lu ..ru ] denote the range of P u , where Pu is the string that corresponds to a node u and P u
is the reverse of Pu . For all data structures Du and for every symbol a ∈ Du we store the values of
ranka (lu − 1, B) and ranka (ru , B).
We will show later in this section that each rank value can be stored in O(log σ) bits. Thus Du
needs O(log σ) bits per element. The total number of elements in all Du is equal to the number of
special nodes plus the number of heavy nodes with one heavy child and at least d light children.
Hence all Du contain O(n/d) symbols and use O((n/d) log σ) = O(n) bits of space. Indexes of heavy
children for nodes with only one heavy child and at most d light children can be kept in O(log log σ)
bits. Data structure that supports select, rank, and access queries on B uses nHk (T ) + o(n log σ)
bits. Auxiliary data structures on B need O(n) + O(n log log σ) bits. Finally we need O(n logd n ) bits
to retrieve the position of a suffix in T in O(d) time. Hence the space usage of our data structure
is nHk (T ) + o(n log σ) + O(n) + O(n logd n ).
26

Queries. Given a query string P , we will find in time O(|P | + log log σ) the range of the reversed
string P in B. We will show below how to find the range of P [0..i] if the range of P [0..i − 1] is
known. Let [lj ..rj ] denote the range of P [0..j], i.e., P [0..j] is the longest common prefix of all suffixes
in B[lj ..rj ]. We can compute lj and rj from lj−1 and rj−1 as lj = Acc[a] + ranka (lj−1 − 1, B) + 1
and rj = Acc[a] + ranka (rj−1 , B) for a = P [j] and j = 0, . . . , |P |. Here Acc[f ] is the accumulated
frequency of the first f − 1 symbols. Using our auxiliary data structures on B and additional
information stored in nodes of the suffix tree T , we can answer necessary rank queries in constant
time (with one exception). At the same time we traverse a path in the suffix tree T until the locus
of P is found or a light node is reached. Additional information stored in selected tree nodes will
help us answer rank queries in constant time. A more detailed description is given below.
Our procedure starts at the root node of T and we set l−1 = 0, r−1 = n − 1, and i = 0. We
compute the ranges B[li ..ri ] that correspond to P [0..i] for i = 0, . . . , |P |. Simultaneously we move
down in the suffix tree until we reach a light node. Let u denote the last visited node of T and let
a = P [i]. We denote by ua the next node that we must visit in the suffix tree, i.e., ua is the locus of
P [0..i]. We can compute li and ri in O(1) time if ranka (ri−1 , B) and ranka (li−1 − 1, B) are known.
We will show below that these queries can be answered in constant time because either (a) the
answers to rank queries are explicitly stored in Du or (b) the rank query that must be answered is
a small interval rank query. The only exception is the situation when we move from a heavy node
to a light node in the suffix tree; in this situation the rank query takes O(log log σ) time. For ease
of description we distinguish between the following four cases.
(i) Node u is a heavy node and a ∈ Du . In this case we identify the heavy child uj of u that is
labeled with a. We can also find li and ri in time O(1) because ranka (li−1 , B) and ranka (ri−1 , B)
are stored in Du .
(ii) Node u is a heavy node and a 6∈ Du or we do not keep the dictionary Du for the node u.
In this case u has at most one heavy child and at most d light children. If ua is a heavy node
(case iia), then the leftmost occurrence of a in B[li−1 ..ri−1 ] is within d2 symbols of li−1 and the
rightmost occurrence of a in B[li−1 ..ri−1 ] is within d2 symbols of ri−1 . Hence we can find li and ri
by answering small interval rank queries ranka (li−1 , li−1 +d2 ) and ranka (ri−1 −d2 , ri−1 ) respectively.
If ua is a light node (case iib), we answer two standard rank queries on B in order to compute li
and ri .
(iii) If u is a light node, then P [0..i − 1] occurs at most d times. Hence P [0..i − 1] also occurs at
most d times and ri−1 − li−1 ≤ d. Therefore we can compute ri and li in O(1) time by answering
small interval rank queries.
(iv) We are on an edge of the suffix tree between a node u and some child uj of u. In this case
all occurrences of P [0..i − 1] are followed by the same symbol a = P [i]. Hence all occurrences
of P [0..i − 1] are preceded by P [i] in the reverse text. Therefore B[li−1 ..ri−1 ] contains only one
symbol a = P [i]. In this case ranka (ri−1 , B) and ranka (li−1 − 1, B) are partial rank queries; hence
li and ri can be computed in O(1) time.
In all cases, except for the case (iia), we can answer rank queries and compute li and ri in O(1)
time. In case (iia) we need O(log log σ) time answer rank queries. However case (iia) only takes
place when the node u is heavy and its child ua is light. Since all descendants of a light node are
light, case (iia) occurs only once when the pattern P is processed. Hence the total time to find the
range of P in B is O(|P | + log log σ) time. When the range is known, we can count and report all
occurrences of P in standard way.

27

Construction Algorithm. We can construct the suffix tree T and the BWT B in O(n) deterministic time. Then we can visit all nodes of T and identify all nodes u for which the data structure
Du must be constructed. We keep information about nodes for which Du will be constructed in a
bit vector. For every such node we also store the list of its heavy children with their labels. To
compute additional information for Du , we traverse the nodes of T one more time using a variant
of depth-first search. When a node u ∈ T is reached, we know the interval [lu , ru ] of su in B,
where su is the string that labels the path from the root to a node u ∈ T . We generate the list
of all children ui of u and their respective labels ai . If we store a data structure Du for the node
u, we identify labels ah of heavy children uh of u. For every ah we compute rankah (lu − 1, B) and
rankah (ru , B) and add this information to Du . Then we generate the intervals that correspond to
all strings su ai in B and keep them in a list List(u). Since intervals in List(u) are disjoint, we can
store List(u) in O(σ log n) bits.
We can organize our traversal in such way that only O(log n) lists List(u) need to be stored.
Let num(u) denote the number of leaves in the subtree of a node u. We say that a node is small if
num(ui ) ≤ num(u)/2 and big otherwise. Every node can have at most one big child. When a node
u processed and List(u) is generated, we visit small children ui of u in arbitrary order. When all
small children ui are visited and processed, we discard the list L(u). Finally if u has a big child ub ,
we visit ub . If a node u is not the root node and we keep List(u), then num(u) ≤ num(parent(u))/2.
Therefore we keep List(u) for at most O(log n) nodes u. Thus the space we need to store all List(u)
is O(σ log2 n) = o(n) for σ ≤ n1/2 . Hence the total workspace used of our algorithm is O(n log σ).
The total number of rank queries that we need to answer is O(n/d) because all Du contain O(n/d)
elements. We need O((n/d) log log σ) time to construct all Du and to answer all rank queries. The
total time needed to traverse T and collect necessary data about heavy nodes and special nodes is
O(n). Therefore our index can be constructed in O(n) time.
It remains to show how we can store selected precomputed answers to rank queries in O(log σ)
bits per query. We divide the sequence B into chunks of size σ 2 . For each chunk and for every
symbol a we encode the number of a’s occurrences per chunk in a binary sequence Aa , Aa =
1d1 01d2 0 . . . 1di 0 . . . where di is equal to the number of times a occurs in the i-th chunk. If a symbol
B[i] is in the chunk Ch, then we can answer ranka (i, B) by O(1) queries on Aa and a rank query
on Ch; see e.g., [19]. Suppose that we need to store a pre-computed answer to a query ranka (i, B);
we store the answer to ranka (i0 , Ch) where Ch is the chunk that contains i and i0 is the relative
position of B[i] in Ch. Since a chunk contain σ 2 symbols, ranka (i0 , Ch) ≤ σ 2 and we can store the
answer to ranka (i0 , Ch) in O(log σ) bits. When the answer to the rank query on Ch is known, we
can compute the answer to ranka (i, B) in O(1) time.

28

