Johannes Fischer, Dominik Köppl, and Florian Kurpicz 2111
10.4230/LIPIcs.xxx.yyy.p

# On the Benefit of Merging Suffix Array Intervals for Parallel Pattern
Matching

Johannes Fischer  Dept. of Computer Science, Technische Universität Dortmund,
Germany
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Dominik Köppl  Dept. of Computer Science,
Technische Universität Dortmund, Germany
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Florian Kurpicz  Dept. of Computer Science,
Technische Universität Dortmund, Germany
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We present parallel algorithms for exact and approximate pattern matching with
suffix arrays, using a CREW-PRAM with $p$ processors. Given a static text of
length $n$, we first show how to compute the suffix array interval of a given
pattern of length $m$ in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\frac{m}{p}+\lg p+\lg\lg
p\cdot\lg\lg n\right)$ time for $p\leq m$. For approximate pattern matching
with $k$ differences or mismatches, we show how to compute all occurrences of
a given pattern in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\frac{m^{k}\sigma^{k}}{p}\max\left(k,\lg\lg
n\right)\\!+\\!(1+\frac{m}{p})\lg p\cdot\lg\lg n+\text{occ}\right)$ time,
where $\sigma$ is the size of the alphabet and $p\leq\sigma^{k}m^{k}$. The
workhorse of our algorithms is a data structure for merging suffix array
intervals quickly: Given the suffix array intervals for two patterns $P$ and
$P^{\prime}$, we present a data structure for computing the interval of
$PP^{\prime}$ in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg\lg
n\right)$ sequential time, or in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(1+\lg_{p}\lg n\right)$
parallel time. All our data structures are of size
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\right)$ bits (in addition
to the suffix array).

###### Key words and phrases:

parallel algorithms, pattern matching, approximate string matching

###### 1991 Mathematics Subject Classification:

I.1.2 Algorithms

##  1\. Introduction

We consider parallelizing indexed pattern matching queries in static texts,
using (compressed) suffix arrays [14, 16] and (compressed) suffix trees [17,
19] as underlying indexes. We work with the _concurrent read exclusive write_
(CREW) _parallel random access machine_ (PRAM) with $p$ processors, as this
model most accurately reflects the design of existing multi-core CPUs. Our
starting point is that a (possibly very long) pattern can be split up into
several subpatterns that can be matched in parallel. In a suffix array, this
will result in $p$ intervals, each corresponding to one of the subpatterns.
These intervals, called _subintervals_ , will then be combined (using a merge
tree approach) to finally yield the interval for the entire pattern. From this
interval, all occurrences of the pattern in the text could then be easily
listed.

We also consider parallel indexed pattern matching with $k$ errors, again
using the same indexes as in the exact case. Here, we follow the approach of
Huynh et al. [10], whose basic idea is to first make all possible
modifications of the pattern within distance $k$, and then match those
modifications in the suffix array. To avoid repeated computations of
subintervals, a preprocessing is performed for every prefix and suffix of the
pattern. We show how to parallelize both steps (preprocessing and the actual
matching), resulting in a fast parallel matching algorithm. We stress that in
the case of approximate pattern matching, parallel pattern matching algorithms
are of even more practical importance than in the exact case, as this is an
inherently time-consuming task in the sequential case, even for short
patterns.

###  1.1. Our Results

In the abstract, we stated the results for uncompressed suffix arrays [14] as
the underlying index, which requires
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\lg n\right)$ bits of space
for a text of length $n$. However, there exists a wealth of compressed
versions of suffix arrays (CSAs) [16], which are smaller (using
$\left|\textup{CSA}\right|$ bits), but often have nonconstant access time
$t_{\textsf{SA}}$. (See also Figure 1 for known trade-offs.) Here, we state
our results more generally, using the parameters $\left|\textup{CSA}\right|$
and $t_{\textsf{SA}}$.

Our first result (Thm. 4.6) is an index of size
$\left|\textup{CSA}\right|+\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\right)$
bits that, with $p\leq m$ processors, allows us to compute the suffix array
interval of a pattern of length $m$ in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\left(\frac{m}{p}+\lg
p+\lg\lg p\cdot\lg\lg n\right)\right)$ time and
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\left(m+\min\left(p,\lg
n\right)\left(\lg p+\lg\lg p\cdot\lg\lg n\right)\right)\right)$ work. Our
second result (Thm. 5.6) is an index of the same size
$\left|\textup{CSA}\right|+\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\right)$
bits that can find all occ occurrences of a pattern in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\left(\frac{m^{k}\sigma^{k}}{p}\max\left(k,\lg\lg
n\right)+(1+\frac{m}{p})\lg p\cdot\lg\lg n\right)+\text{occ}\right)$ time, for
$p\leq m^{k}\sigma^{k}$. Both results rely on the ability to merge two suffix
array intervals quickly, a task for which we give a data structure of size
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\right)$ bits on top of CSA
that allows us to do the merging in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\lg
n\right)$ sequential (Lemma 3.7) or in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}(1+\lg_{p}\lg
n)\right)$ parallel time (Lemma 4.4).

###  1.2. Related Work

We are only aware of one article addressing the parallelization of single
queries [11]. Their main result is to augment a suffix tree with a data
structure of size $\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\lg
p\right)$ words that answers pattern matching queries using
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\frac{m}{p}\lg p\right)$ time
and $\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(m\lg p\right)$ work,
which is worse than ours in all three dimensions. Parallelizing approximate
pattern matching has not been done earlier, to the best of our knowledge.
Another natural approach for exploiting parallelism would be distributing the
patterns to be matched onto the different processors and answer them in
parallel; this is more of a load balancing problem and cannot be compared with
our approach. Parallel construction of text indices is another road of
research [4, 12], and could easily be combined with our approach. Finally, in
the early 1990’s, some work has been done on parallelizing online pattern
matching algorithms [2, 3].

##  2\. Preliminaries

Let $T=t_{1}\dots t_{n}$ be a _text_ of length $n$ consisting of characters
contained in an integer _alphabet_ $\Sigma$ of size
$\sigma=\left|\Sigma\right|=n^{\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(1\right)}$.
$T[i..j]$ represents the _substring_ $t_{i}\dots t_{j}$ for $1\leq i\leq j\leq
n$. We call $T[i..n]$ the $i$-th _suffix_ of $T$ and $T[1..i]$ the $i$-th
_prefix_ of $T$. We denote the length of the _longest common prefix_ of the
$i$-th and $j$-th suffix, i.e., $T[i..n]$ and $T[j..n]$, by
$\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left(i,j\right)$. The _suffix
array_ of a text $T$ of length $n$ is a permutation of
$\left\\{1,\dots,n\right\\}$ such that $T[\textsf{SA}[i]..n]$ is
lexicographically smaller than $T[\textsf{SA}[i+1]..n]$ for all
$i=1,\dots,n-1$. We denote the inverse of SA with $\textsf{SA}^{-1}$.

