Relative Compressed Reverse Suffix Array

Kulekci, Muhammed Oguzhan; Parthasarathi, Mano Prakash; Shah, Rahul; Thankachan, Sharma V.

doi:10.4230/LIPIcs.STACS.2026.62

Relative Compressed Reverse Suffix Array

Muhammed Oguzhan Kulekci

Miami University, Oxford, OH, USA Mano Prakash Parthasarathi¹¹1Corresponding author

North Carolina State University, Raleigh, NC, USA Rahul Shah

Louisiana State University, Baton Rouge, LA, USA Sharma V. Thankachan

North Carolina State University, Raleigh, NC, USA

Abstract

Suffix trees and suffix arrays are two fundamental data structures in the field of string algorithms. For a string (a.k.a. text or sequence) of length $n$ over an alphabet of size $\sigma$ , these structures typically require $O(n\log n)$ bits of space. The FM-index provides a compressed representation of the suffix array in $\approx n\log\sigma$ bits, allowing for efficient queries on both the suffix array and its inverse array in near logarithmic time. In certain applications, such as approximate pattern matching (i.e., with wildcards, mismatches, edits), there is a need to access the suffix array of a text, as well as the suffix array of text’s reverse. Motivated by this, we explore the possibility of encoding the suffix array of the reversed text in a compact form, assuming the availability of the FM-index for the original text. Our first solution is an $O(n)$ -bit (relative) encoding of the suffix array of the reversed text, with the time for decoding an entry being only $O(\log^{*}n)$ times that of decoding an entry in the text’s suffix array using FM-index. We then demonstrate how to reduce the space to $O(n/\kappa)$ bits for a parameter $\kappa$ , while multiplicative factor in time becomes approximately $O(\kappa\log^{*}n+\kappa^{3})$ . We can also support inverse suffix array and longest common extension queries on the reversed text. These results are achieved through some careful and non-trivial application of various succinct data structure techniques.

Keywords and phrases:

String Matching, Text Indexing, Data Structures, Suffix Trees

Funding:

Mano Prakash Parthasarathi: U.S. National Science Foundation (NSF) award CCF-2315822.

Rahul Shah: U.S. NSF awards CCF-2434261 and CCF-2137057

Sharma V. Thankachan: U.S. NSF awards CCF-2316691 and CCF-2315822.

Copyright and License:

© Muhammed Oguzhan Kulekci, Mano Prakash Parthasarathi, Rahul Shah, and
Sharma V. Thankachan; licensed under Creative Commons License CC-BY 4.0

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Pattern matching

DOI:

10.4230/LIPIcs.STACS.2026.62

Event:

43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Editors:

Meena Mahajan, Florin Manea, Annabelle McIver, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The suffix tree data structure [22, 33, 34] has long been a fundamental tool in string processing, enabling tasks such as pattern matching in time linear in the pattern length. However, their use has been limited in practice due to their high memory usage. Suffix arrays [21] were introduced as a more memory-efficient alternative that can perform most of the tasks as suffix trees. Both suffix trees and suffix arrays of a text of length $n$ still require $O(n\log n)$ bits to store, while the text itself only needs $n\log\sigma$ bits, where $\sigma$ is the alphabet size. The major breakthrough came in 2000 with the FM-index [7], along with another important development called the compressed suffix array [14]; both of these encode the suffix array in succinct (even compressed) space. Since then, compressed text indexing has continued to be an active area of research, with the FM-index emerging as a foundational component in many bioinformatics tools [18, 20].

In its standard form, the FM-index is essentially the Burrows-Wheeler Transform (BWT) of the text, stored in a data structure that supports rank queries (typically using a wavelet tree [13, 24]), along with a sampled subset of suffix array values. The wavelet tree part uses $n\log\sigma+o(n)+O(\sigma\log n)$ bits, and supports rank queries in time $t_{wt}=O(1+\log\sigma/\log\log n)$ . For a parameter $\tau$ , the number of sampled suffix array values is $n/\tau$ and its storage takes $O((n/\tau)\log n)$ bits. To keep this extra space within $o(n)$ bits, $\tau$ is typically chosen as $\omega(\log n)$ . With this, the suffix array (SA) and inverse suffix array (ISA) queries can be supported in time $t_{sa}=O(\tau\cdot t_{wt})$ . With additional $o(n)$ bits, we can obtain an encoding of the suffix tree itself that supports various queries in time close to $O(t_{sa})$ [31, 30]. Recent results have revealed the possibility of achieving even more space-efficient encodings of suffix arrays/trees when the data is highly repetitive [10, 16, 26, 27].

We investigate the problem of compactly encoding the suffix array of the reverse of a text, assuming access to the text’s FM-index in its standard form (i.e., the Burrows–Wheeler Transform represented as a wavelet tree together with a sampled suffix array). While this is a natural question in its own right, solutions to it have important applications in text indexing for approximate string matching. A common technique for supporting pattern matching with mismatches or “don’t care” characters involves maintaining both the suffix array or tree of the text and that of its reverse, along with a range query data structure built from specific points derived from these structures [2]. For a comprehensive survey of various results based on this technique, we refer the reader to Lewenstein [19]. See also the solutions for contextual pattern matching [1, 25], bidirectional indexes [17], and affix arrays [32] for further applications. Reducing the memory footprint of the data structures associated with the reversed text can significantly reduce the overall space usage in such applications. We highlight that our problem aligns with the broader theme of relative text indexing, such as relative suffix trees [6] and relative FM-indexes [3], where the goal is to encode a data structure over a dataset by leveraging the availability of the same structure over a closely related dataset. The fact that, in our case, one text is essentially the reverse of the other introduces significant structure to the problem.

This problem was introduced by Ganguly et al. [12], who presented an algorithm to decode the suffix array values of the reversed text directly from the text’s FM-index, without requiring any additional data structures. However, it was heuristic in nature. Specifically, its query time is proportional to the length of the shortest unique substring of the text ending at the value returned, which can be $\Theta(n)$ in the worst case. Therefore, our goal is to support suffix array (and inverse suffix array) queries on the reversed text in time close to that of suffix array queries on the original text. We present our results next.

Our Results

Let $\mathsf{T}[1\mathinner{.\,.\allowbreak}n]$ denote the text to be indexed, where the characters belong to an integer alphabet of size $\sigma$ . We can represent the text’s Burrows–Wheeler Transform (BWT) as a (multiary) wavelet tree in $n\log\sigma+o(n)+O(\sigma\log n)$ bits of space, supporting basic wavelet tree operations (rank, select, access) in time $t_{wt}=O(1+\log\sigma/\log\log n)$ and range quantile queries in time $t_{quantile}=O(\log\sigma)$ . By maintaining some auxiliary structures of space $O(n/\kappa)$ bits for an integer parameter $\kappa\geq 1$ , we can support suffix array (SA) and inverse suffix array (ISA) queries in time $t_{sa}=O(t_{wt}\cdot\kappa\log n)$ . We obtain the following results.

1.

Our first result is that suffix array queries on the reversed text can be supported in time $t_{pa}=t_{sa}\cdot O(\log^{*}n)$ with an auxiliary structure of $O(n)$ bits of space.
2.

We then generalize the above result by introducing a parameter $\kappa$ , achieving a space usage of $O(n/\kappa)$ bits and a query time $t_{pa}=t_{sa}\cdot O((\kappa\log^{*}n+\kappa^{3}\log\kappa)\cdot\log^{2}\kappa)$ .

We also show how to support inverse suffix array queries on the reversed text within the same space and in time $O(t_{pa}\cdot\log n\cdot\log\log n)$ , which is based on a simple method for answering longest common extension queries on the reversed text. As shown in [31, 30], we can use $o(n)$ extra bits to obtain a succinct encoding of the suffix tree of the reversed text that supports various standard operations efficiently.

2 Notation and Preliminary

Throughout this paper, let $\mathsf{T}=\mathsf{T}[1\mathinner{.\,.\allowbreak}n]$ denotes the text to be indexed and $\Sigma$ denotes the alphabet set. The $i$ -th character of $\mathsf{T}$ is denoted by $\mathsf{T}[i]$ and the substring $\mathsf{T}[i]\circ\mathsf{T}[i+1]\circ\dots\circ\mathsf{T}[j-1]\circ\mathsf{T}% [j]$ is denoted by $\mathsf{T}[i\mathinner{.\,.\allowbreak}j]$ , where $1\leq i\leq j\leq n$ and $\circ$ denotes concatenation. The string $\mathsf{T}[i\mathinner{.\,.\allowbreak}j]$ is empty if $i>j$ . We also use $\mathsf{T}[i\mathinner{.\,.\allowbreak}j)$ for $\mathsf{T}[i\mathinner{.\,.\allowbreak}j-1]$ and $\mathsf{T}(i\mathinner{.\,.\allowbreak}j]$ for $\mathsf{T}[i+1\mathinner{.\,.\allowbreak}j]$ . A substring $\mathsf{T}[i\mathinner{.\,.\allowbreak}j]$ is called a suffix if $j=n$ and a prefix if $i=1$ ; also $\mathsf{T}[1\mathinner{.\,.\allowbreak}j]$ is a proper prefix if $j\neq n$ and $\mathsf{T}[i\mathinner{.\,.\allowbreak}n]$ is a proper suffix if $i\neq 1$ . For any string $S=S[1\mathinner{.\,.\allowbreak}s]$ , we denote its reverse $S[s]\circ S[s-1]\circ\dots\circ S[2]\circ S[1]$ by $\overleftarrow{S}$ . Without loss of generality, assume that the characters in our alphabet set $\Sigma$ corresponds to integers in the range $[0,\sigma)$ , where $\sigma=|\Sigma|$ . Also, let $\$$ denote the first character in lexicographic order (equivalently, $0$ ) and $\mathsf{T}[i]=\$$ iff $i=n$ , ensuring that no suffix is a prefix of another suffix.

We call a data structure auxiliary if it is used to support operations assuming some related structures are available; otherwise, it is considered standalone. We assume the standard word RAM model of computation with word size $\Omega(\log n)$ bits.

2.1 Succinct Data Structure Toolkit

2.1.1 Rank/select Queries, Indexible Dictionaries and Wavelet Trees

Let $S[1\mathinner{.\,.\allowbreak}n]\in\Sigma^{n}$ , where $\Sigma=\{0,1,2,\dots,\sigma-1\}$ . We define three basic operations.

$\blacksquare$

$\mathsf{access}_{S}(i)$ is $S[i]$ .
$\blacksquare$

$\mathsf{rank}_{S}(i,\alpha)$ , where $\alpha\in\Sigma$ , is the number of $\alpha$ ’s in $S[1\mathinner{.\,.\allowbreak}i]$ .
$\blacksquare$

$\mathsf{select}_{S}(j,\alpha)$ is the position of $j$ -th occurrence of $\alpha$ in $S$ .

When $\Sigma=\{0,1\}$ , we can maintain $S$ in $n+o(n)$ bits and support all three operations in $O(1)$ time [28]. Another representation, called indexible dictionary takes $m\log(n/m)+O(m)$ bits, where $m$ is the number of $1$ ’s in $S$ [29]. It supports the above operations in $O(\log\log n)$ time. Interestingly, it can support $\mathsf{select}_{S}(j,1)$ in $O(1)$ time, and also $\mathsf{rank}_{S}(i,1)$ when $S[i]=1$ (referred to as partial rank) in $O(1)$ time. We will use this result extensively.

For a general alphabet $\Sigma$ , we have the wavelet tree data structure that uses $n\log\sigma+o(n)+O(\sigma\log n)$ bits of space and supports all three basic operations in $O(\log\sigma)$ time [13]. It can also support range quantile queries in $O(\log\sigma)$ time [11], where the goal is to find the $k$ -th smallest element in $S[x\mathinner{.\,.\allowbreak}y]$ , given the tuple $(x,y,k)$ . Multiary wavelet trees offer further improvements, reducing the time complexity of the three basic operations to $O(1+\log\sigma/\log\log n)$ [8]; however, the time for range quantile queries remains $O(\log\sigma)$ . Also note that the $o(n)$ term in space can be made $O(n/\log^{c}n)$ for any constant $c$ using efficient bit string representations [28]. We refer to Navarro’s survey for further reading on this topic [24]. Moving forward, we use $t_{wt}$ to denote the time complexity of the basic operations, and $t_{quantile}$ to represent the time complexity of a range quantile query.

2.1.2 Range Minimum Query (RMQ)

Let $A[1\mathinner{.\,.\allowbreak}n]$ be an array of numbers. A range minimum query $\operatorname{RMQ}_{A}(x,y)$ returns the position $k\in[x,y]$ , where $A[k]$ is the smallest element in $A[x\mathinner{.\,.\allowbreak}y]$ . By maintaining a standalone data structure of space $2n+o(n)$ bits, we can support RMQ in $O(1)$ time [9].

2.1.3 Succinct Representation of Ordinal Trees

The topology of an ordinal tree of $n$ nodes can be represented in $2n+o(n)$ bits and support the following operations in $O(1)$ time [15, 23]. We specify a node by its preorder rank.

$\blacksquare$

$\mathsf{parent}(u)$ returns the parent of node $u$ .
$\blacksquare$

$\operatorname{LCA}(u,v)$ returns the lowest (farthest from the root) common ancestor of nodes $u$ and $v$ .
$\blacksquare$

$\mathsf{size}(u)$ returns the number of leaves in the subtree of node $u$ .
$\blacksquare$

$0pt(u)$ returns the number of ancestors of node $u$ .
$\blacksquare$

$\mathsf{level\_ancestor}(u,d)$ returns the ancestor of node $u$ at $0pt$ $d$ .
$\blacksquare$

range of leaves $[a,b]$ of any given node $u$ , where $a$ -th (resp., $b$ -th) leaf in the tree represents the leftmost (resp., rightmost) leaf in the subtree of $u$ .

2.2 Suffix Tree, Suffix Array and Longest Common Prefix (LCP) Array

The suffix of $\mathsf{T}$ starting at position $i$ is $\mathsf{T}[i\mathinner{.\,.\allowbreak}n]$ . The circular suffix of $\mathsf{T}$ , starting at position $i$ is $\mathsf{T}[i\mathinner{.\,.\allowbreak}n]\circ\mathsf{T}[1\mathinner{.\,.% \allowbreak}i)=\mathsf{T}[i]\circ\mathsf{T}[i+1]\circ\dots\circ\mathsf{T}[n]% \circ\mathsf{T}[1]\circ\mathsf{T}[2]\circ\dots\circ\mathsf{T}[i-1]$ .

We define the suffix tree of text $\mathsf{T}$ as a compacted trie of all circular suffixes of $\mathsf{T}$ . This is equivalent to the standard definition (i.e., without the term “circular”), since $\mathsf{T}[i]=\$$ iff $i=n$ . It consists of $n$ leaves and less than $n$ internal nodes. The edges are (implicitly) labeled with substrings of $\mathsf{T}$ . We use $\mathrm{str}(u)$ to denote the concatenation of edge labeled on the path from root to node $u$ . Also, let $\mathrm{strlen}(u)$ be the length of $\mathrm{str}(u)$ (called string depth). The $i$ -th leftmost leaf in the suffix tree is denoted by $\ell_{i}$ . The suffix array and the inverse suffix array of $\mathsf{T}$ are the arrays $\operatorname{SA}[1\mathinner{.\,.\allowbreak}n]$ and $\operatorname{ISA}[1\mathinner{.\,.\allowbreak}n]$ , respectively, where $\operatorname{SA}[j]=i$ and $\operatorname{ISA}[i]=j$ iff the $j$ -th smallest circular suffix in lexicographic order is $\mathsf{T}[i\mathinner{.\,.\allowbreak}n]\circ\mathsf{T}[1\mathinner{.\,.% \allowbreak}i)$ . Equivalently, $\mathrm{str}(\ell_{j})=\mathsf{T}[i\mathinner{.\,.\allowbreak}n]\circ\mathsf{T% }[1\mathinner{.\,.\allowbreak}i)$ .

For a string $P$ , the locus node $u$ (if it exists) is the node closest to root such that $P$ is a prefix of $\mathrm{str}(u)$ and the range of leaves of $u$ is called the suffix range of $P$ , denoted by $[\mathsf{sp}(P),\mathsf{ep}(P)]$ . The set $\{\operatorname{SA}[k]\mid k\in[\mathsf{sp}(P),\mathsf{ep}(P)]\}$ denotes the occurrences of $P$ in $\mathsf{T}$ . The longest common extension, denoted by $\operatorname{LCE}(i,j)$ is the length of the longest common prefix of the suffixes of $\mathsf{T}$ starting positions $i$ and $j$ , which is the same as $\mathrm{strlen}(u)$ , where $u$ is the lowest common ancestor (LCA) of leaves $\ell_{\operatorname{ISA}[i]}$ and $\ell_{\operatorname{ISA}[j]}$ .

The longest common prefix array $\operatorname{LCP}[1\mathinner{.\,.\allowbreak}n)$ is an array where $\operatorname{LCP}[i]=\operatorname{LCE}(\operatorname{SA}[i],\operatorname{SA% }[i+1])$ . Therefore, $\operatorname{LCE}(i,j)$ is the smallest element in $\operatorname{LCP}[x\mathinner{.\,.\allowbreak}y)$ , where $x=\min\{\operatorname{ISA}[i],\operatorname{ISA}[j]\}$ and $y=\max\{\operatorname{ISA}[i],\operatorname{ISA}[j]\}$ . The permuted longest common prefix array $\operatorname{pLCP}[1\mathinner{.\,.\allowbreak}n)$ is defined as $\operatorname{pLCP}[j]=\operatorname{LCP}[\operatorname{ISA}[j]]=\operatorname% {LCE}(j,\operatorname{SA}[\operatorname{ISA}[j]+1])$ . Note that the argument of $\operatorname{LCP}[\cdot]$ is a leaf position in the suffix tree, whereas that of $\operatorname{pLCP}[\cdot]$ is a position in the text. We will later see that $\operatorname{pLCP}$ array can be encoded in $2n+o(n)$ bits. See Table 1 for an example.

Table 1:

\operatorname{SA},\operatorname{ISA},\operatorname{LCP},\operatorname{pLCP},% \operatorname{BWT},\operatorname{PA},\operatorname{IPA},\operatorname{LCS}

, and

\operatorname{pLCS}

values for

\mathsf{T}[1\mathinner{.\,.\allowbreak}12]=mississippi\$

.

$i$	1	2	3	4	5	6	7	8	9	10	11	12
$\mathsf{T}$ [1..12]	m	i	s	s	i	s	s	i	p	p	i	$
$\operatorname{SA}$ [1..12]	12	11	8	5	2	1	10	9	7	4	6	3
$\operatorname{ISA}$ [1..12]	6	5	12	10	4	11	9	3	8	7	2	1
$\operatorname{LCP}$ [1..12]	0	1	1	4	0	0	1	0	2	1	3	-
$\operatorname{pLCP}$ [1..12]	0	0	-	1	4	3	2	1	0	1	1	0
$\operatorname{BWT}$ [1..12]	i	p	s	s	m	$	p	i	s	s	i	i
$\operatorname{PA}$ [1..12]	12	2	11	5	8	1	9	10	3	6	4	7
$\operatorname{IPA}$ [1..12]	6	2	9	11	4	10	12	5	7	8	3	1
$\operatorname{LCS}$ [1..12]	0	1	1	4	0	0	1	0	2	1	2	-
$\operatorname{pLCS}$ [1..12]	0	1	2	2	4	1	-	0	1	0	1	0

2.3 Prefix Tree, Prefix Array and Longest Common Suffix (LCS) Array

We now introduce the prefix tree and prefix array of the text, which are equivalent to the suffix tree and suffix array of the reversed text. These alternative definitions are introduced purely for notational convenience.

The prefix of $\mathsf{T}$ ending at position $i$ is $\mathsf{T}[1\mathinner{.\,.\allowbreak}i]$ . The circular prefix of $\mathsf{T}$ ending at $i$ is $\mathsf{T}(i\mathinner{.\,.\allowbreak}n]\circ\mathsf{T}[1\mathinner{.\,.% \allowbreak}i]$ and its reverse is $\mathsf{T}[i]\circ\mathsf{T}[i-1]\circ\dots\circ\mathsf{T}[1]\circ\mathsf{T}[n% ]\circ\mathsf{T}[n-1]\circ\dots\circ\mathsf{T}[i+1]$ . The prefix tree of $\mathsf{T}$ is a compacted trie of the reverse of all circular prefixes of $\mathsf{T}$ . It will have $n$ leaves and less than $n$ internal nodes, and the edges will be labeled as in the suffix tree, but with substrings of $\overleftarrow{\mathsf{T}}$ . We shall reuse the notations $\ell_{i}$ , $\mathrm{str}(\cdot)$ and $\mathrm{strlen}(\cdot)$ as before when the context is clear. We define prefix array $\operatorname{PA}[1\mathinner{.\,.\allowbreak}n]$ and inverse prefix array $\operatorname{IPA}[1\mathinner{.\,.\allowbreak}n]$ of $\mathsf{T}$ as $\operatorname{PA}[j]=i$ and $\operatorname{IPA}[i]=j$ iff $\mathrm{str}(\ell_{j})$ is the “reverse” of the circular prefix of $\mathsf{T}$ ending at $i$ . Define $\overleftarrow{\operatorname{LCE}}(i,j)$ as the length of the longest common suffix of the prefixes of $\mathsf{T}$ ending at positions $i$ and $j$ . Therefore, $\overleftarrow{\operatorname{LCE}}(i,j)=\mathrm{strlen}(u)$ , where $u$ is the LCA of leaves $\ell_{\operatorname{IPA}[i]}$ and $\ell_{\operatorname{IPA}[j]}$ in the prefix tree. The longest common suffix (LCS) array $\operatorname{LCS}[1\mathinner{.\,.\allowbreak}n)$ is an array where $\operatorname{LCS}[i]=\overleftarrow{\operatorname{LCE}}(\operatorname{PA}[i],% \operatorname{PA}[i+1])$ and the permuted longest common suffix (pLCS) array is such that $\operatorname{pLCS}[j]=\operatorname{LCS}[\operatorname{IPA}[j]]=% \overleftarrow{\operatorname{LCE}}(j,\operatorname{PA}[\operatorname{IPA}[j]+1])$ . See Table 1 for an example.

2.4 The FM-index

The FM-index [7] is a compressed representation of the suffix array $\operatorname{SA}$ , based on the text’s BWT [5]. It is a self-index, meaning it does not require access to the original text in order to function. The BWT of $\mathsf{T}$ , denoted by $\operatorname{BWT}[1\mathinner{.\,.\allowbreak}n]$ is a permutation of characters in $\mathsf{T}$ , where $\operatorname{BWT}[i]$ denotes the last character of $i$ -th lexicographically smallest circular suffix of $\mathsf{T}$ . In other words, $\operatorname{BWT}[i]=\mathsf{T}[\operatorname{SA}[i]-1]$ if $\operatorname{SA}[i]\neq 1$ and is $\$$ otherwise. See Table 1 for an example.

The Last-to-Front operation is defined as $\operatorname{LF}[i]=\operatorname{ISA}[\operatorname{SA}[i]-1]$ if $\operatorname{SA}[i]\neq 1$ and is $1$ otherwise. Moreover, $\operatorname{LF}[i]=Count(c)+\mathsf{rank}_{\operatorname{BWT}}(i,c)$ , where $c=\operatorname{BWT}[i]$ and $Count(c)=|\{j\mid\operatorname{BWT}[j]<c\}|$ . By maintaining $\operatorname{BWT}$ as a wavelet tree, along with $Count(c)$ for all $c\in\Sigma$ , in $O(\sigma\log n)$ bits, we can support $\operatorname{LF}[\cdot]$ operation in $O(t_{wt})$ time.

We next focus on $\operatorname{SA}[\cdot]$ and $\operatorname{ISA}[\cdot]$ operations. Let $\operatorname{LF}^{k}[i]=\operatorname{LF}[\operatorname{LF}^{k-1}[i]]$ if $k>1$ and is $\operatorname{LF}[i]$ if $k=1$ , then $\operatorname{SA}[\operatorname{LF}^{k}[i]]=\operatorname{SA}[i]-k$ . For a parameter $\tau$ , explicitly store the pairs $(i,\operatorname{SA}[i])$ with $\operatorname{SA}[i]$ being a multiple of $\tau$ ; space is $O((n/\tau)\log n)$ bits. To decode $\operatorname{SA}[i]$ , where $(i,\operatorname{SA}[i])$ is not stored, we compute $\operatorname{LF}[i],\operatorname{LF}^{2}[i],\operatorname{LF}^{3}[i],\dots$ until we find an $\operatorname{LF}^{k}[i]$ , where $(\operatorname{LF}^{k}[i],\operatorname{SA}[\operatorname{LF}^{k}[i]])$ is stored, and return $\operatorname{SA}[i]=k+\operatorname{SA}[\operatorname{LF}^{k}[i]]$ . To decode $\operatorname{ISA}[j]$ , where $(\operatorname{ISA}[j],j)$ is not stored, we find $j^{\prime}=\tau\lceil j/\tau\rceil$ and $i^{\prime}=\operatorname{ISA}[j^{\prime}]$ (note that $(i^{\prime},j^{\prime})$ is stored) and return $\operatorname{LF}^{k}[i^{\prime}]$ , where $k=j^{\prime}-j$ . In both cases, the sampling scheme guarantees $k\leq\tau$ and the resulting time complexity, denoted by $t_{sa}$ , is $k\cdot t_{wt}=O(\tau\cdot t_{wt})$ .

We can also extract any substring $\mathsf{T}[j\mathinner{.\,.\allowbreak}j+r)$ in time $O(t_{sa}+r\cdot t_{wt})$ as follows: find $x=\operatorname{ISA}[j+r]$ , $\operatorname{LF}[x],\operatorname{LF}^{2}[x],\operatorname{LF}^{3}[x],\dots,% \operatorname{LF}^{r-1}[x]$ successively and output the string $\operatorname{BWT}[\operatorname{LF}^{r-1}[x]]\circ\dots\operatorname{BWT}[% \operatorname{LF}[x]]\circ\operatorname{BWT}[x]$ .

Lemma 1.

Suppose the text’s $\operatorname{BWT}$ is available as a wavelet tree supporting basic operations (i.e., $\mathsf{rank},\mathsf{select}$ and $\mathsf{access}$ ) in $t_{wt}$ time, then with $O((n/\tau)\log n)$ extra bits, we can support $\operatorname{SA}/\operatorname{ISA}$ queries in time $t_{sa}=O(\tau\cdot t_{wt})$ and extract any substring $\mathsf{T}[j\mathinner{.\,.\allowbreak}j+r)$ in time $O(t_{sa}+r\cdot t_{wt})$ . Here, $\tau$ is a parameter.

2.5 Longest Common Extension (LCE) and Related Queries

The following two results, along with the succinct representation of the suffix tree topology as in Section 2.1.3, gives the compressed representation of the suffix tree. We present sketches of the proofs for these known results, since we will be adapting them in subsequent sections.

Lemma 2 (Sadakane [31]).

The $\operatorname{pLCP}$ array can be encoded in $2n+o(n)$ bits, such that $\operatorname{pLCP}[j]$ for any position $j$ in the text can be retrieved in $O(1)$ time.

Proof.

Key observation is that $\operatorname{pLCP}[j+1]\geq\operatorname{pLCP}[j]-1$ for all $j$ . To prove this, note that it is trivially true when $\operatorname{pLCP}[j]=0$ . Otherwise, let $\operatorname{SA}[\operatorname{ISA}[j]+1]=j^{\prime}$ . Then $\operatorname{ISA}[j+1]<\operatorname{ISA}[j^{\prime}+1]$ , therefore $\operatorname{pLCP}[j+1]$ is atleast $\operatorname{LCE}(j+1,j^{\prime}+1)=\operatorname{pLCP}[j]-1$ . By rearranging the inequality and by adding $j$ on both sides, we get $j+\operatorname{pLCP}[j]\leq(j+1)+\operatorname{pLCP}[j+1]$ . This means, the function $f(j)=j+\operatorname{pLCP}[j]$ is non-decreasing. Moreover $f(j)\in[1,n]$ , because $\operatorname{pLCP}[n]=0$ and hence $f(n)=n$ . Therefore, we can store the function $f(\cdot)$ as a bit string $B=0^{f(1)}10^{f(2)-f(1)}10^{f(3)-f(2)}1\dots$ with $O(1)$ time rank/select support in $2n+o(n)$ bits. To decode $\operatorname{pLCP}[j]$ , we first find $p=\mathsf{select}_{B}(j,1)$ , the position of $j$ -th $1$ in $B$ in $O(1)$ time. Then we have $f(j)=p-j$ , the number of $0$ ’s until $p$ , and $\operatorname{pLCP}[j]=f(j)-j$ . $\hfill\blacktriangleleft$

Lemma 3 ( $\operatorname{LCE}$ Queries).

By maintaining an auxiliary structure of space $O(n)$ bits along with the FM-index, we can answer $\operatorname{LCE}(\cdot,\cdot)$ queries in $O(t_{sa})$ time.

Proof.

Maintain the encoding of the $\operatorname{pLCP}$ array described in Lemma 2 and an RMQ data structure over the $\operatorname{LCP}$ array, but without explicitly storing the $\operatorname{LCP}$ array itself. To compute $\operatorname{LCE}(i,j)$ , find $i^{\prime}=\operatorname{ISA}[i]$ and $j^{\prime}=\operatorname{ISA}[j]$ . Without loss of generality, assume that $i^{\prime}<j^{\prime}$ . Then find $k^{\prime}\in[i^{\prime},j^{\prime})$ , where $\operatorname{LCP}[k^{\prime}]$ is the smallest in $\operatorname{LCP}[i^{\prime}\mathinner{.\,.\allowbreak}j^{\prime})$ using an RMQ in $O(1)$ time. Then compute $k=\operatorname{SA}[k^{\prime}]$ and return $\operatorname{pLCP}[k]$ . Total time is $O(t_{sa})$ . $\hfill\blacktriangleleft$

We next present an additional result that will be used later.

Lemma 4 ( $\overleftarrow{\operatorname{LCE}}$ Queries).

Let $D$ be an integer parameter. By maintaining an auxiliary structure of space $O((n/D)\log n)$ bits, we can compute $\overleftarrow{\operatorname{LCE}}(i,j)$ for any given $i, j$ via $O(\log D)$ number of $\operatorname{LCE}$ queries.

Proof.

For any given text of length $n$ , there exists a standalone data structure of space $O(n/D)$ words, equivalently $O((n/D)\log n)$ bits, that in constant time either correctly computes $\operatorname{LCE}(i,j)$ or determines that $\operatorname{LCE}(i,j)\leq D^{2}$ for any given $i, j$ [4]. We maintain this data structure over the reversed text, which allows us to correctly compute $\overleftarrow{\operatorname{LCE}}(i,j)$ or to determine that $\overleftarrow{\operatorname{LCE}}(i,j)\leq D^{2}$ . When $\overleftarrow{\operatorname{LCE}}(i,j)\leq D^{2}$ , we exploit the following observation: $\overleftarrow{\operatorname{LCE}}(i,j)\geq t$ if and only if $\operatorname{LCE}(i-t+1,j-t+1)\geq t$ , and binary search on $t\in[0,D^{2}]$ . This will give us $\overleftarrow{\operatorname{LCE}}(i,j)$ in $O(\log D)$ number of $\operatorname{LCE}$ queries. $\hfill\blacktriangleleft$