An _interval_ $\mathop{}\mathopen{}\mathcal{I}\mathopen{}\ =[b..e]$ is the set
of consecutive integers from $b$ to $e$, for $b\leq e$. For an interval
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}$, we use the notations
$\mathsf{b}(\mathop{}\mathopen{}\mathcal{I}\mathopen{})$ and
$\mathsf{e}(\mathop{}\mathopen{}\mathcal{I}\mathopen{})$ to denote the
beginning and end of $\mathop{}\mathopen{}\mathcal{I}\mathopen{}$; i.e.,
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\
=[\mathsf{b}(\mathop{}\mathopen{}\mathcal{I}\mathopen{})..\mathsf{e}(\mathop{}\mathopen{}\mathcal{I}\mathopen{})]$.
We write $\left|\mathop{}\mathopen{}\mathcal{I}\mathopen{}\right|$ to denote
the length of $\mathop{}\mathopen{}\mathcal{I}\mathopen{}$; i.e.,
$\left|\mathop{}\mathopen{}\mathcal{I}\mathopen{}\right|=\mathsf{e}(\mathop{}\mathopen{}\mathcal{I}\mathopen{})-\mathsf{b}(\mathop{}\mathopen{}\mathcal{I}\mathopen{})+1$.

For a pattern $\alpha\in\Sigma^{*}$, let
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha\right)$ be the
interval with $T[\textsf{SA}[i]..\textsf{SA}[i]+|\alpha|-1]=\alpha\iff
i\in\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha\right)$. If we
consider two intervals
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha\right)$ and
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\beta\right)$ and the
corresponding merged interval
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha\beta\right)$, we call
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha\right)$ the _left
side_ interval, $\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\beta\right)$
the _right side_ interval. Let
$\Psi^{k}[i]=\textsf{SA}^{-1}\left[\textsf{SA}[i]+k\right]$ be the position of
the suffix $T[\textsf{SA}[i]+k..n]$ in the suffix array.

###  2.1. Suffix Trees

The _suffix tree_ of a text $T$ is the tree obtained by compacting the trie of
all suffixes of $T$; it has $n$ leaves and less than $n$ internal nodes, where
$n$ is the length of $T$. Each edge is labeled with a string. We enumerate the
leaves from left to right such that the $i$-th leaf has $i-1$
lexicographically preceding suffixes; we write
$\mathop{}\mathopen{}\mathsf{leafrank}\mathopen{}\left(\ell\right)=i$ if the
leaf $\ell$ is the $i$-th leaf. We extend the notion of intervals to nodes;
i.e., $\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(v\right)$ denotes the
interval $[b..e]$ such that $\textsf{SA}[b],\dots,\textsf{SA}[e]$ are exactly
the suffixes below node $v$.

Since we target small space bounds, our focus is on a compressed
representation of suffix trees [19, 17, 6, 7]. The main ingredient of the so-
called compressed suffix tree is a _compressed suffix array_ [16]. Depending
on its implementation, a compressed suffix array takes
$\left|\textup{CSA}\right|$ bits of space, and gives $t_{\textsf{SA}}$ time
access to SA and $\textsf{SA}^{-1}$ – see Figure 1 for a comparison of the
uncompressed and a compressed suffix array. With additional
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\right)$ [19] or even $o(n)$
bits [5], a compressed suffix tree can answer queries on the LCP-array that
stores the values
$\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[i]},{\textsf{SA}[i+1]}\right)$
for each $1\leq i\leq n-1$. The last ingredient of a compressed suffix tree is
the tree topology (either explicitly [19] or implicitly [17]), and $o(n)$-bit
succinct data structures for navigating in it [20, 9].

For our purpose, we need the following queries on the suffix tree:
$\mathop{}\mathopen{}\mathsf{lca}\mathopen{}\left(u,v\right)$ returns the
lowest common ancestor of two nodes $u$ and $v$,
$\mathop{}\mathopen{}\mathsf{label}\mathopen{}\left(e\right)$ returns the
label of an edge $e$,
$\mathop{}\mathopen{}\mathsf{pathlabel}\mathopen{}\left(v\right)$ returns the
labels on the edges of the path from the root to $v$. These queries can be
answered by all common compressed suffix trees [17, 19, 6, 7].

$\left|\textup{CSA}\right|$ $t_{\textsf{SA}}$ reference $2n\lg n$
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(1\right)$ [14]
$(1+\epsilon)n\lg n$
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\epsilon\right)$ [15]
$nH_{k}+{\mathop{}\mathopen{}o\mathopen{}\left(nH_{k}\right)}+{\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n+\sigma^{k+1}\lg
n+n\lg n/s\right)}$ $\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg
s\right)$ [1]

Figure 1. Different representations of the compressed suffix array using
$\left|\textup{CSA}\right|$ bits with the time bound $t_{\textsf{SA}}$ for
accessing a value of SA and $\textsf{SA}^{-1}$. The sampling rate $s$
satisfies $s=\omega(\lg_{\sigma}n)$.

###  2.2. Integer Dictionaries

An _integer dictionary_ is a set consisting of tuples of the form $(k,v)$,
where $k\in U:=\left[1..\left|U\right|\right]$ is an integer from a universe
$U$ with
$\left|U\right|=n^{\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(1\right)}$;
we call $k$ a _key_ and $v$ a _value_. A common task is to find a tuple in a
dictionary by a given key. Besides, we might be interested in finding the
_successor_ (_predecessor_) of a key $k$, i.e., the largest (smallest) key
$k^{\prime}$ in the dictionary with $k^{\prime}\leq k$ ($k^{\prime}\geq k$).
We define the operations
$\mathop{}\mathopen{}\mathsf{key}\mathopen{}\left((k,v)\right)=k$ and
$\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left((k,v)\right)=v$.

A well-known _dynamic_ integer dictionary representation is the _$y$ -fast
trie_ [23]. It can perform lookups, predecessor and successor queries in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg\lg n\right)$ expected
time, and uses $\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\lg n\right)$
bits of space for storing $n$ elements. It consists of an $x$-fast trie whose
leaves store binary search trees. In more detail, the $x$-fast trie stores
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n/\lg n\right)$ entries in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg n\right)$ hash tables,
and each leaf stores $\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg
n\right)$ entries in its balanced binary search tree. Here, we only need a
_static_ version. Therefore, we use perfect hashing [8] as our hashing method,
resulting in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg\lg n\right)$
time w.h.p. in worst case for all queries, while keeping the same space bounds
and linear deterministic construction time. Alternatively, we can construct
the hash tables in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\lg\lg
n\right)$ deterministic time [18, Theorem 1], resulting in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg\lg n\right)$
deterministic worst case time for all queries. Further, we exchange the
balanced binary search trees with sorted arrays, which will be useful later
when we parallelize the queries.

##  3\. Suffix Array Interval Merging