3 Relative Encoding of $\operatorname{PA}$ in $O(n)$ Extra bits

The prefix tree/array of $\mathsf{T}$ corresponds to the suffix tree/array of $\overleftarrow{T}$ . Specifically, the $i$ -th entry in the suffix array of $\overleftarrow{\mathsf{T}}$ is $(n-\operatorname{PA}[i]+1)$ . Therefore, it suffices to design an encoding of the prefix array.

3.1 Basic Components

Let $\pi\neq 0$ be an integer parameter (positive or negative). We now introduce arrays $\operatorname{LCP}_{\pi}$ and $\operatorname{pLCP}_{\pi}$ , which are generalizations of $\operatorname{LCP}$ array and $\operatorname{pLCP}$ array as follows:

\operatorname{LCP}_{\pi}[i]=\operatorname{LCE}(\operatorname{SA}[i],% \operatorname{SA}[i+\pi]),\text{ where }i+\pi\leq n

\operatorname{pLCP}_{\pi}[j]=\operatorname{LCP}_{\pi}[\operatorname{ISA}[j]]=% \operatorname{LCE}(j,\operatorname{SA}[\operatorname{ISA}[j]+\pi]),\text{ % where }\operatorname{ISA}[j]+\pi\leq n

The encoding technique by Sadakane (see Lemma 2) extends to the $\operatorname{pLCP}_{\pi}$ array as follows.

Lemma 5.

Let $\pi\neq 0$ be an integer parameter (positive or negative). We can encode $\operatorname{pLCP}_{\pi}$ in $O(n)$ bits, and return $\operatorname{pLCP}_{\pi}[j]$ for any text position $j$ in $O(1)$ time.

Proof.

We first prove that $\operatorname{pLCP}_{\pi}[j+1]\geq\operatorname{pLCP}_{\pi}[j]-1$ for all $j$ . Clearly, the inequality holds when $\operatorname{pLCP}_{\pi}[j]=0$ . Otherwise, let $\operatorname{SA}[\operatorname{ISA}[j]+\pi]=j^{\prime}$ and $\operatorname{SA}[\operatorname{ISA}[j+1]+\pi]=j^{\prime\prime}$ . Then we can see that $\operatorname{ISA}[j+1]<\operatorname{ISA}[j^{\prime\prime}]\leq\operatorname{% ISA}[j^{\prime}+1]$ if $\pi$ is positive and $\operatorname{ISA}[j+1]>\operatorname{ISA}[j^{\prime\prime}]\geq\operatorname{% ISA}[j^{\prime}+1]$ if $\pi$ is negative. In both cases, $\operatorname{pLCP}_{\pi}[j+1]=\operatorname{LCE}(j+1,j^{\prime\prime})\geq% \operatorname{LCE}(j+1,j^{\prime}+1)\geq\operatorname{LCE}(j,j^{\prime})-1=% \operatorname{pLCP}_{\pi}[j]-1$ . By rearranging the inequality as in the proof of Lemma 2, we obtain a non-decreasing function $f_{\pi}(j)=j+\operatorname{pLCP}_{\pi}[j]\in\mathcal{O}(n)$ . We store $f_{\pi}$ as bit string $B=0^{f_{\pi}(1)}10^{f_{\pi}(2)-f_{\pi}(1)}10^{f_{\pi}(3)-f_{\pi}(2)}1\dots$ with $O(1)$ time rank/select support in $O(n)$ bits. Then $\operatorname{pLCP}_{\pi}[j]$ is given by $f_{\pi}(j)-j=(\mathsf{select}_{B}(j,1)-j)-j$ . $\hfill\blacktriangleleft$

Lemma 6 (Sampled $\operatorname{pLCP}_{\pi}$ ).

Let $\pi\neq 0$ be an integer parameter (positive or negative) and $S\subseteq[n]$ be a set of size $s$ . There exists a standalone structure of space $O(s\log(n/s))$ bits that returns $\operatorname{pLCP}_{\pi}[j]$ for any given $j\in S$ in $O(1)$ time.

Proof.

We modify the proof in Lemma 5 as follows. Define a bit string $C[1\mathinner{.\,.\allowbreak}n]$ , where $C[j]=1$ iff $j\in S$ . Define another bit string $B=0^{f_{\pi}(s_{1})}10^{f_{\pi}(s_{2})-f_{\pi}(s_{1})}10^{f_{\pi}(s_{3})-f_{% \pi}(s_{2})}1\dots$ , where $s_{i}=\mathsf{select}_{C}(i,1)$ . Maintain $C$ and $B$ as indexible dictionaries in $O(s\log(n/s))$ bits with efficient rank/select support. Given any $j\in S$ , we find $p=\mathsf{rank}_{C}(j,1)$ in $O(1)$ time using a partial-rank query. Then find $f_{\pi}(j)=\mathsf{select}_{B}(p,1)-p$ and report $\operatorname{pLCP}_{\pi}[j]=f_{\pi}(j)-j$ . $\hfill\blacktriangleleft$

The Longest common suffix (LCS) array and the permuted longest common suffix (pLCS) array can also be generalized as follows.

\operatorname{LCS}_{\pi}[i]=\overleftarrow{\operatorname{LCE}}(\operatorname{% PA}[i],\operatorname{PA}[i+\pi]),\text{ where }i+\pi\leq n

\operatorname{pLCS}_{\pi}[j]=\operatorname{LCS}_{\pi}[\operatorname{IPA}[j]]=% \overleftarrow{\operatorname{LCE}}(j,\operatorname{PA}[\operatorname{IPA}[j]+% \pi]),\text{ where }\operatorname{IPA}[j]+\pi\leq n

Since $\operatorname{LCS}_{\pi}$ and $\operatorname{pLCS}_{\pi}$ are equivalent to $\operatorname{LCP}_{\pi}$ and $\operatorname{pLCP}_{\pi}$ of the reverse of $\mathsf{T}$ , the following result is an immediate corollary of Lemma 6.

Corollary 7 (Sampled $\operatorname{pLCS}_{\pi}$ ).

Let $\pi\neq 0$ be an integer parameter (positive or negative) and $S\subseteq[n]$ be a set of size $s$ . There exists a standalone structure of space $O(s\log(n/s))$ bits that returns $\operatorname{pLCS}_{\pi}[j]$ for any given $j\in S$ in $O(1)$ time.

3.2 The Data Structure

Assuming the availability of an FM-index of $\mathsf{T}$ in its standard from as described in Section 2.4, we now present components in the relative encoding of the prefix array $\operatorname{PA}$ of $\mathsf{T}$ . For $h\in[1,\log^{*}n]$ , define $\Delta_{h}$ as $(\log^{(h)}n)^{2}$ round to the integer which is the next power of $2$ . i.e., $\Delta_{h}=2^{\lceil 2\log^{(h+1)}n\rceil}$ . Here $\log^{(h)}n=\log n$ if $h=1$ and is $\log(\log^{(h-1)}n)$ if $h>1$ , and $\log^{*}n$ is the smallest $h$ where $\log^{(h)}n\leq 1$ . Therefore, $\Delta_{\log^{*}n}=1$ . Also let $\Delta_{0}=n+1$ . We denote the predecessor and successor of $i$ that are multiples of $\Delta_{h}$ by $i_{h}^{\prime}=\Delta_{h}\cdot\lfloor i/\Delta_{h}\rfloor$ and $i_{h}^{\prime\prime}=\Delta_{h}\cdot\lceil i/\Delta_{h}\rceil$ , respectively. Therefore, when $\Delta_{h}$ divides $i$ , we have $i_{h}^{\prime}=i_{h}^{\prime\prime}=i$ .

3.2.1 Technical Overview

If $i$ is divisible by $\Delta_{1}$ , we explicitly store $\operatorname{PA}[i]$ using $O(\log n)$ bits. If $i$ is divisible by $\Delta_{2}$ , but not by $\Delta_{1}$ , we encode $\operatorname{PA}[i]$ relative to either $\operatorname{PA}[i^{\prime}_{1}]$ or $\operatorname{PA}[i^{\prime\prime}_{1}]$ (depending on the case, to be described) using $\log\Delta_{1}$ bits. Similarly, if $i$ is divisible by $\Delta_{3}$ , but not by $\Delta_{2}$ , we encode $\operatorname{PA}[i]$ relative to either $\operatorname{PA}[i^{\prime}_{2}]$ or $\operatorname{PA}[i^{\prime\prime}_{2}]$ using $\log\Delta_{2}$ bits. More generally, we encode $\operatorname{PA}[i]$ relative to either $\operatorname{PA}[i^{\prime}_{f-1}]$ or $\operatorname{PA}[i^{\prime\prime}_{f-1}]$ using $\log\Delta_{f-1}$ bits, where $f\leq\log^{*}n$ is the smallest integer such that $i$ is divisible by $\Delta_{f}$ . The function $\Delta_{h}$ is chosen carefully such that the total space usage is bounded by a sum that converges to $O(n)$ bits. The algorithm for decoding $\operatorname{PA}[i]$ works as follows: for $h=1,2,\dots$ , decode either $i^{\prime}_{h}$ or $i^{\prime\prime}_{h}$ (depending on the case) and terminate at $h=f$ where $i^{\prime}_{f}=i^{\prime\prime}_{f}=i$ , thereby yielding $\operatorname{PA}[i]$ . We present the details next.

3.2.2 Components of the Data Structure

For each $h\in[1,\log^{*}n]$ , maintain arrays $\operatorname{PA}_{h}[1,n/\Delta_{h}]$ as described below.

$\blacksquare$

If $i$ is divisible by $\Delta_{1}$ , we store $\operatorname{PA}[i]$ explicitly in $\operatorname{PA}_{1}$ as $\operatorname{PA}_{1}[i/\Delta_{1}]=\operatorname{PA}[i]$ .
$\blacksquare$

If $i$ is not divisible by $\Delta_{1}$ , we find the smallest integer $f$ where $i$ is divisible by $\Delta_{f}$ ; such an $f\in[2,\log^{*}n]$ exists since $\Delta_{\log^{*}n}=1$ . Then store a value $\theta_{i}$ in $\operatorname{PA}_{f}$ as $\operatorname{PA}_{f}[i/\Delta_{f}]=\theta_{i}$ . The value $\theta_{i}$ is determined by certain nodes in the prefix tree, which in turn are based on $i^{\prime}_{f-1}$ and $i^{\prime\prime}_{f-1}$ as illustrated in Figure 1. Let $u^{\prime}=\operatorname{LCA}(\ell_{i^{\prime}_{f-1}},\ell_{i})$ and $u^{\prime\prime}=\operatorname{LCA}(\ell_{i},\ell_{i^{\prime\prime}_{f-1}})$ , and $u$ be the lowest node among $u^{\prime}$ and $u^{\prime\prime}$ . Also let $Q=\mathrm{str}(u)$ and node $w$ be the child of $u$ on the path to $\ell_{i}$ and $\beta$ be the leading character on the edge from $u$ to $w$ . This means that a substring of $\mathsf{T}$ matching $\beta\circ\overleftarrow{Q}$ ends at position $\operatorname{PA}[i]$ , and therefore starts at $\operatorname{PA}[i]-|Q|$ . Consequently, $\operatorname{SA}[\mathsf{sp}(\beta\circ\overleftarrow{Q})\mathinner{.\,.% \allowbreak}\mathsf{ep}(\beta\circ\overleftarrow{Q})]$ must contain the entry $\operatorname{PA}[i]-|Q|$ . Then $\theta_{i}$ is defined as the offset within the suffix range of $\beta\circ\overleftarrow{Q}$ , Specifically,

$\operatorname{SA}[\mathsf{sp}(\beta\circ\overleftarrow{Q})+\theta_{i}]=% \operatorname{PA}[i]-|Q|.$

Finally, $0\leq\theta_{i}\leq\mathsf{ep}(\beta\circ\overleftarrow{Q})-\mathsf{sp}(\beta% \circ\overleftarrow{Q})+1=\mathsf{size}(w)<\Delta_{f-1}$ ; therefore, we can store $\theta_{i}$ using $\log\Delta_{f-1}=O(\log^{(f)}n)$ bits.

Figure 1: Here

u=u^{\prime}

. The dashed lines denote the range leaves under the respective nodes.

While decoding $\operatorname{PA}[i]$ , the answer is readily available from $\operatorname{PA}_{1}$ if $i$ is a multiple of $\Delta_{1}$ . Otherwise, we utilize the relationship $\operatorname{PA}[i]=\operatorname{SA}[\mathsf{sp}(\beta\circ\overleftarrow{Q}% )+\theta_{i}]+|Q|$ , where $\theta_{i}$ is retrieved from $\operatorname{PA}_{f}$ ; however, $|Q|$ and $\mathsf{sp}(\beta\circ\overleftarrow{Q})$ are not explicitly stored. To find them, we maintain the following auxiliary structures.

$\blacksquare$

The succinct encodings of the topologies of both the suffix tree and the prefix tree.
$\blacksquare$

For each $h\in[1,\log^{*}n]$ , we maintain a collection of structures as in Corollary 7. Precisely, for a fixed $h$ , we assign $S=\{j\mid\operatorname{ISA}[j]\nobreak\ \text{ is divisible by }\Delta_{h-1}\}$ and make a separate structure for each non-zero value of $\pi\in\{-\Delta_{h-1},-\Delta_{h-1}+\Delta_{h},\dots,\Delta_{h-1}-\Delta_{h},% \Delta_{h-1}\}$ . Note that for a fixed $h$ , $|S|=n/\Delta_{h-1}$ and the number of structures is $2\Delta_{h-1}/\Delta_{h}$ .

This completes the description of our data structure.

3.2.3 Space Complexity Analysis

The length of $\operatorname{PA}_{h}$ is $n/\Delta_{h}$ and each entry in $\operatorname{PA}_{h}$ is encoded in $\log\Delta_{h-1}=O(\log^{(h)}n)$ bits. Therefore, space is $n/\Delta_{h}\cdot\log\Delta_{h-1}=O(n/\log^{(h)}n)$ bits for a fixed $h$ and $\sum_{h=1}^{\log^{*}n}\frac{n}{\log^{(h)}n}=O(n)$ bits for all $h\in[1,\log^{*}n]$ combined. The tree topologies takes $O(n)$ bits. The space (in bits) required by all versions of the structures in Corollary 7 can also be bounded by $O(n)$ , as shown below, resulting in an overall space complexity of $O(n)$ bits.

\sum_{h=1}^{\log^{*}n}\frac{2\Delta_{h-1}}{\Delta_{h}}\cdot\frac{n}{\Delta_{h-% 1}}\log\Delta_{h-1}=2\sum_{h=1}^{\log^{*}n}\frac{n}{\log^{(h)}n}=O(n).

3.3 Algorithm for Decoding $\operatorname{PA}[i]$