To perform the merging of two suffix array intervals in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\lg
n\right)$ time, we adapt the idea from Lam et al. [13, Lemma 19]. In their
method, the aim is to output all occurrences resulting from the merging of two
suffix array intervals in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}(\lg\lg
n+\text{occ})\right)$ time. Here, we show how to modify their approach such
that only the resulting interval is returned, leading to
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\lg
n\right)$ time. Although our method is similar to Lam et al. [13], we give the
full proof for completeness.

The idea is to sample the $\Psi$\- and
$\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}$-values of each $(\lg^{2}n)$-th
suffix array position. The sampling is stored in $y$-fast tries such that a
search in a sorted array can be broken down to a $y$-fast trie query, or to a
binary search on a range of size
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg^{2}n\right)$ – both can
be performed in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg\lg
n\right)$ time. To lower the space consumption, the sampling is done only for
certain nodes determined by the heavy path decomposition of the suffix tree,
whose definition follows.

###  3.1. Heavy Path Decomposition

The _heavy path decomposition_ of a rooted tree assigns a _level_ to each node
of the tree. The level of the root is $1$. A node inherits the level of its
parent if its subtree is the largest among the subtrees of all its siblings
(ties are broken arbitrarily); we call such a node _heavy_. Otherwise, it has
the level of its parent incremented by one; we then call the node _light_.
Further, we define the root to be light. A maximal connected subgraph
consisting of nodes on the same level is called _heavy path_. A heavy path
starts with a light node, called _head_ , and ends at a heavy leaf.

###  3.2. Precomputed Data Structures

We first present a simple data structure for the child-operation
$\mathop{}\mathopen{}\mathsf{child}\mathopen{}\left(u,c\right)$ in a
(compressed) suffix tree, i.e., for finding the child $v$ of $u$ such that the
label of the edge between $u$ and $v$ starts with character $c$. We use
$\Delta=\Omega(\lg n)$ as the sampling rate throughout this section.

######  Lemma 3.1.

The suffix tree of a text of length $n$ can be augmented with a data structure
of size $\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\lg n/\Delta\right)$
bits answering $\mathop{}\mathopen{}\mathsf{child}\mathopen{}\left(v,c\right)$
in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\Delta\right)$
time.

######  Proof 3.2.

We sample the children of each internal node $u$ and store the sampled
children in a $y$-fast trie with the first character of the edge label between
$u$ and the respective child as key. Given a node $u$ with $k$ children, we
sample every $\Delta$-th child of $u$ so that $u$’s $y$-fast trie contains
$\left\lfloor k/\Delta\right\rfloor$ elements. Since the suffix tree has less
than $2n$ nodes, storing the $y$-fast tries for all internal node takes
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\lg n/\Delta\right)$ bits
overall.

Given a character $c$, we search
$\mathop{}\mathopen{}\mathsf{child}\mathopen{}\left(u,c\right)$ in the
following way: Since the children of a node $u$ are sorted by the first
character of the edge connecting $u$ with its respective child, the $y$-fast
trie of $u$ can retrieve the first child $v$ whose edge label
$\mathop{}\mathopen{}\mathsf{label}\mathopen{}\left(u,v\right)$ is
lexicographically at least as large as $c$. If $c$ is a prefix of
$\mathop{}\mathopen{}\mathsf{label}\mathopen{}\left(u,v\right)$, then we are
done. Otherwise, say that $v$ is the $i$-th child of $u$, we can find
$\mathop{}\mathopen{}\mathsf{child}\mathopen{}\left(u,c\right)$ by a binary
search on the range between the $(i-\Delta)$-th child and the $i$-th child in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\Delta\right)$
time.

We also need a simple
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\right)$-bit data structure
to find the heavy leaf of a given heavy path in constant time [13, Lemma 15].

Next, we define three types of integer dictionaries that we are going to index
in $y$-fast tries to allow fast lookups. For every light node $v$, we define
the integer dictionary

$\mathop{}\mathopen{}\Gamma\mathopen{}\left(v\right):=\left\\{(\Psi^{\left|\mathop{}\mathopen{}\mathsf{pathlabel}\mathopen{}\left(v\right)\right|}[i],i):i\equiv
1\\!\\!\\!\pmod{\Delta}\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}i\in\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(v\right)\right\\}.$

Given a heavy leaf $\ell$ and its head $v$, we define the two integer
dictionaries

$\mathop{}\mathopen{}H_{\textup{L}}\mathopen{}\left(\ell\right):=\left\\{(\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[\mathop{}\mathopen{}\mathsf{leafrank}\mathopen{}\left(\ell\right)]},{\textsf{SA}[i]}\right),i):i\equiv
1\\!\\!\\!\pmod{\Delta}\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}i\in\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(v\right)\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}i\leq\mathop{}\mathopen{}\mathsf{leafrank}\mathopen{}\left(\ell\right)\right\\}$

and

$\mathop{}\mathopen{}H_{\textup{R}}\mathopen{}\left(\ell\right):=\left\\{(\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[\mathop{}\mathopen{}\mathsf{leafrank}\mathopen{}\left(\ell\right)]},{\textsf{SA}[i]}\right),i):i\equiv
1\\!\\!\\!\pmod{\Delta}\text{\leavevmode\nobreak\ and\leavevmode\nobreak\
}i\in\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(v\right)\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}i>\mathop{}\mathopen{}\mathsf{leafrank}\mathopen{}\left(\ell\right)\right\\}.$

We store $\mathop{}\mathopen{}\Gamma\mathopen{}\left(v\right)$ in a $y$-fast
trie for each light node $v$,
$\mathop{}\mathopen{}H_{\textup{L}}\mathopen{}\left(\ell\right)$ and
$\mathop{}\mathopen{}H_{\textup{R}}\mathopen{}\left(\ell\right)$ in a $y$-fast
trie for each heavy leaf $\ell$. Given an interval
$\mathcal{J}{}\subseteq[1..n]$, we can find

  * •

an $i\in\mathop{}\mathopen{}\Gamma\mathopen{}\left(v\right)$ with
$\mathsf{b}(\mathcal{J})\leq\mathop{}\mathopen{}\mathsf{key}\mathopen{}\left(i\right)=\Psi^{\left|\mathop{}\mathopen{}\mathsf{pathlabel}\mathopen{}\left(v\right)\right|}[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(i\right)]\leq\mathsf{e}(\mathcal{J})$,

  * •

an
$i_{\textup{l}}\in\mathop{}\mathopen{}H_{\textup{L}}\mathopen{}\left(\ell\right)$
with
$\mathsf{b}(\mathcal{J})\leq\mathop{}\mathopen{}\mathsf{key}\mathopen{}\left(i_{\textup{l}}\right)=\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[\mathop{}\mathopen{}\mathsf{leafrank}\mathopen{}\left(\ell\right)]},{\textsf{SA}[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(i_{\textup{l}}\right)]}\right)\leq\mathsf{e}(\mathcal{J})$,
and

  * •

an
$i_{\textup{r}}\in\mathop{}\mathopen{}H_{\textup{R}}\mathopen{}\left(\ell\right)$
with
$\mathsf{b}(\mathcal{J})\leq\mathop{}\mathopen{}\mathsf{key}\mathopen{}\left(i_{\textup{r}}\right)=\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[\mathop{}\mathopen{}\mathsf{leafrank}\mathopen{}\left(\ell\right)]},{\textsf{SA}[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(i_{\textup{r}}\right)]}\right)\leq\mathsf{e}(\mathcal{J})$,

all in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\cdot\lg\Delta\right)$
time.

######  Lemma 3.3.

We need
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\lg^{2}n/\Delta\right)$ bits
of space to store the $y$-fast tries for all
$\mathop{}\mathopen{}\Gamma\mathopen{}\left(\cdot\right)$,
$\mathop{}\mathopen{}H_{\textup{L}}\mathopen{}\left(\cdot\right)$, and
$\mathop{}\mathopen{}H_{\textup{R}}\mathopen{}\left(\cdot\right)$.

######  Proof 3.4.

Since the subtrees of the light nodes on the same level are disjoint, summing
over the sizes of $\mathop{}\mathopen{}\Gamma\mathopen{}\left(v\right)$ for
all light nodes $v$ on the same level yields at most $n/\Delta$ elements.
Since the heavy path decomposition has at most
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg n\right)$ different
levels and a $y$-fast trie uses
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg n\right)$ bits per stored
element, the claim for
$\left|\mathop{}\mathopen{}\Gamma\mathopen{}\left(v\right)\right|$ follows.

We analyze the size of
$\mathop{}\mathopen{}H_{\textup{L}}\mathopen{}\left(\cdot\right)$ by
identifying a leaf with its
$\mathop{}\mathopen{}\mathsf{leafrank}\mathopen{}$. The sampling of
$\mathop{}\mathopen{}H_{\textup{L}}\mathopen{}\left(\cdot\right)$ considers
only $n/\Delta$ leaves. A leaf $\ell$ has at most
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg n\right)$ light nodes as
ancestors. So there are at most
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg n\right)$ heavy leaves
$\ell_{\textup{H}}$ having
$\mathop{}\mathopen{}\mathsf{leafrank}\mathopen{}\left(\ell\right)$ as a value
in their dictionary
$\mathop{}\mathopen{}H_{\textup{L}}\mathopen{}\left(\ell_{\textup{H}}\right)$.
Hence, summing over
$\mathop{}\mathopen{}H_{\textup{L}}\mathopen{}\left(\ell_{\textup{H}}\right)$
for all heavy leaves $\ell_{\textup{H}}$ yields
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\lg n/\Delta\right)$
elements. The same considerations lead to the same size bounds for
$\mathop{}\mathopen{}H_{\textup{R}}\mathopen{}\left(\cdot\right)$.

######  Lemma 3.5.

Given the compressed suffix tree of $T$ and the dictionaries
$\mathop{}\mathopen{}\Gamma\mathopen{}\left(\cdot\right)$,
$\mathop{}\mathopen{}H_{\textup{L}}\mathopen{}\left(\cdot\right)$ and
$\mathop{}\mathopen{}H_{\textup{R}}\mathopen{}\left(\cdot\right)$ as defined
above, we can merge two suffix array intervals in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\Delta\right)$
time.

######  Proof 3.6.

Let $\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha\right)$ and
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\beta\right)$ be two suffix
array intervals and $P:=\alpha\beta$. Our task is to search the interval
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\right)\subseteq\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha\right)$
with
$\Psi^{\left|\alpha\right|}[i]\in\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\beta\right)$
for all $i\in\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\right)$. Since
$i\mapsto\Psi^{\left|\alpha\right|}[i]$ is monotonically increasing for
$i\in\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha\right)$, the merge
could be solved with two binary searches in
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha\right)$. To obtain the
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\Delta\right)$
time bound we will either use the $y$-fast tries, or perform a binary search
on $\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\Delta\right)$-large
intervals.

Let us take the node $v$ whose suffix array interval is
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha\right)$, i.e., the
lowest common ancestor of the leaves with
$\mathop{}\mathopen{}\mathsf{leafrank}\mathopen{}$
$\mathsf{b}(\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha\right))$
and
$\mathsf{e}(\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha\right))$.
We consider two cases:

Node $v$ is heavy.:

Let $H$ be the heavy path to which $v$ belongs, $\ell$ its heavy leaf, and $u$
its head.

If $\mathop{}\mathopen{}\Gamma\mathopen{}\left(u\right)$ is empty, there are
less than $\Delta$ leaves in the subtree rooted at $u$. Since
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\right)\subset\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(u\right)$,
we can find $\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\right)$ by
binary search in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\Delta\right)$.

Otherwise
($\mathop{}\mathopen{}\Gamma\mathopen{}\left(u\right)\not=\emptyset$), let
$q:=\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[\Psi^{\left|\alpha\right|}[{\mathop{}\mathopen{}\mathsf{leafrank}\mathopen{}\left(\ell\right)}]]},{\textsf{SA}[\mathsf{b}(\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\beta\right))]}\right)$.
The value $q$ is the length of the longest common prefix of $P$ and the path
label of $\ell$, subtracted by $\left|\alpha\right|$. By definition of $q$,
there is a node $r$ on $H$ whose path label coincides with
$\alpha\beta[1..q]$. In particular, this is the node on the path $H$ whose
path label is the longest prefix of $P$ with respect to the path labels of all
other nodes on $H$. Since
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\right)\subset\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(r\right)$,
our task is to find $r$ in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\Delta\right)$
time. To this end, we locate a leaf whose LCA with $\ell$ is $r$.

The interval boundaries can be found by a coarse search on the $y$-fast tries
of $\mathop{}\mathopen{}H_{\textup{L}}\mathopen{}\left(\ell\right)$ and
$\mathop{}\mathopen{}H_{\textup{R}}\mathopen{}\left(\ell\right)$, and a
subsequent refinement step using binary search. Let
$k:=\mathop{}\mathopen{}\mathsf{leafrank}\mathopen{}\left(\ell\right)$. Since
$i\mapsto\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[i]},{\textsf{SA}[k]}\right)$
is monotonically increasing for $i<k$, and monotonically decreasing for $i>k$,
we can perform the binary search for a value on the key-sorted integer
dictionaries
$\left\\{(\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[i]},{\textsf{SA}[k]}\right),i):i<k\right\\}$
and
$\left\\{(\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[i]},{\textsf{SA}[k]}\right),i):i>k\right\\}$
conceptionally. The $y$-fast tries at
$\mathop{}\mathopen{}H_{\textup{L}}\mathopen{}\left(\ell\right)$ and
$\mathop{}\mathopen{}H_{\textup{R}}\mathopen{}\left(\ell\right)$ help us
computing the tuple
$j_{\textup{l}}\in\mathop{}\mathopen{}H_{\textup{L}}\mathopen{}\left(\ell\right)\cup\left\\{(\left|\mathop{}\mathopen{}\mathsf{pathlabel}\mathopen{}\left(\ell\right)\right|,k)\right\\}$
with