At first, compute $f\in[1,\log^{*}n]$ , the smallest integer such that $\Delta_{f}$ divides $i$ . Then, identify nodes $u^{\prime}=\operatorname{LCA}(\ell_{i^{\prime}_{f-1}},\ell_{i})$ and $u^{\prime\prime}=\operatorname{LCA}(\ell_{i},\ell_{i^{\prime\prime}_{f-1}})$ in the prefix tree, and let $u$ be the lowest node among them. This step takes only $O(1)$ time using tree encodings. Let $Q=\mathrm{str}(u)$ and $\beta$ be the leading character on the edge from $u$ to its child $w$ on the path to $\ell_{i}$ . Our next goal is to compute $|Q|$ and the suffix range $[\mathsf{sp}(\beta\circ\overleftarrow{Q}),\mathsf{ep}(\beta\circ\overleftarrow% {Q})]$ of $\beta\circ\overleftarrow{Q}$ , then return $\operatorname{PA}[i]=\operatorname{SA}[\mathsf{sp}(\beta\circ\overleftarrow{Q}% )+\theta_{i}]+|Q|$ . There are two cases.

1.
Case $u=u^{\prime}$ (i.e., $u=u^{\prime}=u^{\prime\prime}$ or $u=u^{\prime}\neq u^{\prime\prime}$ ): In this case, $\operatorname{PA}[i]$ is encoded relative to $\operatorname{PA}[i^{\prime}_{f-1}]$ . We start with an assumption that $r=\operatorname{PA}[i^{\prime}_{f-1}]$ has already been computed. Observe that $|Q|=\mathrm{strlen}(u)=\overleftarrow{\operatorname{LCE}}(\operatorname{PA}[i^% {\prime}_{f-1}],\operatorname{PA}[i])=\operatorname{pLCS}_{\pi}[r]$ , where $\pi=i-i^{\prime}_{f-1}$ . Note also that $r\in S=\{j\mid\operatorname{ISA}[j]\nobreak\ \text{ is divisible by }\Delta_{f% -1}\}$ and $\pi\in\{\Delta_{h},2\Delta_{h},\dots,\Delta_{h-1}\}$ . Recall that we already maintain the data structure of Corollary 7 for this specific choice of $S$ and $\pi$ ; querying it yields $\operatorname{pLCS}_{\pi}[r]$ , and thus $|Q|$ , in $O(1)$ time. We then infer $\overleftarrow{Q}=\mathsf{T}[r-|Q|+1\mathinner{.\,.\allowbreak}r]$ and invoke the steps below.
1. (a)
  
  Find the suffix range $[\mathsf{sp}(\overleftarrow{Q}),\mathsf{ep}(\overleftarrow{Q})]$ of $\overleftarrow{Q}$ : Find the leaf $\ell_{g}$ in the suffix tree, where $g={\operatorname{ISA}[r-|Q|+1]}$ (this leaf corresponds to the suffix $\mathsf{T}[r-|Q|+1\mathinner{.\,.\allowbreak}]$ ), then find its ancestor $v$ such that $\mathsf{size}(v)=\mathsf{size}(u)$ , and return the range of leaves of $v$ as the answer. Note that $v$ exists and it can be computed via binary search, specifically $O(\log n)$ number of $\mathsf{level\_ancestor}$ queries. The first step requires an $\operatorname{ISA}$ query (in time $t_{sa}$ ), the second step takes $O(\log n)$ time and the third step takes $O(1)$ time.
2. (b)
  
  Find $\beta$ : Let $[a,b]$ be the range of leaves of $u$ (in the prefix tree) and let $k=i-a+1$ . Then, $\ell_{i}$ will be the $k$ -th leftmost leaf in the subtree of $u$ , which implies $\beta$ will be the $k$ -th smallest character in $\operatorname{BWT}[\mathsf{sp}(\overleftarrow{Q})\mathinner{.\,.\allowbreak}% \mathsf{ep}(\overleftarrow{Q})]$ . So, perform a range quantile query in time $t_{quantile}$ and find $\beta$ .
3. (c)
  
  Find the suffix range $[\mathsf{sp}(\beta\circ\overleftarrow{Q}),\mathsf{ep}(\beta\circ\overleftarrow% {Q})]$ of $\beta\circ\overleftarrow{Q}$ : Let $x$ (resp., $y$ ) be the first (resp., last) occurrence of $\beta$ in $\operatorname{BWT}[\mathsf{sp}(\overleftarrow{Q})\mathinner{.\,.\allowbreak}% \mathsf{ep}(\overleftarrow{Q})]$ . Then, $[\operatorname{LF}[x],\operatorname{LF}[y]]$ will be the suffix range of $\beta\circ\overleftarrow{Q}$ which can be answered in $O(t_{wt})$ time.
4. (d)
  
  Compute $\operatorname{PA}[i]=\operatorname{SA}[\mathsf{sp}(\beta\circ\overleftarrow{Q}% )+\theta_{i}]+|Q|$ and return it. Note that $\theta_{i}$ is stored explicitly, and hence this step takes $\mathcal{O}(t_{sa})$ time.
Total time is $O(t_{sa}+\log n+t_{quantile}+t_{wt})$ .
2.

Case $u\neq u^{\prime}$ (i.e, $u=u^{\prime\prime}\neq u^{\prime}$ ): In this case, $\operatorname{PA}[i]$ is encoded relative to $\operatorname{PA}[i^{\prime\prime}_{f-1}]$ . As before, we assume that $r=\operatorname{PA}[i^{\prime\prime}_{f-1}]$ has already been computed. Observe that $|Q|=\mathrm{strlen}(u)=\overleftarrow{\operatorname{LCE}}(\operatorname{PA}[i^% {\prime\prime}_{f-1}],\operatorname{PA}[i])=\operatorname{pLCS}_{\pi}[r]$ , where $\pi=i-i^{\prime\prime}_{f-1}$ . Note also that $r\in S=\{j\mid\operatorname{ISA}[j]\nobreak\ \text{ is divisible by }\Delta_{f% -1}\}$ and $\pi\in\{-\Delta_{h},-2\Delta_{h},\dots,-\Delta_{h-1}\}$ . Recall that we already maintain the structure of Corollary 7 for this specific choice of $S$ and $\pi$ ; querying it yields $|Q|=\operatorname{pLCS}_{\pi}[r]$ in $O(1)$ time. We then infer $\overleftarrow{Q}=\mathsf{T}[r-|Q|+1\mathinner{.\,.\allowbreak}r]$ , invoke the same steps as before and obtain $\operatorname{PA}[i]$ in $O(t_{sa}+\log n+t_{quantile}+t_{wt})$ time.

In summary, decoding $\operatorname{PA}[i]$ reduces to decoding either $\operatorname{PA}[i^{\prime}_{f-1}]$ or $\operatorname{PA}[i^{\prime\prime}_{f-1}]$ (depending on the case) in $O(t_{sa}+\log n+t_{quantile}+t_{wt})$ time, which recursively reduces to decoding $\operatorname{PA}[i^{\prime}_{f-2}]$ or $\operatorname{PA}[i^{\prime\prime}_{f-2}]$ , and so forth, until reaching $\operatorname{PA}[i^{\prime}_{1}]$ or $\operatorname{PA}[i^{\prime\prime}_{1}]$ , which are explicitly stored. The overall time is $O((t_{sa}+\log n+t_{quantile}+t_{wt})\cdot f)\subseteq O((\tau\cdot t_{wt}+% \log n+t_{quantile})\log^{*}n)$ .

Theorem 8.

Let the Burrows-Wheeler Transform (BWT) of a text $\mathsf{T}[1\mathinner{.\,.\allowbreak}n]$ be maintained in a data structure that supports basic queries ( $\mathsf{rank}$ , $\mathsf{select}$ , and $\mathsf{access}$ ) in $t_{wt}$ time, and range quantile queries in $t_{quantile}$ time. Then, for any parameter $\tau\geq 1$ , we can maintain a sampled subset of $n/\tau$ suffix array values using $O((n/\tau)\log n)$ bits of additional space, and support suffix array (SA), inverse suffix array (ISA), and longest common extension (LCE) queries in time $t_{sa}=O(\tau\cdot t_{wt})$ .

By maintaining an auxiliary structure of space $O(n)$ bits, we can support prefix array (PA) queries in time $t_{pa}=O((\tau\cdot t_{wt}+t_{quantile}+\log n)\cdot\log^{*}n)$ .

By employing the multiary wavelet tree, where $t_{wt}=O(1+\log\sigma/\log\log n)$ and $t_{quantile}=O(\log\sigma)$ [8], and setting $\tau=\log n$ , we obtain the following result.

Corollary 9.

For any text $\mathsf{T}[1\mathinner{.\,.\allowbreak}n]$ over an alphabet of size $\sigma$ , we can represent its Burrows–Wheeler Transform using a (multiary) wavelet tree in $n\log\sigma+o(n)+O(\sigma\log n)$ bits of space, supporting basic wavelet tree operations (rank, select, access) in time $O(1+\log\sigma/\log\log n)$ and range quantile queries in time $O(\log\sigma)$ . By maintaining some auxiliary structures of space $O(n)$ bits, we can support suffix array (SA), inverse suffix array (ISA), and longest common extension (LCE) queries in time $t_{sa}=O((1+\log\sigma/\log\log n)\log n)$ , and prefix array (PA) queries in time $t_{pa}=O(t_{sa}\cdot\log^{*}n)$ .

4 Relative Encoding of $\operatorname{PA}$ in Sublinear Space

In this section, we present an $O((n/\delta)\log\delta)$ -bit (relative) encoding of $\operatorname{PA}$ , where $\delta>0$ is an integer parameter. Without loss of generality, we assume that $\delta$ is a power of $2$ .

4.1 Basic Components

We now present several useful results.

Lemma 10 (Approximate $\operatorname{pLCP}_{\pi}$ in small space).

Let $\pi\neq 0$ be an integer parameter (positive or negative). There exists a standalone structure of space $O((n/\delta)\log\delta)$ bits that returns $\operatorname{pLCP}^{\approx}_{\pi}[j]$ in $O(\log\delta)$ time, where $\operatorname{pLCP}_{\pi}[j]-\delta\leq\operatorname{pLCP}^{\approx}_{\pi}[j]% \leq\operatorname{pLCP}_{\pi}[j]$ .

Proof.

We obtain this result by modifying Lemma 6. The idea is to select a set $S\subseteq\{1,2,3,\dots,n\}$ of sampled positions and store $f_{\pi}(j)$ values of only those $j\in S$ . The set $S$ is constructed as follows. Initially $S=\{1\}$ . Then for $j=2$ to $n$ , we include $j$ in $S$ iff $j$ is a multiple of $\delta$ or $f_{\pi}(j)-f_{\pi}(j^{\prime})>\delta$ , where $j^{\prime}<j$ is the largest value in $S$ currently. The size of $S$ is $\Theta(n/\delta)$ since $f_{\pi}(\cdot)\leq 2n$ and is non-decreasing. For a query $j$ , we return $f_{\pi}(j^{\prime})-j$ as $\operatorname{pLCP}^{\approx}_{\pi}[j]$ , where $j^{\prime}$ is the predecessor of $j$ in $S$ . The correctness follows from that fact that $f_{\pi}(j^{\prime})\leq f_{\pi}(j)=\operatorname{pLCP}_{\pi}[j]+j\leq f_{\pi}(% j^{\prime})+\delta$ and $j^{\prime}\leq j\leq j^{\prime}+\delta$ , which implies $\operatorname{pLCP}_{\pi}[j]-\delta\leq f_{\pi}(j^{\prime})-j\leq\operatorname% {pLCP}_{\pi}[j]$ .

We now present the implementation details. Define a bit string $C$ corresponding to $S$ , where $C[j]=1$ iff $j\in S$ . Define another bit string $B=0^{f_{\pi}(s_{1})}10^{f_{\pi}(s_{2})-f_{\pi}(s_{1})}10^{f_{\pi}(s_{3})-f_{% \pi}(s_{2})}1...$ , where $s_{i}=\mathsf{select}_{C}(i,1)$ . We maintain both $C$ and $B$ as indexible dictionaries with efficient rank/select support. The space required is $O((n/\delta)\log\delta)$ bits since both $B$ and $C$ are of size $O(n)$ with $\Theta(n/\delta)$ number of $1$ ’s. To recover an approximate value of $\operatorname{pLCP}_{\pi}[j]$ , we first find $k=\delta\lfloor j/\delta\rfloor\in S$ and $r=\mathsf{rank}_{C}(k,1)$ using a partial rank query in $O(1)$ time. Then $j^{\prime}$ , the predecessor of $j$ in $S$ is $\mathsf{select}_{C}(t,1)$ for the $t\in[r,r+\delta]$ , where $\mathsf{select}_{C}(t,1)\leq j<\mathsf{select}_{C}(t+1,1)$ , which can be computed in $O(\log\delta)$ time via binary search. Finally, get $f_{\pi}(j^{\prime})=\mathsf{select}_{B}(t,1)-t$ and return $\operatorname{pLCP}^{\approx}_{\pi}[j]=f_{\pi}(j^{\prime})-j$ . $\hfill\blacktriangleleft$

Lemma 11 (Approximate $\operatorname{pLCS}_{\pi}$ in small space).

Let $\pi\neq 0$ be an integer parameter (positive or negative). There exists a standalone structure of space $O((n/\delta)\log\delta)$ bits that returns $\operatorname{pLCS}^{\approx}_{\pi}[j]$ in $O(\log\delta)$ time, where $\operatorname{pLCS}_{\pi}[j]-\delta\leq\operatorname{pLCS}^{\approx}_{\pi}[j]% \leq\operatorname{pLCS}_{\pi}[j]$ .

Proof.

Follows from Lemma 10, because $\operatorname{pLCS}_{\pi}$ is equivalent to $\operatorname{pLCP}_{\pi}$ of text’s reverse. $\hfill\blacktriangleleft$

Lemma 12 (Exact $\operatorname{pLCP}$ in small space).

By maintaining an $O((n/\delta)\log\delta)$ -bit auxiliary structure with the FM-index, we can return $\operatorname{pLCP}[j]$ for any $j$ in $O(\delta\cdot t_{wt}+t_{sa})$ time.

Proof.

Maintain the structure in Lemma 10 for $\pi=1$ . Let $j^{\prime}=\operatorname{SA}[\operatorname{ISA}[j]+1]$ , then $\operatorname{pLCP}[j]=\operatorname{LCE}(j,j^{\prime})$ . Find $h=\operatorname{pLCP}^{\approx}_{\pi}[j]$ first. Now we know $\operatorname{LCE}(j,j^{\prime})=h+\operatorname{LCE}(j+h,j^{\prime}+h)$ and $\operatorname{LCE}(j+h,j^{\prime}+h)\leq\delta$ . Therefore, simply extract the substrings $\mathsf{T}[j+h\mathinner{.\,.\allowbreak}j+h+\delta)$ and $\mathsf{T}[j^{\prime}+h\mathinner{.\,.\allowbreak}j^{\prime}+h+\delta)$ and compute $\operatorname{LCE}(j+h,j^{\prime}+h)$ naively. $\hfill\blacktriangleleft$

Lemma 13 (Exact $\operatorname{LCE}(\cdot,\cdot)$ in small space).

By maintaining an $O((n/\delta)\log\delta)$ -bit auxiliary structure with FM-index, we can return $\operatorname{LCE}(i,j)$ in time $t_{\operatorname{LCE}}=O((\delta\cdot t_{wt}+t_{sa})\cdot\delta)$ time.

Proof.

We divide the $\operatorname{LCP}$ array into blocks of size $\delta$ . i.e., $\operatorname{LCP}[1\mathinner{.\,.\allowbreak}\delta],\operatorname{LCP}[% \delta+1\mathinner{.\,.\allowbreak}2\delta],\operatorname{LCP}[2\delta+1% \mathinner{.\,.\allowbreak}3\delta]$ , etc. Also let $\operatorname{LCP}^{\prime}[x]$ be the smallest element in $x$ -th block. Maintain a range minimum query structure over $\operatorname{LCP}^{\prime}$ array (space required is $2n/\delta+o(n/\delta)$ bits). Besides this, we will use the result in Lemma 12. When a query $(i,j)$ comes, we compute $\operatorname{LCE}(i,j)$ as follows. Let $i^{\prime}=\operatorname{ISA}[i]$ and $j^{\prime}=\operatorname{ISA}[j]$ . Without loss of generality, lets assume that $i^{\prime}<j^{\prime}$ . To efficiently find our answer $\min_{k\in[i^{\prime},j^{\prime})}\operatorname{LCP}[k]$ , we invoke the following procedure.