$\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{l}}\right)-\Delta]},{\textsf{SA}[k]}\right)\leq\left|\alpha\right|+q\leq\mathop{}\mathopen{}\mathsf{key}\mathopen{}\left(j_{\textup{l}}\right)=\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{l}}\right)]},{\textsf{SA}[k]}\right)$

and the tuple
$j_{\textup{r}}\in\mathop{}\mathopen{}H_{\textup{R}}\mathopen{}\left(\ell\right)\cup\left\\{(\left|\mathop{}\mathopen{}\mathsf{pathlabel}\mathopen{}\left(\ell\right)\right|,k)\right\\}$
with

$\mathop{}\mathopen{}\mathsf{key}\mathopen{}\left(j_{\textup{r}}\right)=\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{r}}\right)]},{\textsf{SA}[k]}\right)\leq\left|\alpha\right|+q\leq\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{r}}\right)+\Delta]},{\textsf{SA}[k]}\right).$

Since
$\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{l}}\right)-\Delta]},{\textsf{SA}[k]}\right)\leq\left|\alpha\right|+q\leq\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{r}}\right)+\Delta]},{\textsf{SA}[k]}\right)$,
we can find one of the positions
$i_{\textup{l}}\in[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{l}}\right)-\Delta..\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{l}}\right)]$
and
$i_{\textup{r}}\in[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{r}}\right)..\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{r}}\right)+\Delta]$
by binary search such that
$\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[i_{\textup{l}}]},{\textsf{SA}[k]}\right)=\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}\left({\textsf{SA}[i_{\textup{r}}]},{\textsf{SA}[k]}\right)=\left|\alpha\right|+q$.
The binary search takes
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\Delta\right)$
time. On finding $i_{\textup{l}}$ or $i_{\textup{r}}$, we can retrieve $r$,
i.e., the lowest common ancestor of $\ell$ and the $i_{\textup{l}}$-th or
$i_{\textup{r}}$-th leaf. If the pattern $P$ is a prefix of the path label of
$r$, then
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\right)=\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(r\right)$,
and we are done. Otherwise, we choose the child $w$ of $r$ whose edge label
$S$ starts with $\beta[q+1]$; $w$ can be retrieved in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\Delta\right)$
time by Lemma 3.1. The child $w$ must be a light node, for otherwise we get a
contradiction to the definition of $r$. We set $v\leftarrow w$,
$\alpha\leftarrow P[1..\left|\alpha\right|+q+\left|S\right|]$,
$\beta\leftarrow P[\left|\alpha\right|+1..\left|P\right|]$, and jump to the
next case:

Node $v$ is light.:

If $\mathop{}\mathopen{}\Gamma\mathopen{}\left(v\right)$ is empty, then
$\left|\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(v\right)\right|<\Delta$.
Therefore, we can find the interval boundaries of
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\right)$ in
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(v\right)$ with a binary
search in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\Delta\right)$
time. Otherwise, we use the $y$-fast trie storing
$\mathop{}\mathopen{}\Gamma\mathopen{}\left(v\right)$ to find the tuple
$j_{\textup{l}}\in\mathop{}\mathopen{}\Gamma\mathopen{}\left(v\right)$ with
the smallest key satisfying
$\mathsf{b}(\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\beta\right))\leq\mathop{}\mathopen{}\mathsf{key}\mathopen{}\left(j_{\textup{l}}\right)=\Psi^{\left|\alpha\right|}[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{l}}\right)]$
and the tuple
$j_{\textup{r}}\in\mathop{}\mathopen{}\Gamma\mathopen{}\left(v\right)$ with
the largest key satisfying
$\mathop{}\mathopen{}\mathsf{key}\mathopen{}\left(j_{\textup{r}}\right)=\Psi^{\left|\alpha\right|}[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{r}}\right)]\leq\mathsf{e}(\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\beta\right))$.
If both exist, we can find the positions
$\mathsf{b}(\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\right))\in[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{l}}\right)-\Delta..\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{l}}\right)]$
and
$\mathsf{e}(\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\right))\in[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{r}}\right)..\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(j_{\textup{r}}\right)+\Delta]$
by two binary searches. If there is no tuple
$i\in\mathop{}\mathopen{}\Gamma\mathopen{}\left(v\right)$ with
$\mathsf{b}(\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\beta\right))\leq\mathop{}\mathopen{}\mathsf{key}\mathopen{}\left(i\right)\leq\mathsf{e}(\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\beta\right))$,
we search with the $y$-fast trie of
$\mathop{}\mathopen{}\Gamma\mathopen{}\left(v\right)$ the tuple
$k_{\textup{l}}\in\mathop{}\mathopen{}\Gamma\mathopen{}\left(v\right)$ with

$\mathop{}\mathopen{}\mathsf{key}\mathopen{}\left(k_{\textup{l}}\right)=\Psi^{\left|\alpha\right|}[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(k_{\textup{l}}\right)]\leq\mathsf{b}(\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\beta\right))\leq\Psi^{\left|\alpha\right|}[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(k_{\textup{l}}\right)+\Delta]$

and the tuple
$k_{\textup{r}}\in\mathop{}\mathopen{}\Gamma\mathopen{}\left(v\right)$ with

$\Psi^{\left|\alpha\right|}[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(k_{\textup{r}}\right)-\Delta]\leq\mathsf{e}(\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\beta\right))\leq\Psi^{\left|\alpha\right|}[\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(k_{\textup{r}}\right)]=\mathop{}\mathopen{}\mathsf{key}\mathopen{}\left(k_{\textup{r}}\right).$

Both values exist, and
$\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(k_{\textup{r}}\right)-\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(k_{\textup{l}}\right)\leq\Delta$.
So we find the interval
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\right)$ by applying two
binary searches to the range
$\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(k_{\textup{l}}\right)..\mathop{}\mathopen{}\mathsf{val}\mathopen{}\left(k_{\textup{r}}\right)$.

Setting $\Delta:=\lg^{c}n$ for $c\geq 2$ yields:

######  Lemma 3.7.

Given the compressed suffix tree of $T$, there is a data structure of size
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\right)$ bits that allows us
to merge two suffix array intervals in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\lg
n\right)$ time.

##  4\. Parallel Exact Pattern Matching

We parallelize the merging of suffix array intervals that we presented in
Section 3 and show that queries in the suffix tree using consecutive
subpatterns and linear space can be solved in parallel on a CREW-PRAM. For
this, we use parallel binary search:

######  Lemma 4.1 ([21, Theorem 2.1]).

Given a sorted array of size $n$, a binary search requires
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(1+\lg_{p}n\right)$ time when
operating on a CREW-PRAM with $p$ processors.

We conclude that we can parallelize the query on $y$-fast tries in the same
way:

######  Lemma 4.2.

A $y$-fast trie can do lookups, predecessor and successor queries in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(1+\lg_{p}\lg n\right)$ time
using $p$ processors.

######  Proof 4.3.

We can find an element in an $x$-fast trie in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(1+\lg_{p}\lg n\right)$ time
using parallel binary search (Lemma 4.1) on the
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg n\right)$ hash tables.
The sorted arrays stored at the leaves can similarly be searched in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(1+\lg_{p}\lg n\right)$ time,
again using Lemma 4.1.

Let us focus on the merging of two suffix array intervals as treated in
Section 3. The dominant term of its running time is due to the query time of
the $y$-fast tries and the binary searches. As we can parallelize both, a
parallelization of the merging algorithm improves the time bounds
significantly:

######  Lemma 4.4.

Given $p$ processors and two suffix array intervals
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha\right)$ and
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\beta\right)$, the merged
interval $\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha\beta\right)$
can be computed in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}(1+\lg_{p}\lg
n)\right)$ time
and$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\min\left(p,\lg
n\right)(1+\lg_{p}\lg n)\right)$ work.

######  Proof 4.5.

We can merge two suffix array intervals in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\lg
n\right)$ time using Lemma 3.7. Recalling the proof of Lemma 3.5, we took the
node $v$ whose suffix array interval is
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha\right)$. There, in
both cases ($v$ is either heavy or light), the time is dominated by searching
in $y$-fast tries, and/or by binary searching in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\Delta\right)$ sampled
$\Psi$\- or $\mathop{}\mathopen{}\mathsf{lcp}\mathopen{}$-values. Both can be
parallelized by Lemmas 4.1 and 4.2, respectively. This yields
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}(1+\lg_{p}\lg
n)\right)$ time using $p$ processors. During the parallel searches, we use at
most $\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg n\right)$ processors
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(1+\lg_{p}\lg n\right)$ times.
This amounts to
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\min\left(p,\lg
n\right)(1+\lg_{p}\lg n)\right)$ work.

Being able to merge two suffix array intervals in parallel, we now show how to
compute the suffix array interval of a pattern $P$ in parallel. To this end,
we decompose the pattern in subpatterns $\alpha_{1},\dots,\alpha_{p}$ such
that $P=\alpha_{1}\alpha_{2}\dots\alpha_{p}$, and then compute the suffix
array intervals for the subpatterns. Then we merge those intervals in
parallel.

######  Theorem 4.6.

Given a text of size $n$ and a pattern of size $m$. With $p\leq m$ processors,
we can compute the suffix array interval of the pattern in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\left(\frac{m}{p}+\lg
p+\lg\lg p\cdot\lg\lg n\right)\right)$ time and
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\left(m+\min\left(p,\lg
n\right)\left(\lg p+\lg\lg p\cdot\lg\lg n\right)\right)\right)$ work. In order
to achieve this time bound we need an index of size
$\left|\textup{CSA}\right|+\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\right)$
bits.

######  Proof 4.7.

Let $P=\alpha^{0}_{1}\alpha^{0}_{2}\dots\alpha^{0}_{p}$ be a pattern of length
$m$ such that $|\alpha^{0}_{i}|=\Theta{\left(\frac{m}{p}\right)}$ for
$i=1,\dots,p$. The computation of all intervals
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha^{0}_{i}\right)$
requires
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\frac{m}{p}\right)$
time. In the first merge step we have two processors to compute each of the
intervals
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha^{1}_{i}\right):=\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha^{0}_{2i-1}\alpha^{0}_{2i}\right)$
for $i=1,\dots,\frac{p}{2}$. In each merge step we halve the number of
intervals. So in the $k$-th merge step ($1\leq k\leq\lg p$), we have $2^{k}$
processors to compute each of the intervals
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha^{k}_{i}\right):=\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha^{k-1}_{2i-1}\alpha^{k-1}_{2i}\right)$
for $i=1,\dots,\frac{p}{2^{k}}$. As we require
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg p\right)$ merge steps and
can use Lemma 4.4 with $2^{k}$ processors in the $k$-th merge step, the
interval $\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\right)$ can be
computed in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\sum_{k=1}^{\lg
p}\left(1+\lg_{2^{k}}\lg
n\right)\right)=\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\left(\lg
p+\lg\lg p\cdot\lg\lg n\right)\right)$ time, given the intervals
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\alpha^{0}_{i}\right)$ of the
subpatterns – see Figure 2. In total,
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\right)$ can be found in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\left(\frac{m}{p}+\lg
p+\lg\lg p\cdot\lg\lg n\right)\right)$ time.

During the computation of the suffix array intervals of the subpatterns of $P$
we use all $p$ processors, which results in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}m\right)$
work. The same holds for each merging step, as we use all processors to
parallelize the binary search. We have
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\lg p\right)$ merge steps.
During the $k$-th merge step, we merge $\frac{p}{2^{k}}$ suffix array
intervals with $2^{k}$ processors each. Using Lemma 4.4 the total work is
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\left(m+\min\left(p,\lg
n\right)\left(\lg p+\lg\lg p\cdot\lg\lg n\right)\right)\right)$.

Figure 2. Schedule for the merging of $p$ suffix array intervals, i.e., the
suffix array intervals of the subpatterns. The number in each node denotes the
number of processors available for the merging of the two considered suffix
array intervals.

##  5\. Parallel Approximate Pattern Matching

In this section, we consider two different distances for the approximate
string matching problem. The first distance we consider is the _Levenshtein
distance_ , where the distance between two patterns $P$ and $P^{\prime}$ is
the minimal number of the operations _insert_ , _change_ and _remove_ required
to change $P^{\prime}$ into $P$. The second one is the _Hamming distance_ ,
where the distance of two pattern $P$ and $P^{\prime}$ of equal length is the
number of mismatching positions, i.e., $|\\{i\colon P[i]\neq
P^{\prime}[i],1\leq i\leq\left|P\right|\\}|$. We consider two problems related
to these distances.

$k$-difference problem:

Given a text $T$ of length $n$ and a pattern $P$ of length $m$, we want to
report all occurrences $i\in\left\\{1,\dots,n\right\\}$ such that $T[i..i+j]$
and $P$ have a Levenshtein distance of at most $k$ for at least one
$j\in\left\\{0,\dots,n-i\right\\}$.

$k$-mismatch problem:

Given a text $T$ of length $n$ and a pattern $P$ of length $m$, we want to
report all occurrences $i\in\left\\{1,\dots,n-m\right\\}$ such that
$T[i..i+m]$ and $P$ have a Hamming distance of at most $k$.

We apply the results from Section 3 to parallelize the approximate string
matching algorithm by Huynh et al. [10]. To do so, we first present an
approach to compute the suffix array intervals of all prefixes and suffixes of
the pattern in parallel – see Figure 3.

######  Lemma 5.1.

Given a text of length $n$ and its suffix array, we can compute the suffix
array intervals of all prefixes and suffixes of a pattern of length $m$ in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}(1+\frac{m}{p})\lg
p\cdot\lg\lg n\right)$ parallel time operating on a CREW-PRAM with $p$
processors.