$\blacksquare$

If $j^{\prime}-i^{\prime}<3\delta$ , we extract $\operatorname{LCP}[k]=\operatorname{pLCP}[\operatorname{SA}[k]]\nobreak\ % \forall\nobreak\ k\in[i^{\prime},j^{\prime})$ and return the minimum.
$\blacksquare$

Otherwise, we extract $\operatorname{LCP}[k]=\operatorname{pLCP}[\operatorname{SA}[k]]\nobreak\ % \forall\nobreak\ k\in[i^{\prime},i^{\prime}+\delta)\cup(\delta\cdot k^{\prime}% ,\delta\cdot k^{\prime}+\delta]\cup(j^{\prime}-\delta,j^{\prime})$ , where $k^{\prime}=\operatorname{RMQ}_{\operatorname{LCP}^{\prime}}(1+\lceil i^{\prime% }/\delta\rceil,\lfloor j^{\prime}/\delta\rfloor)$ and return the minimum.

In both cases, we are required to make two $\operatorname{ISA}$ queries, $O(\delta)$ number of $\operatorname{SA}$ queries, followed by $O(\delta)$ number of $\operatorname{pLCP}[\cdot]$ queries, which makes the total time $O((\delta\cdot t_{wt}+t_{sa})\delta)$ . $\hfill\blacktriangleleft$

4.2 The Data Structure

4.2.1 Technical Overview

We categorize a query $\operatorname{PA}[i]$ as Type-A if $i$ is divisible by $\delta$ (recall that $\delta$ is a power of $2$ ), and as Type-B otherwise. These two types are handled separately. For Type-A queries, we modify our $O(n)$ -bit solution in a relatively simple manner. Instead of maintaining structures up to $\log^{*}n$ levels, we stop at an earlier stage, which suffices to handle such queries and also helps bound the space. Furthermore, we substitute the standard suffix and prefix tree topologies with their sampled counterparts. However, for Type-B queries, we first decode the $\operatorname{PA}$ values of the predecessor and the successor which are multiples of $\delta$ (i.e., $i^{\prime}=\delta\lfloor i/\delta\rfloor$ and $i^{\prime\prime}=\delta\lceil i/\delta\rceil$ ), by treating them as Type-A queries. Then, we decode all the entries in $\operatorname{PA}[i^{\prime}\mathinner{.\,.\allowbreak}i^{\prime\prime}]$ , first in an unsorted manner; afterward, we sort them to obtain $\operatorname{PA}[i]$ . We accomplish this by splitting this range into the minimal number of subranges such that each subrange corresponds to a subtree of the prefix tree, and processing each subrange carefully. This part is more technical.

4.2.2 Handling Type-A Queries

Observe that our $O(n)$ -bit encoding of $\operatorname{PA}$ composed of two tree topologies and several components corresponding to each $h\in[1,\log^{*}n]$ . However, only the components corresponding to $h\in[1,f]$ are utilized when decoding $\operatorname{PA}[i]$ , where $f$ is the smallest integer in $[1,\log^{*}n]$ such that $\Delta_{f}$ divides $i$ (recall that $\Delta_{h}$ is $(\log^{(h)}n)^{2}$ round to the next power of $2$ ). We exploit this fact to design a space efficient structure for Type-A queries. Let $\lambda\in[1,\log^{*}n]$ be the integer, where $\Delta_{\lambda+1}<\delta^{2}\leq\Delta_{\lambda}$ . We now maintain the components in Section 3.2.2 for only selected values of $h$ (with some modifications) as follows:

1.

All values of $h\in[1,\lambda-1]$ ;
2.

$h=\lambda$ , but modify the value of $\Delta_{h}$ to $\delta^{2}$ .
3.

$h=\lambda+1$ , but modify the value of $\Delta_{h}$ to $\delta$ .

The resulting space in bits is

2\sum_{h=1}^{\lambda+1}\frac{n}{\Delta_{h}}\log\Delta_{h-1}\leq\frac{2n}{% \delta}\log\delta^{2}+\frac{2n}{\delta^{2}}\log\Delta_{\lambda-1}+2\sum_{h=1}^% {\lambda-1}\frac{n}{\Delta_{h}}\log\Delta_{h-1}=O((n/\delta)\log\delta).

Our previous algorithm (as described in Section 3.3) can be applied to determine $\operatorname{PA}[i]$ with the same time complexity. However, the topologies of suffix tree and prefix tree still takes $O(n)$ bits. We replace them with the topologies of the sparse prefix tree (SPT) and sparse suffix tree (SST), which require less space. Additionally, we maintain the small space structure in Lemma 13 supporting $\operatorname{LCE}$ queries.

Replacing Prefix Tree with Sparse Prefix Tree (SPT)

We sample a subset of $O(n/\delta)$ nodes in the prefix tree as follows:

1.

leaves $\ell_{k}$ , where $k$ is a multiple of $\delta$ ;
2.

the lowest common ancestor (LCA) of every pair of consecutive leaves sampled in step 1;
3.

the leftmost and rightmost descendant leaves of sampled nodes obtained in step 2.

Let $\mathcal{L}$ be the set of sampled leaves obtained after the above procedure. Then, the SPT is the compacted trie built from the reverse of circular prefixes corresponding only to the leaves in $\mathcal{L}$ – that is, a sparse prefix tree. We maintain its topology in succinct space and a bit string $B[1\mathinner{.\,.\allowbreak}n]$ , where $B[k]=1$ iff $\ell_{k}\in\mathcal{L}$ , as an indexible dictionary. The space required is $O((n/\delta)\log\delta)$ bits as there are $\mathcal{O}(\frac{n}{\delta})$ 1’s in $B$ . We now present some useful results.

Lemma 14.

Given two sampled leaves $\ell_{k},\ell_{k^{\prime}}$ in the prefix tree, the size of their $\operatorname{LCA}$ can be returned in $O(1)$ time using SPT and the associated bit string.

Proof.

The sampled leaf $\ell_{k}$ (resp., $\ell_{k^{\prime}}$ ) in the prefix tree corresponds to the leaf $\ell_{\mathsf{rank}_{B}(k,1)}$ (resp., $\ell_{\mathsf{rank}_{B}(k^{\prime},1)}$ ) in SPT. Therefore, find the range $[s,e]$ of leaves in the subtree of the node $\operatorname{LCA}(\ell_{\mathsf{rank}_{B}(k,1)},\ell_{\mathsf{rank}_{B}(k^{% \prime},1)})$ in SPT and return $\mathsf{select}_{B}(e,1)-\mathsf{select}_{B}(s,1)+1$ . $\hfill\blacktriangleleft$

The prefix tree topology play the following role in our earlier algorithm. Given $i$ , (i) find which among the nodes $u^{\prime}=\operatorname{LCA}(\ell_{i^{\prime}_{f-1}},\ell_{i})$ and $u^{\prime\prime}=\operatorname{LCA}(\ell_{i},\ell_{i^{\prime\prime}_{f-1}})$ is lower (call it $u$ ) to decide which case to use in the decoding procedure and (ii) return the range of leaves $[a,b]$ of $u$ (note that we don’t require the pre-order rank of $u$ ). Since $i,i^{\prime}_{f-1},i^{\prime\prime}_{f-1}$ are all divisible by $\delta$ (hence sampled) in the case of Type-A queries, we can apply Lemma 14 and find the range of leaves of $u^{\prime}$ and $u^{\prime\prime}$ first, then infer $u=u^{\prime}$ iff the range of $u^{\prime}$ is the same or contained within the range of $u^{\prime\prime}$ . The subsequent steps in the recurrence also work since both $i^{\prime}_{h}$ and $i^{\prime\prime}_{h}$ are divisible by $\delta$ for all $h\leq f$ . In summary, a sparse prefix tree topology can perform the required functionalities in our algorithm without any performance slowdown.

Replacing Suffix Tree with Sparse Suffix Tree (SST)

The SST is the compacted trie constructed from the circular suffixes corresponding to the leaves $\ell_{k}$ of the suffix tree, where $k$ is a multiple of $\delta$ . We maintain its topology in succinct space, requiring $O(n/\delta)$ bits.

The suffix tree topology serves the purpose of finding the suffix range $[\mathsf{sp}(\overleftarrow{Q}),\mathsf{ep}(\overleftarrow{Q})]$ of $\overleftarrow{Q}$ in $O(\log n)$ time, given (i) the length of $Q$ (this can be computed using $\operatorname{pLCS}_{\pi}$ as in Section 3.3), (ii) a leaf $\ell_{g}$ in the suffix tree, where $\overleftarrow{Q}$ is a prefix of $\mathrm{str}(\ell_{g})$ , (iii) the size of the suffix range of $Q$ , i.e., $\mathsf{ep}(\overleftarrow{Q})-\mathsf{sp}(\overleftarrow{Q})+1$ (specifically, $\mathsf{size}(u)$ is given, where $u$ is a node in the prefix tree). It is worth noting that this task can be accomplished without the suffix tree topology, and even without the third input parameter. We can exploit the fact that $\operatorname{LCE}(\operatorname{SA}[g],\operatorname{SA}[p])\geq|Q|$ if and only if $p\in[\mathsf{sp}(\overleftarrow{Q}),\mathsf{ep}(\overleftarrow{Q})]$ , and hence we can apply binary search on $p$ and determine the answer using $O(\log n)$ $\operatorname{LCE}$ queries.

We speed up this process by using the additional information in (iii) as follows. If $\mathsf{size}(u)\leq 2\delta$ , we still apply the binary search. The number of $\operatorname{LCE}/\operatorname{SA}$ queries required is $O(\log\delta)$ . Otherwise, find an approximate range using SST first, and then apply binary search on ranges of size $O(\delta)$ as follows.

1.

Find a value $g^{*}$ closer to $g$ , such that $g^{*}$ is a multiple of $\delta$ (thus $\ell_{g^{*}}$ is sampled) and $\mathrm{str}(\ell_{g^{*}})$ is also prefixed by $\overleftarrow{Q}$ as follows. Let $g^{\prime}=\delta\lfloor g/\delta\rfloor$ and $g^{\prime\prime}=\delta\lceil g/\delta\rceil$ . We fix $g^{*}=g^{\prime}$ if $\operatorname{LCE}(\operatorname{SA}[g],\operatorname{SA}[g^{\prime}])\geq|Q|$ , otherwise $g^{*}=g^{\prime\prime}$ (in this case $\operatorname{LCE}(\operatorname{SA}[g],\operatorname{SA}[g^{\prime\prime}])% \geq|Q|$ is guaranteed as $\mathsf{size}(u)>2\delta$ ).
2.

Find $(g^{*}/\delta)$ -th leaf in SST, and return the range $[sp^{*},ep^{*}]$ of leaves of its lowest ancestor with $\mathsf{size}(\cdot)\geq\lfloor\mathsf{size}(u)/\delta\rfloor-1$ . This step takes only $O(\log n)$ time (via $\mathsf{level\_ancestor}$ queries as before, but on SST). Observe that our sampling scheme guarantees $\mathsf{sp}(\overleftarrow{Q})\in[\delta\cdot sp^{*}-O(\delta),\delta\cdot sp^% {*}]$ and $\mathsf{ep}(\overleftarrow{Q})\in[\delta\cdot ep^{*},\delta\cdot ep^{*}+O(% \delta)]$ . Therefore we can now restrict our binary search into a smaller range of size $O(\delta)$ , requiring only $O(\log\delta)$ $\operatorname{LCE}$ and $\operatorname{SA}$ queries.

This subroutine for finding suffix range $[\mathsf{sp}(\overleftarrow{Q}),\mathsf{ep}(\overleftarrow{Q})]$ of $\overleftarrow{Q}$ takes $O(\log n+(t_{sa}+t_{\operatorname{LCE}})\cdot\log\delta)\in O(\log n+(\delta% \cdot t_{wt}+t_{sa})\delta\cdot\log\delta)$ time. After that, we continue with steps (b), (c), and (d) as in Section 3.3.

Figure 2: Illustration of Type-B queries.

By substituting the space–time complexities of the components, incorporating updated data structures, we obtain the following bound for Type-A queries.

Lemma 15 (Type-A Queries).

By maintaining auxiliary structures of space $O((n/\delta)\log\delta)$ bits in total, we can answer Type-A queries in time

O\left((\log n+t_{quantile}+(\delta\cdot t_{wt}+t_{sa})\delta\cdot\log\delta)% \log^{*}n\right).

4.2.3 Handling Type-B Queries

Type-B queries require a more involved solution than Type-A queries. Maintain the structure in Lemma 11 supporting $\operatorname{pLCS}^{\approx}_{\pi}$ queries, for values of $\pi$ in $\{-1,+1\}$ . Also associate $O(\log\delta)$ bits of satellite information (to be defined shortly) with each integer in $[1,n]$ that is a multiple of $\delta$ . The total space is $O((n/\delta)\log\delta)$ bits.

To retrieve $\operatorname{PA}[i]$ , where $i$ is not divisible by $\delta$ , we employ a procedure that decodes a segment of $\operatorname{PA}$ containing $\operatorname{PA}[i]$ . Let $i^{\prime}=\delta\lfloor i/\delta\rfloor$ , $i^{\prime\prime}=\delta\lceil i/\delta\rceil=i^{\prime}+\delta$ , and $u=\operatorname{LCA}(\ell_{i^{\prime}},\ell_{i^{\prime\prime}})$ . We now proceed to define some nodes in the prefix tree as illustrated in Figure 2.

$\blacksquare$

$x_{1},x_{2},\dots,x_{d}$ are nodes that lie on the path from $\ell_{i^{\prime}}$ to $u$ (excluding endpoints), ordered in descending $0pt(\cdot)$ , such that $x_{0}=\ell_{i^{\prime}}$ and $x_{k}$ for $k\in[1,d]$ is the lowest ancestor of $x_{k-1}$ whose child on the path to $\ell_{i^{\prime}}$ has a right sibling. Let $[\cdot,b_{k}]$ denote the range of leaves of $x_{k}$ for $k\in[0,d]$ . Therefore, $(i^{\prime},b_{d}]$ denotes the range of leaves after $i^{\prime}$ , such that the $\operatorname{LCA}$ of any of those leaves with $\ell_{i^{\prime}}$ is a node in $\{x_{1},x_{2},\dots,x_{d}\}$ . The following observation allows us to jump from node $x_{k-1}$ to node $x_{k}$ for all $k\in[1,d]$ .

Observation 16.

For all $k\in[1,d]$ we have $\operatorname{LCA}(\ell_{b_{k-1}},\ell_{b_{k-1}+1})=x_{k}$ ; therefore $\mathrm{strlen}(x_{k})=\operatorname{pLCS}_{+1}[\operatorname{PA}[b_{k-1}]]$ .

$\blacksquare$