######  Proof 5.2.

Let $P=\alpha_{0}\alpha_{1}\dots\alpha_{p-1}$ be a pattern of length $m$ such
that $|\alpha_{i}|=\frac{m}{p}$ for $i=0,\dots,p-1$. Thus, the $j$-th prefix
of a subpattern $\alpha_{i}$ is $P[1+i\frac{m}{p}..i\frac{m}{p}+j]$ for all
$i=0,\dots,p-1$ and $j=1,\dots,\frac{m}{p}$. First, we compute the suffix
array intervals for all those prefixes in parallel, which requires
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(1+m/p\right)$ time, as no
merging is necessary during this step.

In the second step, we merge the suffix array intervals in parallel. Since we
want the suffix array intervals of all prefixes of the pattern, during the
first merge step we merge the suffix array intervals
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P[1+2i\frac{m}{p}..(2i+1)\frac{m}{p}]\right)$
as the left side interval with each of the intervals
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P[1+(2i+1)\frac{m}{p}..(2i+1)\frac{m}{p}+j\right)$
as right side interval for all $i=0,\dots,\frac{p}{2}-1$ and
$j=1,\dots,\frac{m}{p}$. This results in the intervals
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P[1+2i\frac{m}{p}..(2i+1)\frac{m}{p}+j\right)$
for $i=0,\dots,\frac{p}{2}-1$ and $j=1,\dots,\frac{m}{p}$. During each merge
step, we halve the number of left side intervals that we have to consider
during the next merge step but double the number of right side intervals that
are merged, i.e., in the $k$-th merge step, we merge the intervals
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P[1+2^{k}i\frac{m}{p}..(2^{k}i+2^{k-1})\frac{m}{p}]\right)$
with each of the intervals
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P[1+(2^{k}i+2^{k-1})\frac{m}{p}..(2^{k}i+2^{k-1})\frac{m}{p}+j]\right)$
for $i=0,\dots,\frac{p}{2^{k}}-1$ and $j=1,\dots,2^{k-1}\frac{m}{p}$. This
amounts to $\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(m\right)$
intervals that need to be merged in each step. In the end, we obtain the
suffix array intervals of the prefixes of $P$, i.e., the intervals
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\left[1..j\right]\right)$
for $j=1,\dots,m$. Since we start with $p$ left side intervals, and each merge
step halves the number of left side intervals, we end up with $\lg p$ merge
steps.

The computation of the suffix array intervals of all suffixes of $P$ works
analogously. Using Lemma 3.7, we can compute the suffix array intervals of all
prefixes and suffixes of the pattern in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}(1+\frac{m}{p})\lg
p\cdot\lg\lg n\right)$ time.

Figure 3. Schematics of the merging process to compute the suffix array
intervals of all prefixes of a pattern $P=a_{1}\dots a_{4}$ of length $m=12$
using $p=4$ processors. The gray blocks above the first dashed line represent
the suffix array intervals of all prefixes of the subpatterns $a_{i}$ (for
$i=1,\dots,4$). The blocks between the dashed lines represent the suffix array
intervals after the first merge step. The intervals that are merged are shown
by arrows. The blocks below the second dashed line are the suffix array
intervals computed in the second merge step.

operation $c$ $P^{\prime}$ intervals to merge substitution
$c\in\Sigma\setminus\left\\{P[i]\right\\}$ $P[1..i-1]cP[i+1..m]$
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\mathop{}\mathopen{}\mathsf{child}\mathopen{}\left(v,c\right)\right)$
and
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\left[i+1..m\right]\right)$
deletion $-$ $P[1..i-1]P[i+1..m]$
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(v\right)$ and
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\left[i+1..m\right]\right)$
insertion $c\in\Sigma$ $P[1..i-1]cP[i..m]$
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(\mathop{}\mathopen{}\mathsf{child}\mathopen{}\left(v,c\right)\right)$
and
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\left[i..m\right]\right)$

Figure 4. Let $P^{\prime}$ be the resulting string of introducing an error in
the pattern $P[1..m]$ at position $i$. Further, let $v$ be the suffix tree
node with
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(v\right)={\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\left[1..i-1\right]\right)}$.
We can compute the two suffix array intervals considered for merging in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\lg
n\right)$ time, and perform the merging in the same time.

######  Theorem 5.3.

With
$\left|\textup{CSA}\right|+\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\right)$
bits of space, the $1$-difference and $1$-mismatch problems can be solved in
parallel in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\lg
n\left(\frac{m\sigma}{p}+(1+\frac{m}{p})\lg p\right)+\text{occ}\right)$ for
$p\leq m\sigma$.

######  Proof 5.4.

We precompute the suffix array intervals
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\left[i..m\right]\right)$
and
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\left[1..i\right]\right)$
for all $1\leq i\leq m$ in parallel by Lemma 5.1. This requires
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}(1+\frac{m}{p})\lg
p\cdot\lg\lg n\right)$ time. The exact matches are found in the interval
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\left[1..m\right]\right)$.
To compute the matches with one error, we iterate over all positions in
$P[1..m]$, and introduce an error at one position $i$ with $1\leq i\leq m$. An
error can be introduced by an insertion, a deletion, or a substitution. Let us
fix one modification occurring at position $i$, and call the modified string
$P^{\prime}$. Our task is to find
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P^{\prime}\right)$. To this
end, we exploit some already computed results, i.e., we have
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P^{\prime}\left[1..i-1\right]\right)=\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\left[1..i-1\right]\right)$,
and either (substitution)
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P^{\prime}\left[i+1..m\right]\right)=\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\left[i+1..m\right]\right)$,
(deletion)
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P^{\prime}\left[i..m-1\right]\right)=\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\left[i+1..m\right]\right)$,
or (insertion)
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P^{\prime}\left[i+1..m+1\right]\right)=\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P\left[i..m\right]\right)$
– see Figure 4. If $P^{\prime}$ resulted from an insertion or substitution,
the interval
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P^{\prime}\left[1..i-1\right]\right)$
can be enhanced to
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P^{\prime}\left[1..i\right]\right)$
by
$\mathop{}\mathopen{}\mathsf{child}\mathopen{}\left(v,P^{\prime}\left[i\right]\right)$
in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\lg
n\right)$ time due to Lemma 3.1, where $v$ is the node with
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(v\right)=\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P^{\prime}\left[1..i-1\right]\right)$.
Finally, we can compute
$\mathop{}\mathopen{}\mathcal{I}\mathopen{}\left(P^{\prime}\right)$ by merging
two intervals in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\lg\lg
n\right)$ time with Lemma 3.7. Introducing an error in $P$ at $m$ different
positions with $\sigma$ different characters is embarrassingly parallel. With
$p\leq m\sigma$ processors it requires
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\frac{m\sigma}{p}\lg\lg
n+\text{occ}\right)$ time in addition to the time for the preprocessing.

Up to now, we have assumed that the time for the output is in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\text{occ}\right)$.
Unfortunately, this is not always the case, as an occurrence of a pattern with
$k$ errors may be reported multiple times. For example, if we allow one error,
the pattern aba could be reported twice at the first position of the text aaa,
as the second position of the pattern could either be deleted or replaced.
Hence, we need to make sure that each occurrence of a pattern is reported just
once, regardless how many different combinations of operations can be used to
change the pattern to the corresponding substring. This problem has been
discussed and solved in [10].

######  Lemma 5.5 ([10, Discussion related to Theorem 2]).

Given a pattern $P$, we can check whether an occurrence of the pattern
$P^{\prime}$ with at most $k$ errors is minimal regarding its distance and its
edit operations to $P$ in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(k\right)$ time whenever we
append a character or want to report an occurrence.

Using Lemmas 5.1 and 5.5, we can solve the $1$-difference and $1$-mismatch
problems in parallel as described above. The same is true for the
$k$-difference and $k$-mismatch problems.

######  Theorem 5.6.

Using
$\left|\textup{CSA}\right|+\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\right)$
bits of space, the $k$-difference and $k$-mismatch problems can be solved in
parallel in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\left(\frac{m^{k}\sigma^{k}}{p}\max\left(k,\lg\lg
n\right)+(1+\frac{m}{p})\lg p\cdot\lg\lg n\right)+\text{occ}\right)$ for
$p\leq m^{k}\sigma^{k}$ processors.

######  Proof 5.7.

The idea of the algorithm is similar to the algorithm of Theorem 5.3. First,
we compute the suffix array intervals of all the suffixes and prefixes of the
pattern using Lemma 5.1. This requires
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}(1+\frac{m}{p})\lg
p\cdot\lg\lg n\right)$ time. We want to introduce at most $k$ errors in
parallel. Again, we parallelize over the positions of the introduced errors.
Similar to the idea of Theorem 5.3, we merge different suffix array intervals.
But in this case, we cannot parallelize over one position, instead we have to
parallelize considering up to $k$ positions where we can include an error.

The number of patterns $P^{\prime}$ that have a distance of at most $k$ from
$P$ is bounded by
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\sigma^{k}m^{k}\right)$ [22,
Theorem 6]. Thus, we require
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(t_{\textsf{SA}}\frac{m^{k}\sigma^{k}}{p}\max\left(k,\lg\lg
n\right)+\text{occ}\right)$ time using $p\leq\sigma^{k}m^{k}$ processors in
parallel. The
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\max\left(k,\lg\lg
n\right)\right)$-term results from the check of whether the occurrence is
computed with minimal distance to the pattern $P$, which has to be done every
time we update the considered pattern and requires
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(k\right)$ time using Lemma
5.5.

#### Acknowledgment

We thank Anders Roy Christiansen, who found an error in a previous version of
this paper.

## References

  * [1] D. Belazzougui and G. Navarro.  Alphabet-independent compressed text indexing.  ACM Transactions on Algorithms (TALG), 10(4):article 23, 2014.
  * [2] Dany Breslauer and Zvi Galil.  An optimal O(log log n) time parallel string matching algorithm.  SIAM J. Comput., 19(6):1051–1058, 1990.
  * [3] Dany Breslauer and Zvi Galil.  A lower bound for parallel string matching.  SIAM J. Comput., 21(5):856–862, 1992.
  * [4] Martin Farach and S. Muthukrishnan.  Optimal logarithmic time randomized suffix tree construction.  In Proc. ICALP, volume 1099 of LNCS, pages 550–561. Springer, 1996.
  * [5] Johannes Fischer.  Wee LCP.  Inform. Process. Lett., 110(8–9):317–320, 2010.
  * [6] Johannes Fischer.  Combined data structure for previous- and next-smaller-values.  Theor. Comput. Sci., 412(22):2451–2456, 2011.
  * [7] Johannes Fischer, Veli Mäkinen, and Gonzalo Navarro.  Faster entropy-bounded compressed suffix trees.  Theor. Comput. Sci., 410(51):5354–5364, 2009.
  * [8] Michael L. Fredman, János Komlós, and Endre Szemerédi.  Storing a sparse table with ${O}(1)$ worst case access time.  J. ACM, 31(3):538–544, 1984.
  * [9] Simon Gog and Johannes Fischer.  Advantages of shared data structures for sequences of balanced parentheses.  In Proc. DCC, pages 406–415. IEEE Press, 2010.
  * [10] Trinh ND Huynh, Wing-Kai Hon, Tak-Wah Lam, and Wing-Kin Sung.  Approximate string matching using compressed suffix arrays.  Theoretical Computer Science, 352(1):240–249, 2006.
  * [11] Matevz Jekovec and Andrej Brodnik.  Parallel query in the suffix tree.  CoRR, abs/1509.06167, 2015.
  * [12] Juha Kärkkäinen, Dominik Kempa, and Simon J. Puglisi.  Parallel external memory suffix sorting.  In Proc. CPM, volume 9133 of LNCS, pages 329–342. Springer, 2015.
  * [13] Tak-Wah Lam, Wing-Kin Sung, and Swee-Seong Wong.  Improved Approximate String Matching Using Compressed Suffix Data Structures.  Algorithmica, 51(3):298–314, 2007.
  * [14] Udi Manber and Eugene W. Myers.  Suffix arrays: A new method for on-line string searches.  SIAM J. Comput., 22(5):935–948, 1993.
  * [15] J. Ian Munro, Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao.  Succinct representations of permutations and functions.  Theor. Comput. Sci., 438:74–88, 2012.
  * [16] Gonzalo Navarro and Veli Mäkinen.  Compressed full-text indexes.  ACM Comput. Surv., 39(1):Article No. 2, 2007.
  * [17] Enno Ohlebusch, Johannes Fischer, and Simon Gog.  CST++.  In Proc. SPIRE, volume 6393 of LNCS, pages 322–333. Springer, 2010.
  * [18] Milan Ružić.  Constructing efficient dictionaries in close to sorting time.  In Proc. ICALP (1), volume 5125 of LNCS, pages 84–95. Springer, 2008.
  * [19] Kunihiko Sadakane.  Compressed suffix trees with full functionality.  Theory Comput. Syst, 41(4):589–607, 2007.
  * [20] Kunihiko Sadakane and Gonzalo Navarro.  Fully-functional succinct trees.  In Proc. SODA, pages 134–149. ACM/SIAM, 2010.
  * [21] Marc Snir.  On parallel searching.  SIAM J. Comput., 14(3):688–708, 1985.
  * [22] Esko Ukkonen.  Approximate string-matching over suffix trees.  In Proc. CPM, volume 684 of LNCS, pages 228–242. Springer, 1993.
  * [23] Dan E. Willard.  Log-logarithmic worst-case range queries are possible in space ${\Theta}(n)$.  Inform. Process. Lett., 17(2):81–84, 1983.