$y_{1},y_{2},\dots,y_{f}$ are nodes that lie on the path from $\ell_{i^{\prime\prime}}$ to $u$ (excluding endpoints), ordered by descending $0pt(\cdot)$ , such that $y_{0}=\ell_{i^{\prime\prime}}$ and $y_{k}$ for $k\in[1,f]$ is the lowest ancestor of $y_{k-1}$ whose child on the path to $\ell_{i^{\prime\prime}}$ has a left sibling. Let $[a_{k},\cdot]$ denote the range of leaves of $y_{k}$ for $k\in[0,f]$ . Therefore, $[a_{f},i^{\prime\prime})$ denotes the range of leaves before $i^{\prime\prime}$ , such that the $\operatorname{LCA}$ of any of those leaves with $\ell_{i^{\prime\prime}}$ belongs to $\{y_{1},y_{2},\dots,y_{f}\}$ . The following observation allows us to jump from node $y_{k-1}$ to node $y_{k}$ for all $k\in[1,f]$ .

Observation 17.

For all $k\in[1,f]$ , we have $\operatorname{LCA}(\ell_{a_{k-1}},\ell_{a_{k-1}-1})=y_{k}$ ; therefore $\mathrm{strlen}(y_{k})=\operatorname{pLCS}_{-1}[\operatorname{PA}[a_{k-1}]]$ .

Our procedure for decoding $\operatorname{PA}[i]$ depends on which of the intervals $(i^{\prime},b_{d}],[b_{d}+1,a_{f}-1]$ , or $[a_{f},i^{\prime\prime})$ contains $i$ . The satellite information associated with $i^{\prime}$ is $(d,f,b_{d}-i^{\prime},a_{f}-i^{\prime})$ (all four values are bounded by $\delta$ ), which helps to decide the case.

CASE $i\in(b_{0},b_{d}]$

First obtain $\operatorname{PA}[i^{\prime}]$ using a Type-A query, then initialize $b_{0}=i^{\prime}$ and $\mathrm{strlen}(x_{0})=\operatorname{PA}[b_{0}]$ , the length of the prefix ending at $b_{0}$ . Then decode $\operatorname{PA}(b_{0},b_{d}]$ in $d$ steps; at step $k\in[1,d]$ , we compute $\mathrm{strlen}(x_{k}),\mathsf{size}(x_{k}),b_{k}$ and $\operatorname{PA}(b_{k-1},b_{k}]$ . Note that $(b_{0},b_{d}]=(b_{0},b_{1}]\cup(b_{1},b_{2}]\cup\dots(b_{d-1},b_{d}]$ . Let $Q_{t}$ be the prefix of $\mathrm{str}(\ell_{i^{\prime}})$ of length $t$ and $\alpha_{t}$ be the $(t+1)$ -th character of $\mathrm{str}(\ell_{i^{\prime}})$ . Therefore, $\overleftarrow{Q_{t}}=\mathsf{T}[\operatorname{PA}[i^{\prime}]-t+1\mathinner{.% \,.\allowbreak}\operatorname{PA}[i^{\prime}]]$ and $\alpha_{t}=\mathsf{T}[\operatorname{PA}[i^{\prime}]-t]$ . When $t=\mathrm{strlen}(x_{k})$ , we let $Q=Q_{t}$ and $\alpha=\alpha_{t}$ .

1.

Finding $\mathrm{strlen}(x_{k})$ : Observe that $\mathrm{strlen}(x_{k})$ is the largest $t<\mathrm{strlen}(x_{k-1})$ such that $\operatorname{BWT}[\mathsf{sp}(\overleftarrow{Q_{t}}),\mathsf{ep}(% \overleftarrow{Q_{t}})]$ contains a character $\beta_{t}>\alpha_{t}$ . However, finding $[\mathsf{sp}(\overleftarrow{Q_{t}}),\mathsf{ep}(\overleftarrow{Q_{t}})]$ can be expensive. Thankfully, we have an alternative procedure to verify this condition for a given $t$ . Find $z=\operatorname{ISA}[\operatorname{PA}[i^{\prime}]-t+1]$ , which is an entry in $[\mathsf{sp}(\overleftarrow{Q_{t}}),\mathsf{ep}(\overleftarrow{Q_{t}})]$ , then find the largest number $z^{\prime}$ before $z$ , and the smallest number $z^{\prime\prime}$ after $z$ , such that $\operatorname{BWT}[z^{\prime}],\operatorname{BWT}[z^{\prime\prime}]>\alpha_{t}% =\operatorname{BWT}[z]$ , using wavelet tree queries. The condition is satisfied if and only if $\operatorname{LCE}(\operatorname{ISA}[z],\operatorname{ISA}[z^{\prime}])\geq t$ or $\operatorname{LCE}(\operatorname{ISA}[z],\operatorname{ISA}[z^{\prime\prime}])\geq t$ . We next determine an $l$ such that $\mathrm{strlen}(x_{k})\in[l-\delta,l]$ , meaning we only need to iterate over the values of $t$ in $[l-\delta,l]$ for finding $\mathrm{strlen}(x_{k})$ . To find $l$ , we rely on observation 16 that $x_{k}=\operatorname{LCA}(\ell_{b_{k-1}},\ell_{b_{k-1}+1})$ and $\mathrm{strlen}(x_{k})=\operatorname{pLCS}[\operatorname{PA}[b_{k-1}]]$ . Therefore, $\operatorname{pLCS}_{1}^{\approx}[\operatorname{PA}[b_{k-1}]]\leq\mathrm{% strlen}(x_{k})\leq\operatorname{pLCS}_{1}^{\approx}[\operatorname{PA}[b_{k-1}]% ]+\delta$ , and we compute $\operatorname{pLCS}_{1}^{\approx}[\operatorname{PA}[b_{k-1}]]$ in $O(\log\delta)$ time (see Lemma 11), and set $l=\min\{\mathrm{strlen}(x_{k-1})-1,\operatorname{pLCS}_{1}^{\approx}[% \operatorname{PA}[b_{k-1}]]+\delta\}$ . The total time is $O((t_{wt}+t_{sa}+t_{\operatorname{LCE}})\delta)\subseteq O(t_{\operatorname{% LCE}}\cdot\delta)$ .
2.

Finding $\mathsf{size}(x_{k})$ : At first, we find an approximation $\mathsf{size}^{\approx}(x_{k})\in[\mathsf{size}(x_{k})-2\delta,\mathsf{size}(x% _{k})]$ using SPT and the associated bit vector $B$ as follows. Note that $x_{k}=\operatorname{LCA}(\ell_{i^{\prime}},\ell_{b_{k-1}+1})$ and the leaf $\ell_{i^{\prime}}$ is sampled (recall SPT’s construction). Therefore, if $\ell_{b_{k-1}+1}$ is also sampled (i.e., $B[b_{k-1}+1]=1)$ , then we can find the exact value of $\mathsf{size}(x_{k})$ in $O(1)$ time using Lemma 14. Otherwise, find the leaves $\ell_{\mathsf{rank}_{B}(b_{k-1}+1,1)},\ell_{\mathsf{rank}_{B}(b_{k-1}+1,1)+1}$ in SPT, the child of their LCA on the path to $\ell_{\mathsf{rank}_{B}(i^{\prime},1)}$ , and the range $[s,s^{\prime}]$ of leaves of that child. Then return $\mathsf{select}_{B}(s^{\prime},1)-\mathsf{select}(s,1)+1$ as $\mathsf{size}^{\approx}(x_{k})$ . Our sampling scheme guarantees that the value returned lies in the range $[\mathsf{size}(x_{k})-2\delta,\mathsf{size}(x_{k})]$ . The time complexity is $O(1)$ . We now proceed to computing the exact value of $\mathsf{size}(x_{k})$ . Since $Q=\mathrm{str}(x_{k})$ , we have $\mathsf{size}(x_{k})=\mathsf{ep}(\overleftarrow{Q})-\mathsf{sp}(\overleftarrow% {Q})+1$ . Therefore we compute the range $[\mathsf{sp}(\overleftarrow{Q}),\mathsf{ep}(\overleftarrow{Q})]$ as follows. To begin with, we know an entry $\operatorname{ISA}[\operatorname{PA}[i^{\prime}]-|Q|+1]\in[\mathsf{sp}(% \overleftarrow{Q}),\mathsf{ep}(\overleftarrow{Q})]$ , as well as $\mathsf{size}^{\approx}(x_{k})$ . At the point, we can follow the same procedure detailed in Section 4.2.2, where we first identify an approximate range that is sufficiently close to the actual one using sparse suffix tree in $O(\log n)$ time, then perform a binary search requiring only $O(\log\delta)$ LCE and ISA queries. The time required is $O(\log n+(t_{sa}+t_{\operatorname{LCE}})\cdot\log\delta)\subseteq O(\log n+t_{% \operatorname{LCE}}\cdot\log\delta)$ .
3.

Finding $b_{k}$ : Let $\alpha$ be the leading character on the path from $x_{k}$ to its child on the path to $\ell_{i^{\prime}}$ . Count the entries in $\operatorname{BWT}[\mathsf{sp}(\overleftarrow{Q}),\mathsf{ep}(\overleftarrow{Q% })]$ that are above $\alpha=\mathsf{T}[\operatorname{PA}[i^{\prime}]-|Q|]$ (using a wavelet tree query). This gives the number of leaves in the range $(b_{k-1},b_{k}]$ . Therefore we simply add $b_{k-1}$ with this count and return as $b_{k}$ . Time required is $O(t_{wt})$ .
4.
Finding $\operatorname{PA}(b_{k-1},b_{k}]$ : The set $\mathcal{P}=\{\operatorname{SA}[z]+|Q|-1\mid z\in[\mathsf{sp}(\overleftarrow{Q% }),\mathsf{ep}(\overleftarrow{Q})],\operatorname{BWT}[z]>\alpha\}$ is a collection of elements in $\operatorname{PA}(b_{k-1},b_{k}]$ , which can be obtained in $O(t_{wt}+t_{sa})$ time per element using wavelet tree and $\operatorname{SA}[\cdot]$ queries. However, we do not know the order in which they appear in $\operatorname{PA}(b_{k-1},b_{k}]$ ; therefore our next goal is to recover $\operatorname{PA}(b_{k-1},b_{k}]$ by sorting the elements in $\mathcal{P}$ in the ascending order of their $\operatorname{IPA}[\cdot]$ values. We first present a simple solution, and then describe a slightly improved one.
1. (a)
  
  A simple solution using $\overleftarrow{\operatorname{LCE}}(\cdot,\cdot)$ queries: By fixing $D=\delta\log n$ , we maintain the structure in Lemma 4 without changing the asymptotic space complexity, which supports $\overleftarrow{\operatorname{LCE}}(\cdot,\cdot)$ queries in $O(t_{\operatorname{LCE}}\cdot\log(\delta\log n))$ time. Then, for any $p,q\in\mathcal{P}$ , we can decide the relative order of $\operatorname{IPA}[p]$ and $\operatorname{IPA}[q]$ by comparing the characters $\mathsf{T}[p-\overleftarrow{\operatorname{LCE}}(p,q)]$ and $\mathsf{T}[q-\overleftarrow{\operatorname{LCE}}(p,q)]$ . Therefore, an efficient comparison-based sorting algorithm (such as merge sort) can be used to sort the elements of $\mathcal{P}$ in ascending order of their $\operatorname{IPA}[\cdot]$ values using $O((b_{k}-b_{k-1})\log(b_{k}-b_{k-1}))$ number of $\overleftarrow{\operatorname{LCE}}(\cdot,\cdot)$ queries. The resulting time complexity for this step is
  
  $(b_{k}-b_{k-1})\log(b_{k}-b_{k-1})\cdot t_{\operatorname{LCE}}\cdot(\log(% \delta\log n)\subseteq O((b_{k}-b_{k-1})\log\delta\cdot t_{\operatorname{LCE}}% \cdot(\log\delta+\log\log n)).$
2. (b)
  
  An alternative solution: Our goal here is to avoid the direct use of $\overleftarrow{\operatorname{LCE}}(\cdot,\cdot)$ queries, and thereby removing the $\log\log n$ term in the previous time complexity. To achieve this, we reconstruct the subtree rooted at $x_{k}$ on the fly. For any node $w$ in the subtree rooted at $x_{k}$ , let $\mathcal{P}(w)\subseteq\mathcal{P}$ denotes the set of $\operatorname{PA}[\cdot]$ values corresponding to the leaves in the subtree of $w$ . Iterating over $p\in\mathcal{P}$ , our algorithm return the sets $\mathcal{P}(w_{1}),\mathcal{P}(w_{2}),\dots$ , in that order, where nodes $w_{1},w_{2},\dots$ are the children (in the left to right order) of node $w=\operatorname{LCA}(\ell_{\operatorname{IPA}[p]},\ell_{\operatorname{IPA}[p]+% 1})$ . Note that the preorder rank of $w$ is not known even after processing $p$ . Therefore, based on $\mathcal{P}(w)$ , we assign to $w$ a unique label, defined as the ordered pair consisting of the size of $\mathcal{P}(w)$ and the smallest element of $\mathcal{P}(w)$ . With this labeling and parent–child information for all internal nodes, we can easily reconstruct the tree in a top-down fashion and recover $\operatorname{PA}(b_{k-1},b_{k}]$ . We now present the details of processing a specific $p\in\mathcal{P}$ . The first step is to compute $\mathrm{strlen}(w)=\operatorname{pLCS}[p]$ , which is given by the expression below when $p\neq\operatorname{PA}[b_{k}]$ (in that case $\operatorname{PA}[\operatorname{IPA}[p]+1]\in\mathcal{P}$ ); when $p=\operatorname{PA}[b_{k}]$ , it will not return any value.
  
  $\max\{\overleftarrow{\operatorname{LCE}}(p,q)\mid q\in\mathcal{P}\backslash\{p% \},\overleftarrow{T[1\mathinner{.\,.\allowbreak}q]}\texttt{ comes after }% \overleftarrow{T[1\mathinner{.\,.\allowbreak}p]}\texttt{ lexicographically}\}$
  Instead of evaluating this expression by applying $\overleftarrow{\operatorname{LCE}}(\cdot,\cdot)$ directly, we compute $L=\operatorname{pLCS}^{\approx}[p]$ in $O(\log\delta)$ time (see Lemma 11), where $\operatorname{pLCS}[p]-\delta\leq L\leq\operatorname{pLCS}[p]$ . Then, iterate over $q\in\mathcal{P}$ , compute $\operatorname{LCE}(p-L+1,q-L+1)$ , and consider the following two cases:
  1. i.
    
    If $\operatorname{LCE}(p-L+1,q-L+1)<L$ , then we know $\overleftarrow{\operatorname{LCE}}(p,q)<L\leq\mathrm{strlen}(w)$ . Therefore discard $q$ .
  2. ii.
    
    Otherwise we have $\overleftarrow{\operatorname{LCE}}(p,q)=L+\overleftarrow{\operatorname{LCE}}(p% -L,q-L)$ . In that case, extract the substrings $\mathsf{T}[p-L-\delta\mathinner{.\,.\allowbreak}p-L]$ and $\mathsf{T}[q-L-\delta\mathinner{.\,.\allowbreak}q-L]$ and compare them. If the substrings differ, we can compute $\overleftarrow{\operatorname{LCE}}(p-L,q-L)$ (thus compute $\overleftarrow{\operatorname{LCE}}(p,q)$ ) and determine their lexicographic order (and thus the lexicographic order of $\overleftarrow{T[1\mathinner{.\,.\allowbreak}q]}$ and $\overleftarrow{T[1\mathinner{.\,.\allowbreak}p]}$ ). If the substrings match, we infer that $\overleftarrow{\operatorname{LCE}}(p,q)>L+\delta\geq\mathrm{strlen}(w)$ , and therefore both $\ell_{\operatorname{IPA}[q]}$ and $\ell_{\operatorname{IPA}[p]}$ lie in the subtree of the same child of $w$ , and $\overleftarrow{T[1\mathinner{.\,.\allowbreak}q]}$ comes before $\overleftarrow{T[1\mathinner{.\,.\allowbreak}p]}$ in lexicographically.
  The above step for a specific $p, q$ takes $O(t_{\operatorname{LCE}}+t_{sa}+\delta\cdot t_{wt})$ time. By taking the maximum value of $\overleftarrow{\operatorname{LCE}(p,q)}$ over all $q$ that satisfy the required condition on the lexicographic order, we obtain $\mathrm{strlen}(w)$ . We next collect all positions $q$ such that $\overleftarrow{\operatorname{LCE}}(p,q)\geq\mathrm{strlen}(w)$ , group them into sets according to the character $T[q-\mathrm{strlen}(w)]$ , and output these sets in order of increasing character value they correspond to. It is straightforward to verify that the sets produced in this manner are exactly $\mathcal{P}(w_{1}),\mathcal{P}(w_{2}),\dots$ . Moreover, every internal node in the subtree rooted at $x_{k}$ will be processed after we have iterated over all $p\in\mathcal{P}\backslash\{\operatorname{PA}[b_{k}]\}$ . The overall time complexity of this step is $O((b_{k}-b_{k-1})^{2}\cdot(t_{\operatorname{LCE}}+t_{sa}+\delta\cdot t_{wt}))% \subseteq O((b_{k}-b_{k-1})^{2}\cdot t_{\operatorname{LCE}})$ .
We use the second method, although its time complexity is quadratic in the size of the tree, because the first method would add extra $\log\log n$ factors to the time complexity.

The combined time for all 4 steps for all $k\in[1,d]$ , where $d\leq\delta$ is bounded as follows:

\sum_{k=1}^{d}\Big(t_{\operatorname{LCE}}\cdot\delta+(\log n+t_{\operatorname{% LCE}}\cdot\log\delta)+t_{wt}+(b_{k}-b_{k-1})^{2}\cdot t_{\operatorname{LCE}}\Big)

\leq t_{\operatorname{LCE}}\cdot\delta^{2}+(\log n+t_{\operatorname{LCE}}\cdot% \log\delta)\cdot\delta+t_{wt}\cdot\delta+(b_{d}-b_{0})^{2}\cdot t_{% \operatorname{LCE}}

By substituting $b_{d}-b_{0}=O(\delta)$ and $t_{\operatorname{LCE}}=O((t_{sa}+\delta\cdot t_{wt})\delta)$ , the expression simplifies to $O(\delta\cdot\log n+(t_{sa}+\delta\cdot t_{wt})\delta^{3}).$

CASE $i\in[b_{d}+1,a_{f}-1]$

Let $Q=\mathrm{str}(u)$ and $\alpha$ be the leading character on the path from $u$ to its child on the path to $\ell_{i^{\prime}}$ and $\beta$ be the leading character on the path from $u$ to its child on the path to $\ell_{i^{\prime\prime}}$ . Then the set $\mathcal{P}=\{\operatorname{SA}[z]+|Q|-1\mid z\in[\mathsf{sp}(\overleftarrow{Q% }),\mathsf{ep}(\overleftarrow{Q})],\operatorname{BWT}[z]\in[\alpha+1,\beta-1]\}$ is the collection of elements in $\operatorname{PA}[b_{d}+1,a_{f}-1]$ . Since $\mathsf{size}(u)$ , $\mathrm{strlen}(u),\operatorname{PA}[i^{\prime}],\operatorname{PA}[i^{\prime% \prime}]$ are readily available (via Type-A query), the elements in the set $\mathcal{P}$ can be easily extracted in time $O(t_{wt}+t_{sa})$ per element, but not in the order as they appear in $\operatorname{PA}$ . Finally, to recover $\operatorname{PA}[b_{d}+1,a_{f}-1]$ , we follow the same procedure as in the first case. The resulting time is $O((t_{sa}+\delta\cdot t_{wt})\delta^{3})$ .

CASE $i\in[a_{f},i^{\prime\prime})$

Here we obtain $\operatorname{PA}[i^{\prime\prime}]$ first using a Type-A query, then initialize $a_{0}=i^{\prime\prime}$ and $\mathrm{strlen}(y_{0})=\operatorname{PA}[a_{0}]$ , the length of the prefix ending at $a_{0}$ . Then decode $\operatorname{PA}[a_{f},a_{0})$ in $f$ steps, where at step $k\in[1,f]$ , we compute $\mathrm{strlen}(y_{k})$ , $\mathsf{size}(y_{k})$ , $a_{k}$ and $\operatorname{PA}[a_{k},a_{k-1})$ . Note that $[a_{f},a_{0})=[a_{f},a_{f-1})\cup\dots\cup[a_{2},a_{1})\cup[a_{1},a_{0})$ . Suppose $Q=\mathrm{str}(y_{k})$ and $\beta=\mathsf{T}[\operatorname{PA}[i^{\prime\prime}]-|Q|]$ , then the set elements in $\operatorname{PA}[a_{k},a_{k-1})$ is given by $\mathcal{P}=\{\operatorname{SA}[z]+|Q|-1\mid z\in[\mathsf{sp}(\overleftarrow{Q% }),\mathsf{ep}(\overleftarrow{Q})],\operatorname{BWT}[z]<\beta\}$ . This is analogous to that of the first case, therefore we invoke a symmetric procedure to handle this case. In contrast to the first case, where we rely on Observation 16 and use $\operatorname{pLCS}_{1}^{\approx}[\cdot]$ queries, here we rely on Observation 17 and use $\operatorname{pLCS}_{-1}^{\approx}[\cdot]$ queries. Total time is $O(\delta\cdot\log n+(t_{sa}+\delta\cdot t_{wt})\delta^{3})$ time (similar to the first case).

Lemma 18 (Type-B Queries).

The combined space of all auxiliary structures for Type-B queries is $O((n/\delta)\log\delta)$ bits and the query time is $O\left(\delta\cdot\log n+(\delta\cdot t_{wt}+t_{sa})\delta^{3}\right)$ .

By combining Lemma 15 and Lemma 18, we obtain the Theorem below.

Theorem 19.

Let the Burrows-Wheeler Transform (BWT) of a text $\mathsf{T}[1\mathinner{.\,.\allowbreak}n]$ be maintained in a data structure that supports basic queries ( $\mathsf{rank}$ , $\mathsf{select}$ , and $\mathsf{access}$ ) in $t_{wt}$ time, and range quantile queries in $t_{quantile}$ time. Then, for any parameter $\tau\geq 1$ , we can maintain a sampled subset of $n/\tau$ suffix array values using $O((n/\tau)\log n)$ bits of additional space, and support suffix array (SA) and inverse suffix array (ISA) queries in time $t_{sa}=O(\tau\cdot t_{wt})$ . By maintaining an auxiliary structure of space $O((n/\delta)\log\delta)$ bits for a parameter $\delta$ , we can support prefix array (PA) queries in time

t_{pa}=O\left((\log n\cdot(\log^{*}n+\delta)+t_{quantile}\cdot\log^{*}n+(% \delta+\tau)\cdot t_{wt}\cdot(\delta\log\delta\log^{*}n+\delta^{3})\right)

\subseteq O((\log n+t_{quantile}+(\delta+\tau)\cdot t_{wt})\cdot(\delta\log% \delta\log^{*}n+\delta^{3})).

Additionally we can support $\operatorname{LCE}(\cdot,\cdot)$ queries in time $t_{\operatorname{LCE}}=O((\delta\cdot t_{wt}+t_{sa})\delta)$ and $\overleftarrow{\operatorname{LCE}}(\cdot,\cdot)$ queries in time $O(t_{\operatorname{LCE}}\cdot(\log\delta+\log\log n))$ .

By employing the multiary wavelet tree, where $t_{wt}=O(1+\log\sigma/\log\log n)$ , $t_{quantile}=O(\log\sigma)$ and setting $\delta=\kappa\log\kappa$ and $\tau=\kappa\log n$ , we obtain the following result.

Corollary 20.

Let $\mathsf{T}[1\mathinner{.\,.\allowbreak}n]$ be a text over an alphabet of size $\sigma$ . We can maintain its Burrows-Wheeler Transform (BWT) as a wavelet tree data structure in $n\log\sigma+o(n)+O(\sigma\log n)$ bits that supports basic queries (rank, select, access) in time $O(1+\log\sigma/\log\log n)$ and range quantile queries in time $O(\log\sigma)$ . For an integer parameter $\kappa$ , we can maintain an auxiliary structure of space $O(n/\kappa)$ bits and support suffix array (SA) and inverse suffix array (ISA) queries in time $t_{sa}=O((1+\log\sigma/\log\log n)\cdot\kappa\log n)$ , and prefix array (PA) queries in time $t_{pa}=t_{sa}\cdot O((\kappa^{3}\log\kappa+\kappa\log^{*}n)\cdot\log^{2}\kappa)$ .

Additionally we can support $\operatorname{LCE}(\cdot,\cdot)$ queries in time $t_{\operatorname{LCE}}=O(t_{sa}\cdot\kappa\log\kappa)$ and $\overleftarrow{\operatorname{LCE}}(\cdot,\cdot)$ queries in time $O(t_{\operatorname{LCE}}\cdot(\log\kappa+\log\log n))$ .

5 A Note On Inverse Prefix Array (IPA) Queries

We present a simple approach for supporting $\operatorname{IPA}[\cdot]$ queries. Assuming the availability of data structures supporting $\operatorname{PA}[\cdot]$ and $\operatorname{LCE}(\cdot,\cdot)$ queries, we maintain the auxiliary structure from Lemma 4 with the parameter set to $D=\kappa\log n$ . This structure requires $O(n/\kappa)$ additional bits of space and supports $\overleftarrow{\operatorname{LCE}}(\cdot,\cdot)$ queries in $\overleftarrow{\operatorname{LCE}}(\cdot,\cdot)$ time $O(t_{\operatorname{LCE}}\cdot\log(\kappa\log n))$ .

Given a text position $j$ , we compute $\operatorname{IPA}[j]$ by performing a binary search over $i\in[1,n]$ . For a candidate index $i$ , we first compute $x=\operatorname{PA}[i]$ . If $x=j$ , we return $i$ and terminate the search. Otherwise, we compute $l=\overleftarrow{\operatorname{LCE}}(x,j)$ and compare the characters $\mathsf{T}[x-l]$ and $\mathsf{T}[j-l]$ (which must be different). If $\mathsf{T}[x-l]<\mathsf{T}[j-l]$ , then we conclude that $i<\operatorname{IPA}[j]$ ; otherwise, $i>\operatorname{IPA}[j]$ . This provides the necessary comparison predicate for binary search. The time complexity is $O((t_{pa}+t_{\operatorname{LCE}}\cdot\log(\kappa\log n))\log n)\subseteq O(t_{% pa}\cdot\log n\cdot\log\log n)$ .

Theorem 21.

With the structure described in Theorem 19, we can maintain an auxiliary data structure of space $O(n/\kappa)$ bits that supports inverse prefix array (IPA) queries in time $O(t_{pa}\cdot\log n\cdot\log\log n)$ .

6 Conclusions

We present a solution for encoding the suffix array and inverse suffix array of the reversed text, assuming the availability of the FM-index of the original text. We can answer suffix array queries on the reversed text in time close to that of suffix array queries on the original text. However, for inverse suffix array queries on the reversed text, we require roughly a factor of $(\log n)$ more time than for inverse suffix array queries on the original text. Narrowing this gap is an interesting problem, which we leave open for future research.

References

[1] Paniz Abedin, Oliver A. Chubet, Daniel Gibney, and Sharma V. Thankachan. Contextual pattern matching in less space. In Data Compression Conference, DCC 2023, Snowbird, UT, USA, March 21-24, 2023, pages 160–167. IEEE, 2023. doi:10.1109/DCC55655.2023.00024.
[2] Amihood Amir, Dmitry Keselman, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein, and Michael Rodeh. Text indexing and dictionary matching with one error. J. Algorithms, 37(2):309–325, 2000. doi:10.1006/JAGM.2000.1104.
[3] Djamal Belazzougui, Travis Gagie, Simon Gog, Giovanni Manzini, and Jouni Sirén. Relative fm-indexes. In String Processing and Information Retrieval: 21st International Symposium, SPIRE 2014, Ouro Preto, Brazil, October 20-22, 2014. Proceedings 21, pages 52–64. Springer, 2014. doi:10.1007/978-3-319-11918-2_6.
[4] Philip Bille, Inge Li Gørtz, Mathias Bæk Tejs Knudsen, Moshe Lewenstein, and Hjalte Wedel Vildhøj. Longest common extensions in sublinear space. In Ferdinando Cicalese, Ely Porat, and Ugo Vaccaro, editors, Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 - July 1, 2015, Proceedings, volume 9133 of Lecture Notes in Computer Science, pages 65–76. Springer, 2015. doi:10.1007/978-3-319-19929-0_6.
[5] Michael Burrows. A block-sorting lossless data compression algorithm. SRS Research Report, 124, 1994.
[6] Andrea Farruggia, Travis Gagie, Gonzalo Navarro, Simon J Puglisi, and Jouni Sirén. Relative suffix trees. The Computer Journal, 61(5):773–788, 2018. doi:10.1093/COMJNL/BXX108.
[7] Paolo Ferragina and Giovanni Manzini. Opportunistic data structures with applications. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pages 390–398. IEEE, 2000. doi:10.1109/SFCS.2000.892127.
[8] Paolo Ferragina, Giovanni Manzini, Veli Mäkinen, and Gonzalo Navarro. Compressed representations of sequences and full-text indexes. ACM Trans. Algorithms, 3(2):20, 2007. doi:10.1145/1240233.1240243.
[9] Johannes Fischer and Volker Heun. Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput., 40(2):465–492, 2011. doi:10.1137/090779759.
[10] Travis Gagie, Gonzalo Navarro, and Nicola Prezza. Fully functional suffix trees and optimal text searching in BWT-runs bounded space. J. ACM, 67(1):2:1–2:54, 2020. doi:10.1145/3375890.
[11] Travis Gagie, Simon J. Puglisi, and Andrew Turpin. Range quantile queries: Another virtue of wavelet trees. In String Processing and Information Retrieval (SPIRE), volume 5721 of Lecture Notes in Computer Science, pages 1–6. Springer, Berlin, Heidelberg, 2009. arXiv:0903.4726. doi:10.1007/978-3-642-03784-9_1.
[12] Arnab Ganguly, Daniel Gibney, Sahar Hooshmand, M. Oguzhan Külekci, and Sharma V. Thankachan. Fm-index reveals the reverse suffix array. In Inge Li Gørtz and Oren Weimann, editors, 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, Copenhagen, Denmark, June 17-19, 2020, volume 161 of LIPIcs, pages 13:1–13:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.CPM.2020.13.
[13] Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. High-order entropy-compressed text indexes. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 841–850. SIAM, 2003. URL: http://dl.acm.org/citation.cfm?id=644108.644250.
[14] Roberto Grossi and Jeffrey Scott Vitter. Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput., 35(2):378–407, 2005. doi:10.1137/S0097539702402354.
[15] Jesper Jansson, Kunihiko Sadakane, and Wing-Kin Sung. Ultra-succinct representation of ordered trees with applications. J. Comput. Syst. Sci., 78(2):619–631, 2012. doi:10.1016/J.JCSS.2011.09.002.
[16] Dominik Kempa and Tomasz Kociumaka. Collapsing the hierarchy of compressed data structures: Suffix arrays in optimal compressed space. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1877–1886. IEEE, 2023. doi:10.1109/FOCS57990.2023.00114.
[17] Tak Wah Lam, Ruiqiang Li, Alan Tam, Simon C. K. Wong, Edward Wu, and Siu-Ming Yiu. High throughput short read alignment via bi-directional BWT. In 2009 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2009, Washington, DC, USA, November 1-4, 2009, Proceedings, pages 31–36. IEEE Computer Society, 2009. doi:10.1109/BIBM.2009.42.
[18] Ben Langmead, Cole Trapnell, Mihai Pop, and Steven L. Salzberg. Ultrafast and memory-efficient alignment of short dna sequences to the human genome. Genome Biology, 10(3):R25, 2009.
[19] Moshe Lewenstein. Orthogonal range searching for text indexing. In Andrej Brodnik, Alejandro López-Ortiz, Venkatesh Raman, and Alfredo Viola, editors, Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, volume 8066 of Lecture Notes in Computer Science, pages 267–302. Springer, 2013. doi:10.1007/978-3-642-40273-9_18.
[20] Heng Li and Richard Durbin. Fast and accurate short read alignment with burrows-wheeler transform. Bioinformatics, 25(14):1754–1760, 2009. doi:10.1093/BIOINFORMATICS/BTP324.
[21] Udi Manber and Gene Myers. Suffix arrays: A new method for on-line string searches. SIAM Journal on Computing, 22(5):935–948, 1993. doi:10.1137/0222058.
[22] Edward M. McCreight. A space-economical suffix tree construction algorithm. Journal of the ACM, 23(2):262–272, 1976. doi:10.1145/321941.321946.
[23] J. Ian Munro and Venkatesh Raman. Succinct representation of balanced parentheses and static trees. SIAM J. Comput., 31(3):762–776, 2001. doi:10.1137/S0097539799364092.
[24] Gonzalo Navarro. Wavelet trees for all. J. Discrete Algorithms, 25:2–20, 2014. doi:10.1016/J.JDA.2013.07.004.
[25] Gonzalo Navarro. Contextual pattern matching. In International Symposium on String Processing and Information Retrieval, pages 3–10. Springer, 2020. doi:10.1007/978-3-030-59212-7_1.
[26] Gonzalo Navarro. Indexing highly repetitive string collections, part I: repetitiveness measures. ACM Comput. Surv., 54(2):29:1–29:31, 2022. doi:10.1145/3434399.
[27] Gonzalo Navarro. Indexing highly repetitive string collections, part II: compressed indexes. ACM Comput. Surv., 54(2):26:1–26:32, 2022. doi:10.1145/3432999.
[28] Mihai Pătraşcu. Succincter. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 305–313. IEEE Computer Society, 2008. doi:10.1109/FOCS.2008.83.
[29] Rajeev Raman, Venkatesh Raman, and Srinivasa Rao Satti. Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms, 3(4):43, 2007. doi:10.1145/1290672.1290680.
[30] Luís MS Russo, Gonzalo Navarro, and Arlindo L Oliveira. Fully-compressed suffix trees. In LATIN 2008: Theoretical Informatics: 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008. Proceedings 8, pages 362–373. Springer, 2008. doi:10.1007/978-3-540-78773-0_32.
[31] Kunihiko Sadakane. Compressed suffix trees with full functionality. Theory Comput. Syst., 41(4):589–607, 2007. doi:10.1007/S00224-006-1198-X.
[32] Dirk Strothmann. The affix array data structure and its applications to RNA secondary structure analysis. Theor. Comput. Sci., 389(1-2):278–294, 2007. doi:10.1016/J.TCS.2007.09.029.
[33] Esko Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249–260, 1995. doi:10.1007/BF01206331.
[34] Peter Weiner. Linear pattern matching algorithms. 14th Annual Symposium on Switching and Automata Theory, pages 1–11, 1973. doi:10.1109/SWAT.1973.13.

[bib.bib1] [1] Paniz Abedin, Oliver A. Chubet, Daniel Gibney, and Sharma V. Thankachan. Contextual pattern matching in less space. In Data Compression Conference, DCC 2023, Snowbird, UT, USA, March 21-24, 2023, pages 160–167. IEEE, 2023. doi:10.1109/DCC55655.2023.00024.

[bib.bib2] [2] Amihood Amir, Dmitry Keselman, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein, and Michael Rodeh. Text indexing and dictionary matching with one error. J. Algorithms, 37(2):309–325, 2000. doi:10.1006/JAGM.2000.1104.

[bib.bib3] [3] Djamal Belazzougui, Travis Gagie, Simon Gog, Giovanni Manzini, and Jouni Sirén. Relative fm-indexes. In String Processing and Information Retrieval: 21st International Symposium, SPIRE 2014, Ouro Preto, Brazil, October 20-22, 2014. Proceedings 21, pages 52–64. Springer, 2014. doi:10.1007/978-3-319-11918-2_6.

[bib.bib4] [4] Philip Bille, Inge Li Gørtz, Mathias Bæk Tejs Knudsen, Moshe Lewenstein, and Hjalte Wedel Vildhøj. Longest common extensions in sublinear space. In Ferdinando Cicalese, Ely Porat, and Ugo Vaccaro, editors, Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 - July 1, 2015, Proceedings, volume 9133 of Lecture Notes in Computer Science, pages 65–76. Springer, 2015. doi:10.1007/978-3-319-19929-0_6.

[bib.bib5] [5] Michael Burrows. A block-sorting lossless data compression algorithm. SRS Research Report, 124, 1994.

[bib.bib6] [6] Andrea Farruggia, Travis Gagie, Gonzalo Navarro, Simon J Puglisi, and Jouni Sirén. Relative suffix trees. The Computer Journal, 61(5):773–788, 2018. doi:10.1093/COMJNL/BXX108.

[bib.bib7] [7] Paolo Ferragina and Giovanni Manzini. Opportunistic data structures with applications. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pages 390–398. IEEE, 2000. doi:10.1109/SFCS.2000.892127.

[bib.bib8] [8] Paolo Ferragina, Giovanni Manzini, Veli Mäkinen, and Gonzalo Navarro. Compressed representations of sequences and full-text indexes. ACM Trans. Algorithms, 3(2):20, 2007. doi:10.1145/1240233.1240243.

[bib.bib9] [9] Johannes Fischer and Volker Heun. Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput., 40(2):465–492, 2011. doi:10.1137/090779759.

[bib.bib10] [10] Travis Gagie, Gonzalo Navarro, and Nicola Prezza. Fully functional suffix trees and optimal text searching in BWT-runs bounded space. J. ACM, 67(1):2:1–2:54, 2020. doi:10.1145/3375890.

[bib.bib11] [11] Travis Gagie, Simon J. Puglisi, and Andrew Turpin. Range quantile queries: Another virtue of wavelet trees. In String Processing and Information Retrieval (SPIRE), volume 5721 of Lecture Notes in Computer Science, pages 1–6. Springer, Berlin, Heidelberg, 2009. arXiv:0903.4726. doi:10.1007/978-3-642-03784-9_1.

[bib.bib12] [12] Arnab Ganguly, Daniel Gibney, Sahar Hooshmand, M. Oguzhan Külekci, and Sharma V. Thankachan. Fm-index reveals the reverse suffix array. In Inge Li Gørtz and Oren Weimann, editors, 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, Copenhagen, Denmark, June 17-19, 2020, volume 161 of LIPIcs, pages 13:1–13:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.CPM.2020.13.

[bib.bib13] [13] Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. High-order entropy-compressed text indexes. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 841–850. SIAM, 2003. URL: http://dl.acm.org/citation.cfm?id=644108.644250.

[bib.bib14] [14] Roberto Grossi and Jeffrey Scott Vitter. Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput., 35(2):378–407, 2005. doi:10.1137/S0097539702402354.

[bib.bib15] [15] Jesper Jansson, Kunihiko Sadakane, and Wing-Kin Sung. Ultra-succinct representation of ordered trees with applications. J. Comput. Syst. Sci., 78(2):619–631, 2012. doi:10.1016/J.JCSS.2011.09.002.

[bib.bib16] [16] Dominik Kempa and Tomasz Kociumaka. Collapsing the hierarchy of compressed data structures: Suffix arrays in optimal compressed space. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 1877–1886. IEEE, 2023. doi:10.1109/FOCS57990.2023.00114.

[bib.bib17] [17] Tak Wah Lam, Ruiqiang Li, Alan Tam, Simon C. K. Wong, Edward Wu, and Siu-Ming Yiu. High throughput short read alignment via bi-directional BWT. In 2009 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2009, Washington, DC, USA, November 1-4, 2009, Proceedings, pages 31–36. IEEE Computer Society, 2009. doi:10.1109/BIBM.2009.42.

[bib.bib18] [18] Ben Langmead, Cole Trapnell, Mihai Pop, and Steven L. Salzberg. Ultrafast and memory-efficient alignment of short dna sequences to the human genome. Genome Biology, 10(3):R25, 2009.

[bib.bib19] [19] Moshe Lewenstein. Orthogonal range searching for text indexing. In Andrej Brodnik, Alejandro López-Ortiz, Venkatesh Raman, and Alfredo Viola, editors, Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, volume 8066 of Lecture Notes in Computer Science, pages 267–302. Springer, 2013. doi:10.1007/978-3-642-40273-9_18.

[bib.bib20] [20] Heng Li and Richard Durbin. Fast and accurate short read alignment with burrows-wheeler transform. Bioinformatics, 25(14):1754–1760, 2009. doi:10.1093/BIOINFORMATICS/BTP324.

[bib.bib21] [21] Udi Manber and Gene Myers. Suffix arrays: A new method for on-line string searches. SIAM Journal on Computing, 22(5):935–948, 1993. doi:10.1137/0222058.

[bib.bib22] [22] Edward M. McCreight. A space-economical suffix tree construction algorithm. Journal of the ACM, 23(2):262–272, 1976. doi:10.1145/321941.321946.

[bib.bib23] [23] J. Ian Munro and Venkatesh Raman. Succinct representation of balanced parentheses and static trees. SIAM J. Comput., 31(3):762–776, 2001. doi:10.1137/S0097539799364092.

[bib.bib24] [24] Gonzalo Navarro. Wavelet trees for all. J. Discrete Algorithms, 25:2–20, 2014. doi:10.1016/J.JDA.2013.07.004.

[bib.bib25] [25] Gonzalo Navarro. Contextual pattern matching. In International Symposium on String Processing and Information Retrieval, pages 3–10. Springer, 2020. doi:10.1007/978-3-030-59212-7_1.

[bib.bib26] [26] Gonzalo Navarro. Indexing highly repetitive string collections, part I: repetitiveness measures. ACM Comput. Surv., 54(2):29:1–29:31, 2022. doi:10.1145/3434399.

[bib.bib27] [27] Gonzalo Navarro. Indexing highly repetitive string collections, part II: compressed indexes. ACM Comput. Surv., 54(2):26:1–26:32, 2022. doi:10.1145/3432999.

[bib.bib28] [28] Mihai Pătraşcu. Succincter. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 305–313. IEEE Computer Society, 2008. doi:10.1109/FOCS.2008.83.

[bib.bib29] [29] Rajeev Raman, Venkatesh Raman, and Srinivasa Rao Satti. Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms, 3(4):43, 2007. doi:10.1145/1290672.1290680.

[bib.bib30] [30] Luís MS Russo, Gonzalo Navarro, and Arlindo L Oliveira. Fully-compressed suffix trees. In LATIN 2008: Theoretical Informatics: 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008. Proceedings 8, pages 362–373. Springer, 2008. doi:10.1007/978-3-540-78773-0_32.

[bib.bib31] [31] Kunihiko Sadakane. Compressed suffix trees with full functionality. Theory Comput. Syst., 41(4):589–607, 2007. doi:10.1007/S00224-006-1198-X.

[bib.bib32] [32] Dirk Strothmann. The affix array data structure and its applications to RNA secondary structure analysis. Theor. Comput. Sci., 389(1-2):278–294, 2007. doi:10.1016/J.TCS.2007.09.029.

[bib.bib33] [33] Esko Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249–260, 1995. doi:10.1007/BF01206331.

[bib.bib34] [34] Peter Weiner. Linear pattern matching algorithms. 14th Annual Symposium on Switching and Automata Theory, pages 1–11, 1973. doi:10.1109/SWAT.1973.13.

Relative Compressed Reverse Suffix Array

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Our Results

2 Notation and Preliminary

2.1 Succinct Data Structure Toolkit

2.1.1 Rank/select Queries, Indexible Dictionaries and Wavelet Trees

2.1.2 Range Minimum Query (RMQ)

2.1.3 Succinct Representation of Ordinal Trees

2.2 Suffix Tree, Suffix Array and Longest Common Prefix (LCP) Array

2.3 Prefix Tree, Prefix Array and Longest Common Suffix (LCS) Array

2.4 The FM-index

Lemma 1.

2.5 Longest Common Extension (LCE) and Related Queries

Lemma 2 (Sadakane [31]).

Proof.

Lemma 3 (LCE Queries).

Proof.

Lemma 4 (LCE← Queries).

Proof.

3 Relative Encoding of 𝐏𝐀 in 𝑶⁢(𝒏) Extra bits

3.1 Basic Components

Lemma 5.

Proof.

Lemma 6 (Sampled pLCPπ).

Proof.

Corollary 7 (Sampled pLCSπ).

3.2 The Data Structure

3.2.1 Technical Overview

3.2.2 Components of the Data Structure

3.2.3 Space Complexity Analysis

3.3 Algorithm for Decoding 𝐏𝐀⁡[𝒊]

Theorem 8.

Corollary 9.

4 Relative Encoding of 𝐏𝐀 in Sublinear Space

4.1 Basic Components

Lemma 10 (Approximate pLCPπ in small space).

Proof.

Lemma 11 (Approximate pLCSπ in small space).

Proof.

Lemma 12 (Exact pLCP in small space).

Proof.

Lemma 13 (Exact LCE⁡(⋅,⋅) in small space).

Proof.

4.2 The Data Structure

4.2.1 Technical Overview

4.2.2 Handling Type-A Queries

Replacing Prefix Tree with Sparse Prefix Tree (SPT)

Lemma 14.

Proof.

Replacing Suffix Tree with Sparse Suffix Tree (SST)

Lemma 15 (Type-A Queries).

4.2.3 Handling Type-B Queries

Observation 16.

Observation 17.

CASE 𝒊∈(𝒃𝟎,𝒃𝒅]

CASE 𝒊∈[𝒃𝒅+𝟏,𝒂𝒇−𝟏]

CASE 𝒊∈[𝒂𝒇,𝒊′′)

Lemma 18 (Type-B Queries).

Theorem 19.

Corollary 20.

5 A Note On Inverse Prefix Array (IPA) Queries

Theorem 21.

6 Conclusions

References

Lemma 3 ( $\operatorname{LCE}$ Queries).

Lemma 4 ( $\overleftarrow{\operatorname{LCE}}$ Queries).

3 Relative Encoding of $\operatorname{PA}$ in $O(n)$ Extra bits

Lemma 6 (Sampled $\operatorname{pLCP}_{\pi}$ ).

Corollary 7 (Sampled $\operatorname{pLCS}_{\pi}$ ).

3.3 Algorithm for Decoding $\operatorname{PA}[i]$

4 Relative Encoding of $\operatorname{PA}$ in Sublinear Space

Lemma 10 (Approximate $\operatorname{pLCP}_{\pi}$ in small space).

Lemma 11 (Approximate $\operatorname{pLCS}_{\pi}$ in small space).

Lemma 12 (Exact $\operatorname{pLCP}$ in small space).

Lemma 13 (Exact $\operatorname{LCE}(\cdot,\cdot)$ in small space).

CASE $i\in(b_{0},b_{d}]$

CASE $i\in[b_{d}+1,a_{f}-1]$

CASE $i\in[a_{f},i^{\prime\prime})$