# Grammar Compression by Induced Suffix Sorting

Daniel S. N. Nunes  Federal Institute of BrasíliaTaguatinga Department of
Computer Science, University of BrasíliaBrasíliaBrazil<EMAIL_ADDRESS>,  Felipe A. Louza  Faculty of Electrical Engineering, Federal University of
UberlândiaUberlândiaBrazil<EMAIL_ADDRESS>,  Simon Gog  eBay Inc.San JoseUSA
<EMAIL_ADDRESS>,  Mauricio Ayala-Rincón  Departments of Computer Science and
Mathematics, University of BrasíliaBrasíliaBrazil<EMAIL_ADDRESS>and  Gonzalo
Navarro  Center for Biotechnology and Bioengineering (CeBiB) Department of
Computer Science, University of ChileSantiagoChile<EMAIL_ADDRESS>
###### Abstract.

A grammar compression algorithm, called GCIS, is introduced in this work. GCIS
is based on the induced suffix sorting algorithm SAIS, presented by Nong et
al. in 2009. The proposed solution builds on the factorization performed by
SAIS during suffix sorting. A context-free grammar is used to replace factors
by non-terminals. The algorithm is then recursively applied on the shorter
sequence of non-terminals. The resulting grammar is encoded by exploiting some
redundancies, such as common prefixes between right-hands of rules, sorted
according to SAIS. GCIS excels for its low space and time required for
compression while obtaining competitive compression ratios. Our experiments on
regular and repetitive, moderate and very large texts, show that GCIS stands
as a very convenient choice compared to well-known compressors such as Gzip,
7-Zip, and RePair, the gold standard in grammar compression. In exchange, GCIS
is slow at decompressing. Yet, grammar compressors are more convenient than
Lempel-Ziv compressors in that one can access text substrings directly in
compressed form, without ever decompressing the text. We demonstrate that GCIS
is an excellent candidate for this scenario because it shows to be competitive
among its RePair based alternatives. We also show, how GCIS relation with SAIS
makes it a good intermediate structure to build the suffix array and the LCP
array during decompression of the text.

data compression, suffix sorting, extract, suffix-array, LCP-array.

††ccs: Theory of computation Data compression††ccs: Theory of computation Data
structures and algorithms for data management††ccs: Theory of computation
Grammars and context-free languages

##  1\. Introduction

Text compression is a fundamental task in Computer Science that consists in
transforming an input string into another string whose bit sequence
representation is smaller. The suffix array (Manber and Myers, 1993; Gonnet et
al., 1992) is a key data structure used to compute lossless compression
transforms (Ohlebusch and Gog, 2011; Kärkkäinen et al., 2013; Goto and Bannai,
2014), such as the Burrows-Wheeler transform (BWT) (Burrows and Wheeler, 1994)
and the Lempel-Ziv factorization (LZ77) (Ziv and Lempel, 1977; Liu et al.,
2016), which are at the heart of the popular data compression tools like
Bzip2, 7-zip and Gzip.

The suffix array construction (or suffix sorting) may be performed in linear
time (see Puglisi et al. (2007) and Dhaliwal et al. (2012) for good reviews).
Nong et al. (2009) introduced a remarkable suffix array construction algorithm
called SAIS, which runs in linear time and is fast in practice. Subsequently,
SAIS was adapted to directly compute the BWT (Okanohara and Sadakane, 2009),
the $\Phi$-array (Kärkkäinen et al., 2009; Goto and Bannai, 2014), the LCP
array (Fischer, 2011), and the suffix array for string collections (Louza et
al., 2017a).

Grammar compression (Kieffer and Yang, 2000) is a compression technique based
on finding a small context-free grammar that generates (only) the text.
Finding the smallest such grammar is NP-hard (Charikar et al., 2005), but
heuristics like RePair (Larsson and Moffat, 1999) work very well in practice.
Like Lempel-Ziv, grammar compression performs particularly well on repetitive
text collections. An advantage of grammar compression is that text substrings
can be extracted from the compressed representation without the need to
decompress the text (Bille et al., 2015). One can then aim at never
decompressing the text but work on it directly in compressed form.

This article introduces GCIS, a new grammar-based compression algorithm that
builds on SAIS framework. GCIS constructs a context-free grammar recursively,
based on the string factorization performed by SAIS. The rules are encoded
exploiting the common prefixes between the right-hands of consecutive rules,
which are sorted lexicographically by SAIS. GCIS is the first grammar-
compressor algorithm, as far as we know, based on induced suffix sorting.

Our experiments show that, on repetitive texts and compared to the best
grammar-compressor (RePair (Larsson and Moffat, 1999)) and the best Lempel-Ziv
compressor (7-zip (Pavlov, 2017)), GCIS is an interesting alternative in
practice because it displays the fastest compression speed and low memory
usage, while reaching a compression ratio close to that of RePair. We also
show that GCIS is competitive with the relevant alternatives when processing
regular (not highly repetitive) and very large texts.

In exchange, GCIS is slower than most alternatives for decompressing the text.
As explained, however, we may aim at extracting any desired substring while
never decompressing the whole text. When compared to variants of RePair that
allow extraction, GCIS turns out to be very efficient while using less space.
Further, it is possible to build the suffix and LCP arrays as a byproduct of
text decompression by GCIS in competitive time.

This work differs from its early version (Nunes et al., 2018) in that we
support efficient extraction of substrings and computation of suffix and LCP
arrays directly from decompression. We also present more thorough descriptions
and experimental results.

##  2\. Background

###  2.1. Suffix array

Let $T$ be a string of length $|T|=n$, over an ordered alphabet $\Sigma$. We
assume that our alphabet $\Sigma$ has an integer size, but limited to $n$,
that is, $1\leq|\Sigma|\leq n$. The concatenation of strings or symbols is
denoted by the dot operator ($\cdot$). The symbol $<$ is used for the
lexicographic order relation between strings.

Let $T[i]$ be the $i$-th symbol of $T$. The substring (factor) from $T[i]$ to
$T[j]$, both included, is denoted by $T[i,j]$, for $1\leq i\leq j\leq n$. A
prefix of $T$ is a substring of the form $T[1,i]$ and a suffix is a substring
of the form $T[i,n]$, also denoted by $T_{i}$. For convenience, it is assumed
that $T$ always ends with a special symbol $T[n]=\$$, which is not present
elsewhere in $T$ and lexicographically precedes every symbol in $T[1,n-1]$.

The suffix array ($\mathsf{SA}$) (Manber and Myers, 1993; Gonnet et al., 1992)
of a string $T[1,n]$ is an array of integers in the range $[1,n]$ that gives
the lexicographic order of all suffixes of $T$, such that
$T_{\mathsf{SA}[1]}<T_{\mathsf{SA}[2]}<\ldots<T_{\mathsf{SA}[n]}$. The length
of the longest common prefix ($\mathsf{LCP}$) of two strings $X$ and $Y$ in
$\Sigma^{*}$ is denoted $\texttt{lcp}(X,Y)$. The $\mathsf{LCP}$ array of
$T[1,n]$ is an array of integers that stores the lcp value between consecutive
suffixes in $\mathsf{SA}$, such that
$\mathsf{LCP}[i]=\texttt{lcp}(T_{\mathsf{SA}[i-1]},T_{\mathsf{SA}[i]})$, for
$1<i\leq n$, and we define $LCP[1]=0$. The suffixes starting with the same
symbol $c\in\Sigma$ form a $c$-bucket in $\mathsf{SA}$. The head and the tail
of a $c$-bucket refer to the first and the last position of the $c$-bucket in
$\mathsf{SA}$.

###  2.2. Grammar compression

Let $G=(\Sigma,\Gamma,P,X_{S})$ be a reduced context-free grammar (i.e, with
no unreachable non-terminals) such that $\Sigma$ is the terminal alphabet of
$G$; $\Gamma$ is the set of non-terminal symbols (disjoint from $\Sigma$);
$P\subseteq\Gamma\times(\Sigma\cup\Gamma)^{*}$ is the set of production rules;
and $X_{S}\in\Gamma$ is the start symbol.

A production rule $(X_{i},\alpha_{i})$ is also denoted
$X_{i}\rightarrow\alpha_{i}$. In this case, it is said that $\alpha_{i}$ is
derived from $X_{i}$. For strings $S,R\in(\Sigma\cup\Gamma)^{*}$, if $R$ is
obtained from $S$ by production rules in $P$, then $R$ is derived from $S$.
When $R$ is obtained by a (possibly empty) sequence of derivations from $S$,
then $R$ is generated from $S$.

Given a string $T$, the grammar compression problem is to find a grammar $G$
that generates only $T$, such that $G$ can be represented in less space than
the original $T$. Given that $G$ grammar-compresses $T$, for
$(X_{i},\alpha_{i})\in P$, $\mathcal{G}(X_{i})=S$ is defined as the single
string $S\in\Sigma^{*}$ that is generated from $X_{i}$. The language generated
by $G$ contains the unique string $\mathcal{G}(X_{S})=T$. This notion can be
extended further for a string of terminals and non-terminals $S$, such that:

$\mathcal{G}(S)=\\{W_{1}\cdot W_{2}\cdot\ldots\cdot
W_{|S|}\;\lvert\;W_{k}\in\mathcal{G}(S[k]),1\leq k\leq|S|\\}.$

When each $S[i]$, $1\leq i\leq|S|$, generates a single sequence, the previous
definition can be replaced by the concatenation of the strings generated by
$S[i]$, $1\leq i\leq|S|$:

$\mathcal{G}(S)=\mathcal{G}(S[1])\cdot\mathcal{G}(S[2])\cdot\ldots\cdot\mathcal{G}(S[|S|])$

###  2.3. Integer Encoding

We cover various techniques to encode sequences of integers, when most of them
are expected to be small. Some of the techniques allow us to directly access
any integer in the sequence.

#### Simple8b

The Simple8b scheme, proposed by Anh and Moffat (2010), encodes a sequence of
small integers in a $64$-bit word using the number of bits required by the
largest integer. Basically, it identifies a word with a $4$-bit tag called
selector, which specifies the number of integers encoded in the rest of the
word and the width of such integers. Simple8b also has specific selectors for
a run consisting of zeroes. If a run of $240$ or $120$ zeros is encountered,
it can be represented with a single $64$-bit word.

#### Directly Addressable Codes

The Directly Addressable Codes (DAC) proposed by Brisaboa et al. (2013) allow
efficient retrieval of any given value $A[i]$ from an array of integers
$A[1,n]$ while encoding such integers compactly. Let $l_{i}$ be the length
(number of bits) of $A[i]$, then this encoding splits each $A[i]$ into $\lceil
l_{i}/b\rceil$ blocks $v_{i,1}$, $v_{i,2}$,…, $v_{i,k}$ of $b$ bits each. A
bit $b_{i,j}=1$ is associated with a block $v_{i,j}$ if $j<k$, that is,
$v_{i,j}$ is not the last block of $A[i]$. Otherwise, $b_{i,j}=0$. Then a
layered data structure is constructed in such a way that the $k$-th layer
contains two bitmaps: the first bitmap is the concatenation of blocks
$v_{i,k}$, for every $1\leq i\leq n$, whereas the second bitmap is the
concatenation of the bits $b_{i,k}$ associated with each block $v_{i,k}$.

To retrieve any given value $A[i]$, one must first recover $b_{i,1}$ and check
if its value is zero. If so $A[i]$ equals $v_{i,1}$, otherwise, it is
necessary to proceed recursively to the $j$-th entry of the next layer, where
$j=\sum_{m=1}^{i}b_{m,1}$, and append the result of the recursive call to
$v_{i,1}$. The prefix sum value $j$ can be computed in constant time by using
auxiliary data structures on top of the bitmaps.

#### Elias-Fano Encoding

This format permits the encoding of a monotonically increasing sequence of $n$
integers over the interval $[0,m-1]$ within $2n+n\lceil\lg\frac{m}{n}\rceil$
bits and allows the retrieval of any integer of such sequence in constant time
(Vigna, 2013). Each integer $a_{i}$ is divided into two parts: $u_{i}$, the
$\lceil\lg n\rceil$ most significant bits of $a_{i}$ and $l_{i}$, the
$\lceil\lg\frac{m}{n}\rceil$ remaining bits of $a_{i}$. The $l_{i}$ values are
concatenated in a single array of $n\lceil\lg\frac{m}{n}\rceil$ bits and each
value $a_{i}$ is classified in one of the total of $n$ possible buckets. Then,
the number of elements of each bucket is represented in a negated unary
representation and such representations are concatenated in a bitmap $B$ of
$2n$ bits, $n$ bits for each possible bucket and further $n$ bits for every
element $a_{i}$.

To retrieve the $i$-th value of the sequence of integers, one just needs to
search for the position $k$ of the $i$-th one bit on $B$, and append $l_{i}$
to the binary representation of $k-i$. The position $k$ can be retrieved in
constant time using auxiliary data structures on top of $B$.

##  3\. SAIS: Induced Suffix Sorting

SAIS (Nong et al., 2009) builds on the induced suffix sorting technique
introduced by previous algorithms (Itoh and Tanaka, 1999; Ko and Aluru, 2003).
Induced suffix sorting consists in deducing the order of unsorted suffixes
from a (smaller) set of already ordered suffixes.

The next definition classifies suffixes and symbols of strings.

###### Definition 0 (L-type and S-type).

For any string $T$, $T_{n}=\$$ has type S. A suffix $T_{i}$ is an S-suffix if
$T_{i}<T_{i+1}$, otherwise $T_{i}$ is an L-suffix. Each symbol $T[i]$ has the
type of $T_{i}$.

The suffixes can be classified in linear time by scanning $T$ once from right
to left, so that the type of each suffix is stored in a bitmap of size $n$.

Note that, within a $c$-bucket, the L-suffixes precede the S-suffixes.

Further, the classification of suffixes is refined as follows:

###### Definition 0 (LMS-type).

Let $T$ be a string. Then $T_{i}$ is an LMS-suffix if $T_{i}$ is an S-suffix
and $T_{i-1}$ is an L-suffix.

Nong et al. (2009) showed that the order of the LMS-suffixes is enough to
induce the order of all suffixes. This is the basis of the SAIS algorithm.

###  3.1. SAIS framework

  1. (1)

Sort the LMS-suffixes. This step is explained later.

  2. (2)

Insert the LMS-suffixes into the tail of their respective $c$-buckets in
$\mathsf{SA}[1,n]$, without changing their order. Now $\mathsf{SA}$ contains
the LMS-suffixes positions, in sorted order, on the end of each $c$-bucket.
The remaining values of $\mathsf{SA}$ are initialized with a sentinel $\bot$
value.

  3. (3)

Induce L-suffixes by scanning $\mathsf{SA}[1,n]$ from left to right: for each
suffix $\mathsf{SA}[i]\neq\bot$, if $T[\mathsf{SA}[i]-1]$ is L-type, insert
$\mathsf{SA}[i]-1$ into the head of its $c$-bucket.

  4. (4)

Induce S-suffixes by scanning $\mathsf{SA}[1,n]$ from right to left: for each
suffix $\mathsf{SA}[i]\neq\bot$, if $T[\mathsf{SA}[i]-1]$ is S-type, insert
$\mathsf{SA}[i]-1$ into the tail of its $c$-bucket.

Whenever a value is inserted in the head (or tail) of a $c$-bucket, the
pointer to the head (or tail) is increased (or decreased) by one.

In order to sort the LMS-suffixes in Step 1, $T[1,n]$ is divided (factorized)
into LMS-substrings.

###### Definition 0.

$T[i,j]$ is an LMS-substring if both $T_{i}$ and $T_{j}$ are LMS-suffixes, but
no suffix between $i$ and $j$ has LMS-type. The last suffix $T_{n}$ is an LMS-
substring.

Let $r^{1}_{1},r^{1}_{2},\dots,r^{1}_{n^{1}}$ be the $n^{1}$ LMS-substrings of
$T$ read from left to right. A modified version of SAIS is applied to sort the
LMS-substrings. Starting from Step 2, $T[1,n]$ is scanned (right-to-left) and
each new LMS-suffix starting with $c$ is inserted (bucket-sorted) at the tail
of its $c$-bucket. Steps 3 and 4 work exactly the same. At the end, the LMS-
substrings are sorted and the beginning positions of each LMS-substring are
stored in their corresponding $c$-buckets in $\mathsf{SA}$.

###  3.2. Naming

A name $v^{1}_{i}$ is assigned to each LMS-substring $r^{1}_{i}$ according to
its lexicographical rank in $[1,\sigma^{1}]$, such that $v^{1}_{i}\leq
v^{1}_{j}$ iff $r^{1}_{i}\leq r^{1}_{j}$, where $\sigma^{1}$ is the number of
different LMS-substrings in $T$. In order to compute the names, each
consecutive LMS-substrings in $\mathsf{SA}$, say $r^{1}_{i}$ and
$r^{1}_{i+1}$, are compared to determine if either $r^{1}_{i}=r^{1}_{i+1}$ or
$r^{1}_{i}<r^{1}_{i+1}$. In the former case $v^{1}_{i+1}$ is set to
$v^{1}_{i}$, whereas in the latter case $v^{1}_{i+1}$ is set to $v^{1}_{i}+1$.
This procedure may be sped up by comparing the LMS-substrings first by symbol
and then by type, with L-type symbols being smaller than S-type symbols in
case of ties (Nong et al., 2011).

###  3.3. Recursive call

A new (reduced) string $T^{1}=v^{1}_{1}\cdot v^{1}_{1}\cdots v^{1}_{n^{1}}$ is
created, whose length ${n^{1}}$ is at most $n/2$, and the alphabet size
$\sigma^{1}$ is integer. If every $v^{1}_{i}\neq v^{1}_{j}$ then all LMS-
suffixes are already sorted. Otherwise, SAIS is recursively applied to sort
all the suffixes of $T^{1}$. Nong et al. (Nong et al., 2009) showed that the
relative order of the LMS-suffixes in $T$ and the order of the respective
suffixes in $T^{1}$ are the same. Therefore, the order of all LMS-suffixes can
be determined by the result of the recursive algorithm.

##  4\. GCIS: Grammar Compression by Induced Suffix Sorting

This section introduces the Grammar Compression algorithm by Induced Sorting
(GCIS).

###  4.1. Compressing

First, a context-free grammar $G=(\Sigma,\Gamma,P,X_{S})$ that generates only
$T[1,n]$ is computed. To do this SAIS is modified as follows.

Consider the $j$-th recursion level. In Step 1, after the input string
$T^{j}[1,n^{j}]$ is divided into the LMS-substrings
$r^{j}_{1},r^{j}_{2},\dots,r^{j}_{n^{j+1}}$ and named
$v^{j}_{1},v^{j}_{2},\dots,v^{j}_{n^{j+1}}$, a new rule $v^{j}_{i}\rightarrow
r^{j}_{i}$ is created for each different LMS-substring $r^{j}_{i}$. Moreover,
an additional rule $v_{0}^{j}\rightarrow v_{0}^{j-1}T^{j}[1,j_{1}-1]$ if $j>0$
or $v_{0}^{j}\rightarrow T[1,j_{1}-1]$ if $j=0$, with $j_{1}$ standing for the
index of the leftmost LMS-type suffix of $T^{j}$, is created for the prefix of
$T^{j}$ that is not included in any LMS-substring. In this context, when
$j=0$, $n^{0}=n$ and $T^{0}=T$.

The algorithm is then called recursively with the reduced string
$T^{j+1}=v^{j}_{1}\leavevmode\nobreak\ \cdot\leavevmode\nobreak\
v^{j}_{2}\leavevmode\nobreak\ \cdots\leavevmode\nobreak\ v^{j}_{n^{j+1}}$ as
input as long as $\sigma^{j+1}<n^{j+1}$, that is, the LMS-substrings are not
pairwise distinct. At the end, when $\sigma^{\ell}=n^{\ell}$, the last
recursion level $j=\ell$ is reached, and the start symbol of $X_{S}$ of $G$ is
created so that the initial production $X_{S}\rightarrow v^{\ell}_{0}\cdot
v^{\ell}_{1}\cdot v^{\ell}_{2}\cdots v^{\ell}_{n^{\ell}}$ generates the
original string $T[1,n]$.

The algorithm stops after computing $X_{S}$, since we are not interested in
constructing the suffix array; Steps 2, 3 and 4 of SAIS are not executed. The
recursive calls return to the top level and a grammar $G$ that generates only
$T[1,n]$ has been computed.

Since for each LMS-substring there is a unique $v^{j}_{i}$, there are no
cycles in any generation. Further, there is only one path of derivations that
from a string $S$ generates a string $S^{\prime}$. The consequence of this
deterministic choice, for every derivation, is that $\mathcal{G}(X_{i})$, for
$X_{i}\in\Gamma$, is a fixed string of terminals. Figure 1 shows the grammar
construction on GCIS.

Figure 1. Grammar construction during GCIS. All LMS-substrings (those starting
with a ‘$*$’ symbol), are sorted according to SAIS framework, and then rules
$v^{0}_{0}\rightarrow\mathrm{AG},v^{0}_{1}\rightarrow\mathrm{\$},\ldots,v^{0}_{7}\rightarrow
CTTTTC$ are created. Next, $T^{1}$ is obtained by replacing every LMS-
substring by the left-hand side of its rule. The procedure is applied
recursively to $T^{1}$. When $T^{2}$ is created, the alphabet size is equal to
$|T^{2}|=n^{2}$, and thus the starting rule $X_{S}$ that generates $T^{0}$ is
obtained.

#### Grammar compression

Consecutive entries in the set of productions $P$ are likely to share a common
prefix, since the LMS-substrings are given lexicographically ordered by SAIS.
Therefore, each rule $X_{i}\rightarrow\alpha_{i}\in P$ is encoded using two
values $(l_{i},\mathrm{s}(\alpha_{i}))$, such that $l_{i}$ encodes lcp
$(\alpha_{i-1},\alpha_{i})$, and the remaining symbols of $\alpha_{i}$ are
given by $\mathrm{s}(\alpha_{i})=\alpha_{i}[l_{i}+1,|\alpha_{i}|]$. For each
starting rule $v^{j}_{0}$, we define $l_{i}=0$. This technique is known as
Front-coding (Witten et al., 1999).

The computation of $(l_{i},\mathrm{s}(\alpha_{i}))$ is performed with no
additional cost with a slight modification in the naming procedure of SAIS.
Each consecutive LMS-substring in $\mathsf{SA}$, say $r^{j}_{i-1}$ and
$r^{j}_{i}$, are compared first by symbol until a mismatch is found, and then
compared by type, to check if either $r^{j}_{i-1}=r^{j}_{i}$ or
$r^{j}_{i-1}<r_{i}$. The symbol-wise comparison reveals
$\texttt{lcp}(r^{j}_{i-1},r^{j}_{i})$ as well, so the resulting complexity is
the same with a small slowdown in the running time.

#### Time complexity

GCIS runs in $O(n)$ time, since each step of the modified SAIS runs in linear
time and the length of the reduced string $T^{j}$ is at most $|T^{j-1}|/2$.

#### Implementation details

Each non-terminal $X_{i}$ is represented by a pair
$\alpha_{i}=(l_{i},\mathrm{s}(\alpha_{i}))$, as explained. The $l_{i}$ values
tend to be small and, considering the $j$-th recursion value, the sum of such
values cannot be greater than $n^{j}$, since no two LMS-substrings overlap by
more than one symbol.

One can encode all $l_{i}$ values by using the Simple8b encoding in an integer
array $W$. All strings $\mathrm{s}(\alpha_{i})$ are encoded in a single fixed-
width integer array $Y$, of cell width $\lfloor\lg(\sigma^{j})\rfloor+1$ bits.
The length of each $\mathrm{s}(\alpha_{i})$ is also encoded using Simple8b
into a word array $Z$. The same observation of the lcp sum can be done here:
the sum of all $|\mathrm{s}(\alpha_{i})|$ on the $j$-th recursion level is no
larger than $n^{j}$.

###  4.2. Decompressing

The decoding process is done level-wise, starting from the last recursion
level $j=\ell$, by decoding the right side of each rule. At the end, $T$ is
decoded from $T^{1}$.

In the $j$-th recursion level, the values $(w,y,z)$ from $W$, $Y$ and $Z$, the
data structures mentioned in the implementation details of Section 4.1, are
decoded sequentially. In order to obtain the right-hand side of the production
rules $\alpha_{k+1}$ from $\alpha_{k}$, the first $w$ symbols of $\alpha_{k}$
are copied to $\alpha_{k+1}$ and the $z$ symbols from $Y$, which correspond to
the string $y$, are appended to $\alpha_{k+1}$. After this process the plain
representation of each rule is stored, in a single array of cells with fixed
width $\lfloor\lg(\sigma^{j})\rfloor+1$ bits. An additional array of pointers
$D$ is also created to find the starting position of each rule in this fixed-
width array.

With the fixed-width array and the array of pointers $D$, $T^{j-1}$ now can be
decoded from $T^{j}$. First, the right side of $v_{0}^{j}$ is copied into
$T^{j-1}$. Then, $T^{j}$ is scanned in a left-to-right fashion and for each
$T^{j}[i]$ the algorithm appends to $T^{j-1}$ the right-hand side of the non-
terminal $T^{j}[i]$, which can be easily found with support of array $D$ in
constant time.

#### Time complexity

The whole decompression process takes $O(n)$ time.

###  4.3. Extracting substrings

In order to support extraction of substrings from the compressed text, it is
necessary to augment the dictionary with two additional data structures:
$P_{S}$, a partial-sum on the lengths of the symbols in the reduced string
$T^{\ell}$ of the last recursion level, and $L$, a data structure that for
each non-terminal $X_{i}$ stores $|\mathcal{G}(X_{i})|$. Formally, those data
structures are defined as:

$P_{S}(i)\leavevmode\nobreak\ \leavevmode\nobreak\ =\leavevmode\nobreak\
\leavevmode\nobreak\ \sum_{j=1}^{i-1}|\mathcal{G}(X_{S_{i}})|,\quad
X_{S}\rightarrow X_{S_{1}},\ldots X_{S_{k}}\text{ and }\quad 1\leq i\leq k+1$

$L(X)\leavevmode\nobreak\ \leavevmode\nobreak\ =\leavevmode\nobreak\
\leavevmode\nobreak\ |\mathcal{G}(X)|,\quad X\in\Sigma\cup\Gamma$

The data structure $L$ can also be defined recursively as:

$L(X)=\left\\{\begin{array}[]{l}1,\quad X\in\Sigma\\\
\displaystyle{\sum_{i=1}^{|S|}L(S[i])},\quad X\rightarrow S\end{array}\right.$

To obtain a substring $T[l,r]$, we then proceed as follows:

  1. (1)

With a binary search, locate indices $a$ and $b$ from $P_{S}$ such that:

$\displaystyle a=\max\\{1\leq k\leq|T^{\ell}|\;\lvert\;P_{S}(k)\leq l\\}$
$\displaystyle b=\min\\{1\leq k\leq|T^{\ell}|+1\;\lvert\;P_{S}(k)>r\\}-1$

  2. (2)

Let $\ell$ be the number of levels in GCIS grammar and $S$ the string derived
from $X_{S}$. Then define $E^{\ell}=S[a,b]$ and follow the next steps for
$i=\ell$ to $i=1$.

  3. (3)

Apply a derivation step to each non-terminal $X\in E^{i}$ to obtain a new
string $E^{i-1}$. Note that $\mathcal{G}(E^{i-1})=T[l^{\prime},r^{\prime}]$ is
a superstring of $T[l,r]$.

  4. (4)

Trim $E^{i-1}$ from the left and right as much as possible as long as it
generates a superstring of $T[l,r]$. This can be done efficiently because we
know the lenght of $\mathcal{G}(X)$, for every $X\in\Sigma\cup\Gamma$.

    1. (a)

If $i=1$, then $E^{0}$ contains only terminal symbols and generates a
superstring $T[l^{\prime},r^{\prime}]=E^{0}$ of $T[l,r]$. Thus, one simply
extracts the symbols $E^{0}[l-l^{\prime}+1,r-l^{\prime}+1]$ to obtain
$T[l,r]$.

    2. (b)

If $i>1$, then $E^{i-1}$ contains only non-terminal symbols and generates a
superstring $T[l^{\prime},r^{\prime}]=\mathcal{G}(E^{i-1})$ of $T[l,r]$. We
then trim $E^{i-1}$ by using $L$ and finding, with a linear search, two
indices $a$ and $b$ of $E^{i-1}$ such that:

$\displaystyle a=\max\left\\{1\leq
k\leq|E^{i}|\;\left\lvert\;l^{\prime}+\sum_{j=1}^{k-1}L(E^{i}[j])\leq
l\right.\right\\}$ $\displaystyle b=\max\left\\{1\leq
k\leq|E^{i}|\;\left\lvert\;r^{\prime}-\sum_{j=k+1}^{|E^{i}|}L(E^{i}[j])\geq
r\right.\right\\}$

$E^{i-1}$ is then trimmed to $E^{i-1}[a,b]$ before proceeding.

Figure 2 shows an example for extracting a text using the aforementioned
procedure.

Figure 2. Extraction of the substring $T[10,34]$ of the text of Figure 1.
Initially, a binary search is performed on $P_{S}$ to identify the substring
of $E^{2}$ that shall be decompressed: $E^{2}[2,4]$, which generates
$T[9,43]$, is decompressed to obtain $E^{1}$. A linear scan is performed in
both ends considering the length of the terminals generated by each rule of
$E^{1}$ to find the indexes $a=2$ and $b=8$. $E^{1}[2,8]$ is then decompressed
and $E^{0}=T[9,36]$ is obtained, which makes possible to extract $T[10,34]$ by
simply ignoring both ends.

#### Implementation details

Since the length of the string $T^{\ell}$ is much shorter than the original
text in practice, the verbatim representation of $P_{S}$ as an array of
integers is affordable.

The array $L$ is represented using DACs. This representation allows efficient
access while representing the data in a compact way.

To support fast extraction, we need to efficiently decompress a single rule.
Simple8b encoding works very well when the objective is compressing or
decompressing since all the rules are first expanded sequentially in the
decompressing stage. However, when the aim is to extract symbols, we need to
expand individual rules. Thus, instead of encoding all the lcp values with the
simple8b scheme, Elias-Fano encoding is employed, allowing us to retrieve a
random lcp value of a rule efficiently and hence the decoding of a random
rule. The length of each $\mathrm{s}(\alpha_{i})$ is also encoded using Elias-
Fano and the $\mathrm{s}(\alpha_{i})$ values are encoded in a fixed-width
integer array. Since the lcp values are front-encoded, we force that every
$k$-th lcp value is set to $0$, with $k\in O(1)$. This setting does not have a
significant impact on compression and ensures that we have to backtrack a
constant number of rules to extract an individual rule prefix.

###  4.4. Suffix array construction

The suffix array ($\mathsf{SA}$) construction boils down to sorting all
suffixes of $T$. Although GCIS compression does not sort suffixes, it executes
Step 1 of SAIS and the production rules created correspond to the LMS-
substrings already sorted, which is used by SAIS for sorting all suffixes. We
show next how to modify our decompression algorithm for building $\mathsf{SA}$
as a byproduct with, asymptotically, no additional overhead.

First, when $j=\ell$, $X_{S}\rightarrow T^{\ell}$ is taken, and its suffix
array $\mathsf{SA}^{j}$ is built directly as $\mathsf{SA}^{j}[T^{j}[i]]=i$.
Nong et al. (2009) observed that $\mathsf{SA}^{j}$ also gives the order of all
LMS-suffixes of string $T^{j-1}$. Then, $T^{j-1}$ is decoded (Section 4.2),
and Steps 2, 3 and 4 of SAIS (Section 3) are executed to obtain
$\mathsf{SA}^{j-1}$, and so on. The algorithm proceeds for $j=\ell-1,\dots,1$,
obtaining the reduced string $T^{j-1}$ together with $\mathsf{SA}^{j-1}$ at
each iteration. At the end, the original string $T$ is decoded from $T^{1}$
and $\mathsf{SA}$ is induced from $\mathsf{SA}^{1}$.

#### Time Complexity

$\mathsf{SA}$ is built in $O(n)$ time, since each step of SAIS is linear and
the length of all reduced strings is $O(n)$.

###  4.5. LCP array construction

When $|\Sigma|\in O(1)$, the longest common prefix ($\mathsf{LCP}$) array can
also be computed in linear time within the induced suffix sorting framework
(Fischer, 2011; Louza et al., 2017b). We show below how to modify our
decompression algorithm to compute $\mathsf{SA}$ and $\mathsf{LCP}$ together
with, asymptotically, no additional cost.

When $j=1$, the original string $T$ is decoded from $T^{1}$, and
$\mathsf{SA}^{1}$ stores the order of all LMS-suffixes of $T$. Then, in linear
time, we compute the $\mathsf{LCP}$ array of the LMS-suffixes using a sparse
variant of $\Phi$-algorithm by Kärkkäinen et al. (2009), which avoids storing
auxiliary arrays by reusing the space of $\mathsf{SA}[n/2,n]$ and
$\mathsf{LCP}[n/2,n]$. The lcp-values between the LMS-suffixes are used to
induce the lcp-values between the L-suffixes during Step 3 (Section 3), and
these are used to induce the S-suffixes during Step 4 (see Louza et al.
(2017b) for details). Given an additional stack of $O(\sigma\log n)$ bits (Gog
and Ohlebusch, 2011), each lcp-value induction is done in $O(\sigma)$ time,
which we assume to be constant at the top recursion level.

Therefore, at the end we have computed $\mathsf{SA}$ and $\mathsf{LCP}$ as a
byproduct of GCIS decompression.

#### Time complexity

$\mathsf{SA}$ and $\mathsf{LCP}$ are built in $O(n)$ time, since each step of
SAIS is linear and the $\mathsf{LCP}$-values induction can be done in constant
time.

##  5\. Experiments

To confirm the practical value of GCIS, we conducted experiments using several
corpora. We measured compression and decompression speed, compression ratio,
and memory usage during compression and decompression of GCIS against
classical and grammar-based compressors (Section 5.4), evaluated the
extraction of symbols (Section 5.6) and showed the efficiency of suffix array
construction of GCIS during the decompression (Section 5.7).

In the following subsections we describe and discuss the experimental setup
and the results.

###  5.1. Texts

Regular texts were taken from the corpora large-corpus (Trigell, 1998), enwiki
(Mahoney, 2006), manzini (Manzini, 2003), pizza-chili (Ferragina and Navarro,
2005a) and silesia (Deorowicz, 2003). Repetitive texts were chosen from pizza-
chili-repetitive corpus (Ferragina and Navarro, 2005b). Very large inputs were
built by repeating and mutating strings such as chr19 (Consortium, 2009) ,
sars-cov (NCBI, 2020) and salmonella (NCBI, 2007) with a mutation rate of
$0.1\%$, thus these texts are highly repetitive as well; each filename has an
integer suffix that represents the number of repetitions. In addition, a
$20$GB prefix from November 2019 Wikipedia dump was taken (Wikipedia, 2019).
Tables 1, 2 and 3 summarize the chosen texts and their size, grouping in boxes
texts from the same corpus.

Table 1. Regular texts. Regular text | Size (MB)
---|---
archive | $27.07$
emacs | $47.46$
linux | $47.60$
samba | $41.58$
spamfile | $84.22$
enwiki8 | $100.00$
enwiki9 | $1000.00$
chr22 | $34.55$
etext99 | $105.28$
gcc-3.0.tar | $86.83$
howto | $39.42$
jdk13c | $69.73$
linux-2.4.5.tar | $116.25$
rctail96 | $114.71$
rfc | $116.42$
sprot34.dat | $109.62$
w3c2 | $104.20$
dblp.xml | $296.14$
dna | $403.93$
english | $2210.40$
pitches | $55.83$
sources | $210.87$
dickens | $10.19$
mozilla | $51.22$
mr | $9.97$
nci | $33.55$
oofice | $6.15$
osdb | $10.09$
reymont | $6.63$
samba | $21.61$
sao | $7.25$
webster | $41.46$
xray | $8.457$
xml | $5.35$
Table 2. Repetitive texts. Repetitive text | Size (MB)
---|---
cere | $461.29$
coreutils | $205.28$
dblp.xml.00001.1 | $104.86$
dblp.xml.00001.2 | $104.86$
dblp.xml.0001.1 | $104.86$
dblp.xml.0001.2 | $104.86$
dna.001.1 | $104.86$
einstein.de.txt | $92.76$
einstein.en.txt | $467.63$
english.001.2 | $104.86$
Escherichia_Coli | $112.69$
influenza | $154.81$
kernel | $257.96$
para | $429.27$
proteins.001.1 | $104.86$
sources.001.2 | $104.86$
world_leaders | $46.97$
Table 3. Very large texts. Very large text | Size (MB)
---|---
c050 | $2956.45$
c100 | $5912.90$
c150 | $8869.35$
c200 | $11\,825.80$
c250 | $14\,782.25$
c300 | $17\,738.69$
c350 | $20\,695.14$
sars-cov100000 | $2990.30$
sars-cov200000 | $5980.60$
sars-cov300000 | $8970.90$
sars-cov400000 | $11\,961.20$
sars-cov500000 | $14\,951.50$
sars-cov600000 | $17\,941.80$
sars-cov700000 | $20\,932.10$
enwiki-20191120-20G | $20\,000.00$
salmonella1000 | $4928.40$
salmonella2000 | $9856.80$
salmonella3000 | $14\,785.20$
salmonella4000 | $19\,713.60$

###  5.2. Compressors and Extractors

To evaluate GCIS in compression speed, decompression speed and compression
ratio, we chose the well-known compressors Gzip (Gailly and Adler, 2017),
Bzip2 (Seward, 1996), 7-zip (Pavlov, 2017); the statistical compressor Ppmdj
(Shkarin, 2006); the grammar compressor RePair (Wan, 2014), the Lempel-Ziv
approximation for very large texts ReLZ (Kosolobov et al., 2020), and the
RePair approximation for very large texts BigRePair (Gagie et al., 2019).

Regarding extraction of symbols, we compared GCIS with different encodings of
RePair grammars that allow fast extraction. These encodings can be represented
in a more straight-forward way, storing $\mathcal{G}(X)$, for
$X\in\Sigma\cup\Gamma$, or in a more elaborated way, creating succinct tree
data structures that replace the original grammar encoding while allowing one
obtain the right-hand side of any rule, as described by Maruyama and Tabei
(2013). The implementation of such data structures was based on the work of
Gagie et al. (2020) and can be found in (I, 2020). We used the following
encodings:

  * •

PlainSlp_32Fblc: uses $32$-bit integers for the array representations.

  * •

PlainSlp_FblcFblc: employs the minimum bit length required to represent the
maximum value of a given integer array.

  * •

PlainSlp_IblcFblc: uses roughly $\lceil\lg i\rceil$ bits to represent the
$i$-th rule exploiting that the $i$-th rule is less than $i$. For representing
$\mathcal{G}(X)$, for $X\in\Sigma\cup\Gamma$, it uses the same strategy of
PlainSlp_FblcFblc.

  * •

PoSlp_Iblc: employs the approach POSLP of Maruyama and Tabei (2013) to
represent the parse tree and encodes the leaves using roughly $\lceil\lg
i\rceil$ bits for the $i$-th rule.

  * •

PoSlp_Sd: applies the POSLP approach of Maruyama and Tabei (2013) to represent
the parse tree and encodes the leaves with Elias-Fano.

In order to assess the computation of suffix and LCP arrays directly from
decompression, GCIS was compared with efficient suffix and $\mathsf{LCP}$
construction algorithms implemented by sais-lite (Mori, 2010; Kurpicz, 2015)
and divsufsort (Mori, 2008; Kurpicz, 2016).

GCIS source code and a detailed description of the processed data are
available at https://github.com/danielsaad/gcis.

###  5.3. Environment Setup

Due to memory capacity and availability, we conducted the experiments in two
machines, one for the regular and repetitive corpora and another for the very
large datasets. Their specifications follow:

Machine #1, used for regular and repetitive texts:

  * •

CPU: 2x Intel(R) Xeon(R) CPU E5-2640 v3 @ 2.60GHz CPUs;

  * •

RAM Memory: $64$GB;

  * •

Operating System: Centos7, kernel version 3.10.

Machine #2, used for very large datasets:

  * •

CPU: 2x Intel(R) Xeon(R) E5-2630 v3 @ 2.40GHz;

  * •

RAM Memory: $386$GB;

  * •

Operating System: Debian GNU/Linux 8, kernel version 3.16.

We compiled GCIS, RePair (and its extractors), BigRePair, Ppmdj and ReLZ under
gcc with -O3 -NDEBUG flags. The default command line parameters of Gzip,
Bzip2, Ppmdj, ReLZ were used on the experiments. A dictionary size of $1$ GB
was used in 7-zip. BigRePair RAM usage was limited to $10$ GB.

GCIS was implemented in C++11 using the Succinct Data Structure Library (SDSL)
version 2.0 (Gog et al., 2014).

###  5.4. Compression and decompression

We evaluated all compressors in terms of compression ratio, compression and
decompression speed. We also considered their peak memory usage during
compression and decompression. BigRePair could not compress some texts, so its
corresponding data in the graphs are missing. Decompression in ReLZ is not
implemented, nonetheless, ReLZ serves as a compression benchmark since it
approximates the Lempel-Ziv parse.

It is important to remark that BigRePair does not produce a compact
representation of rules, since it represents the right-hand side of its rules
with $2$ integers (all the rules are of length two). However, we optimized it
by representing each rule with at most $\lceil\log_{2}r\rceil$ bits, $r$ being
the number of rules, and integrating the non-terminals that occur only once in
their corresponding right-hand side. This saves $\lceil\log_{2}r\rceil$ bits
for each eliminated non-terminal.

For very large texts, only 7-zip, GCIS, ReLZ and BigRePair were evaluated,
since they are the best choices for repetitive data. RePair was not considered
because its data structures do not fit in main memory on such texts.

#### Compression ratio

It stands for the ratio between the compressed and the original text size, and
it is given as percentage.

Figure 3 shows that RePair outperforms GCIS and the approximations designed
for very large texts, and it is competitive with a basic Lempel-Ziv compressor
such as Gzip. However, it is clearly outperformed by Bzip2, Ppmdj and 7-zip.
The latter displays the best compression ratio overall, being Ppmdj a close
competitor in some cases.

Figure 3. Compression ratio on regular texts.

Figure 4 shows the compression ratios for the repetitive corpora. The
compressors that exploit repetitiveness obtain much better compression ratios
this time, whereas Gzip, Bzip2 and Ppmdj obtain similar compression ratios as
on the regular texts. In particular, 7-zip obtains the best compression ratio
in all cases, closely followed by RePair. The compression ratio of GCIS is
about twice that of RePair in most cases, but it is still very good in
absolute terms and outperforms ReLZ. BigRePair obtains a compression ratio
between those of RePair and GCIS.

Figure 4. Compression ratio on repetitive texts.

The results for the very large texts are depicted in Figure 5. 7-zip is better
for the text enwiki-20191120-20G. The situation stays as in the smaller
repetitive files: BigRePair compresses more than GCIS, and GCIS compresses
better than ReLZ, except for the the chromosome 19 based texts.

Figure 5. Compression ratio on very large texts.

#### Compression speed

Figures 6,7 and 8 show the compression speed, in MB/s, of the compressors for
each text type.

Gzip is the fastest compressor in most regular texts. GCIS is the second-
fastest compressor, followed by Ppmdj. GCIS outperforms Bzip2 and ReLZ and is
faster than the others by a wide margin. In particular, GCIS is typically an
order of magnitude faster than the other grammar compressors (RePair and
BigRePair), which are its direct competitors.

Figure 6. Compression speed on regular texts.

Considering repetitive texts, GCIS is still faster than ReLZ and 7-zip (and
often faster than Bzip2); it is also orders of magnitude faster than RePair.
Gzip is still generally the fastest, but its compression ratio is unacceptable
for repetitive data. BigRePair is also slower than GCIS in most cases and, in
the exceptions where BigRePair is faster, it outperforms GCIS by a small
margin.

Figure 7. Compression speed on repetitive texts.

For very large texts, GCIS is much faster than 7-zip, which becomes the
slowest of the considered compressors. However, ReLZ and BigRePair become much
faster than GCIS, as expected from being designed for this scenario. ReLZ is
clearly the fastest compressor, though its compression ratio is the worst. A
problem for GCIS on these very large files is that, once the text exceeds 2
GiB, it needs to use 64-bit integers, which doubles the memory requirements.
BigRePair and ReLZ do not suffer from this problem and require a small amount
of main memory during compression.

Figure 8. Compression speed on very large texts.

#### Decompression speed

Figure 9 depicts the results for regular texts. Gzip and RePair are the
fastest at decompressing, followed by 7-zip and GCIS. Bzip2 and BigRePair are
the slowest decompressors.

Figure 9. Decompression speed on regular texts.

Figure 10 shows that the situation is similar on repetitive texts, except that
7-zip becomes way faster than the others in almost all cases. Despite the
relative differences, in absolute terms GCIS is still fast, decompressing the
files in around 5 MB/s.

Figure 10. Decompression speed on repetitive texts.

The situation stays the same on the compressors that run on very large texts:
as shown in Figure 11, 7-zip is the fastest, followed by GCIS and then by
BigRePair.

Figure 11. Decompression speed on very large texts.

#### Peak memory

We evaluated the peak memory consumption (resident size) of all compressors
during compression and decompression for each type of text; the results are
shown in Figures 12 to 17. Overall, Gzip, Bzip2 and Ppmdj require negligible
space to compress or decompress. On regular texts, considering compression,
GCIS is followed by ReLZ, 7-zip, BigRePair and RePair, the last being behind
by a large margin. The situation is reversed in decompression: BigRePair is
followed by RePair, 7-zip, and GCIS. On repetitive texts, the scenario is
similar for compression, but GCIS escorts BigRePair. On very large texts,
during compression ReLZ is the most space-efficient, followed by BigRePair,
7-zip and lastly by GCIS. Considering decompression the order stays the same,
except for ReLZ, which does not decompress.

Figure 12. Peak memory (in MB) used by the compressors during compression for
regular texts. Figure 13. Peak memory (in MB) used by the compressors during
compression for repetitive texts. Figure 14. Peak memory (in MB) used by the
compressors during compression for very large texts. Figure 15. Peak memory
(in MB) used by the compressors during decompression for regular texts. Figure
16. Peak memory (in MB) used by the compressors during decompression for
repetitive texts. Figure 17. Peak memory (in MB) used by the compressors
during decompression for very large texts.

###  5.5. Overview

Figures 18 to 20 present conceptual radar charts that summarize, for each text
type, the performance of all compressors in each rated aspect. The closer the
values are to the pentagon borders, the better the compressor performed on the
corresponding aspect.

Figure 18. Compressor comparison on regular texts. Figure 19. Compressor
comparison on repetitive texts. Figure 20. Compressor comparison on very large
texts.

###  5.6. Extract operation

Results depicted by Figures 21 and 22 show that GCIS is faster than the
extractors on succinct encodings of RePair but slower than those running on
the more straightfoward representation using integer arrays. In turn,
regarding space on regular and repetitive texts, GCIS is more space-efficient
than the straightfoward encodings but less space-efficient than the POSLP
alternatives, as shown in Figures 23 and 24. GCIS is then a competitive
alternative regarding the space-time trade-off.

Figure 21. Substring length _vs._ extraction time (microseconds) on regular
texts.

Figure 22. Substring length _vs._ extraction time (microseconds) on repetitive
texts. Figure 23. Compression ratio of the extractors on regular texts. Figure
24. Compression ratio of the extractors on repetitive texts.

###  5.7. Suffix Array and LCP Construction

Considering the computation of $\mathsf{SA}$ and $\mathsf{LCP}$ arrays during
decompression, we measured the total time to decompress the files with GCIS
without generating a plain-text file, but instead inducing the $\mathsf{SA}$
and the $\mathsf{LCP}$ arrays. We compared these results with SAIS (Kurpicz,
2015) and divsufsort (Kurpicz, 2016; Fischer and Kurpicz, 2017)
implementations based on those of Yuta Mori, which are known as the fastest
suffix array construction algorithms in practice.

Figure 25 shows the $\mathsf{SA}$ and $\mathsf{LCP}$ construction on the $8$
most repetitive real texts when only the GCIS compressed texts are available.
Very large texts were not considered because the implementations of (Kurpicz,
2015) and (Kurpicz, 2016) only deal with 32-bit integers. GCIS builds the
$\mathsf{SA}$ and $\mathsf{LCP}$ arrays faster than decompressing and then
using the suffix array construction algorithms over the plain text.

The hatched part corresponds to the $\mathsf{LCP}$ computation and the black
bar corresponds to the time spent in decompressing the text with GCIS to
calculate $\mathsf{SA}$ and $\mathsf{LCP}$ values using the SAIS and
divsufsort implementations.

Figure 25. Time consumed during Suffix Array and LCP construction.

##  6\. Conclusions

We have introduced GCIS, a new grammar-based compression algorithm based on
the induced suffix sorting framework of SAIS (Nong et al., 2009). GCIS uses
the meta-symbols introduced by SAIS to generate non-terminals of a balanced
grammar that reproduces the original text. Our experiments on repetitive texts
show that GCIS compresses $3$–$7$ times faster than RePair and 7-zip. Compared
to RePair, the grammar compressor that compresses the most, GCIS compresses
using $3$–$5$ times less memory, yet it obtains a compressed file twice as
large (yet the absolute compression is still attractive, below $5\%$ in most
cases). GCIS decompresses $2$–$8$ times slower than RePair and 7-zip, though.

Grammar-based compression is attractive because, unlike Lempel-Ziv, it can be
enriched to support fast extraction of arbitrary text substrings. From this
perspective and regarding the space-time relation, our experiments show that
GCIS is a competitive option when compared to RePair-based extractors, being
faster and less space-efficient than the succinct encoding of RePair
extractors and slower, but more space-efficient, than the more
straightforwardly encoded RePair extractors.

Finally, as a by-product of GCIS, the suffix array of the text can be obtained
during the decompression algorithm, faster than decompressing and running on
the original text.

All previously discussed features make GCIS especially attractive in scenarios
where it is required to support random access on the compressed text. Grammar
compression of very large files is challenging with RePair because of its
large main memory footprint, for which GCIS offers an interesting alternative.
Given its slowness at decompression, the GCIS grammar is best suited as a
compressed data structure to be repeatedly accessed without decompressing it
completely. A possible further improvement would be to replace the variant of
Nong et al. (2009) used during compression by the more space-efficient SACA-K
(Nong, 2013) algorithm. This could decrease the working space used during
compression. Grammar-based compressed indexes are of particular interest, all
of which are based on RePair (Claude and Navarro, 2010, 2012). Our next goal
is to build those compressed indexes on GCIS instead. This would yield indexes
that might be built much faster, using much less memory, for moderate-sized
repetitive texts, and that may lead to much more efficient search times.

###### Acknowledgements.

Part of the research of DSNN was performed during visits at University of
Chile and supported by FAP-DF, grants 13619.54.33621.1708/2016 and
0193.001380/2017. FAL was supported by the grant 2017/09105-0 from the São
Paulo Research Foundation (FAPESP). MAR was supported by FAP-DF and CNPq,
grants DE 193.001.369/2016 and PQ 307672/2017-4. GN was funded by Basal Funds
FB0001 and Fondecyt Grant 1-200038, Conicyt, Chile.

## References

  * (1)
  * Anh and Moffat (2010) Vo Ngoc Anh and Alistair Moffat. 2010.  Index compression using 64-bit words.  _Softw., Pract. Exper._ 40, 2 (2010), 131–147.
  * Bille et al. (2015) Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, and Oren Weimann. 2015\.  Random Access to Grammar-Compressed Strings and Trees.  _SIAM J. Comput._ 44, 3 (2015), 513–539.
  * Brisaboa et al. (2013) Nieves R. Brisaboa, Susana Ladra, and Gonzalo Navarro. 2013\.  DACs: Bringing direct access to variable-length codes.  _Inf. Process. Lett._ 49, 1 (2013), 392–404.
  * Burrows and Wheeler (1994) Michael Burrows and David J. Wheeler. 1994.  _A block-sorting lossless data compression algorithm_.  Technical Report. Digital SRC Research Report. 1–18 pages.
  * Charikar et al. (2005) Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, and abhi shelat. 2005.  The smallest grammar problem.  _IEEE Transactions on Information Theory_ 51, 7 (2005), 2554–2576.
  * Claude and Navarro (2010) Francisco Claude and Gonzalo Navarro. 2010.  Self-Indexed Grammar-Based Compression.  _Fundamenta Informaticae_ 111, 3 (2010), 313–337.
  * Claude and Navarro (2012) Francisco Claude and Gonzalo Navarro. 2012.  Improved Grammar-Based Compressed Indexes. In _Proc. 19th International Symposium on String Processing and Information Retrieval (SPIRE)_ _(LNCS 7608)_. Springer, Heidelberg, 180–192.
  * Consortium (2009) Genome Reference Consortium. 2009\.  Genome Reference Consortium Human Reference 37.  http://hgdownload.cse.ucsc.edu/goldenpath/hg19/chromosomes/.  Accessed: 06/2020.
  * Deorowicz (2003) Sebastian Deorowicz. 2003\.  Silesia Corpus.  http://sun.aei.polsl.pl/~sdeor/index.php?page=silesia.  Accessed: 06/2020.
  * Dhaliwal et al. (2012) Jasbir Dhaliwal, Simon J. Puglisi, and Andrew Turpin. 2012\.  Trends in Suffix Sorting: A Survey of Low Memory Algorithms. In _Proc. Australasian Computer Science Conference (ACSC)_. Australian Computer Society Inc., Sydney, 91–98.
  * Ferragina and Navarro (2005a) Paolo Ferragina and Gonzalo Navarro. 2005a.  Pizza-Chili Corpus.  http://pizzachili.dcc.uchile.cl/texts.html.  Accessed: 06/2020.
  * Ferragina and Navarro (2005b) Paolo Ferragina and Gonzalo Navarro. 2005b.  Pizza-Chili Repetitive Corpus.  http://pizzachili.dcc.uchile.cl/repcorpus.html.  Accessed: 06/2020.
  * Fischer (2011) Johannes Fischer. 2011\.  Inducing the LCP-Array. In _Proc. Workshop on Algorithms and Data Structures (WADS)_ _(Lecture Notes in Computer Science)_ , Vol. 6844. Springer, Berlin, Heildelberg, 374–385.
  * Fischer and Kurpicz (2017) Johannes Fischer and Florian Kurpicz. 2017.  Dismantling DivSufSort. In _Proceedings of the Prague Stringology Conference_. Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, 62–76.
  * Gagie et al. (2020) Travis Gagie, Tomohiro I, Giovanni Manzini, Gonzalo Navarro, Hiroshi Sakamoto, Louisa Seelbach Benkner, and Yoshimasa Takabatake. 2020\.  Practical Random Access to SLP-Compressed Texts. (2020).  Accepted short paper, SPIRE.
  * Gagie et al. (2019) Travis Gagie, Tomohiro I, Giovanni Manzini, Gonzalo Navarro, Hiroshi Sakamoto, and Yoshimasa Takabatake. 2019.  Rpair: Scaling up RePair with Rsync. In _Proc. 26th International Symposium on String Processing and Information Retrieval (SPIRE)_ _(Lecture Notes in Computer Science)_ , Vol. 11811. Springer-Verlag, Berlin, Heildeberg, 35–44.
  * Gailly and Adler (2017) Jean-Loup Gailly and Mark Adler. Accessed: 3/2017.  The gzip home page.  http://www.gzip.org/.
  * Gog et al. (2014) Simon Gog, Timo Beller, Alistair Moffat, and Matthias Petri. 2014\.  From Theory to Practice: Plug and Play with Succinct Data Structures. In _Proc. Symposium on Experimental and Efficient Algorithms (SEA)_ _(Lecture Notes in Computer Science)_ , Vol. 8504. Springer, Cham., 326–337.
  * Gog and Ohlebusch (2011) Simon Gog and Enno Ohlebusch. 2011.  Fast and Lightweight LCP-Array Construction Algorithms. In _Proc. Workshop on Algorithm Engineering and Experimentation (ALENEX)_. ACM Digital Library, US, 25–34.
  * Gonnet et al. (1992) Gaston H. Gonnet, Ricardo A. Baeza-Yates, and Tim Snider. 1992.  New Indices for Text: PAT Trees and PAT Arrays.  In _Information Retrieval_. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 66–82.
  * Goto and Bannai (2014) Keisuke Goto and Hideo Bannai. 2014.  Space Efficient Linear Time Lempel-Ziv Factorization for Small Alphabets. In _Proc. IEEE Data Compression Conference (DCC)_. IEEE, NY, 163–172.
  * I (2020) Tomohiro I. 2020\.  Shaped SLP implementation .  https://github.com/itomomoti/ShapedSlp.  Accessed: 08/2020.
  * Itoh and Tanaka (1999) Hideo Itoh and Hozumi Tanaka. 1999.  An Efficient Method for in Memory Construction of Suffix Arrays. In _Proc. International Symposium on String Processing and Information Retrieval (SPIRE)_. IEEE, NY, 81–88.
  * Kärkkäinen et al. (2013) Juha Kärkkäinen, Dominik Kempa, and Simon J. Puglisi. 2013\.  Linear Time Lempel-Ziv Factorization: Simple, Fast, Small. In _Proc. Annual Symposium on Combinatorial Pattern Matching (CPM)_ _(Lecture Notes in Computer Science)_ , Vol. 7922. Springer, Berlin, Heidelberg, 189–200.
  * Kärkkäinen et al. (2009) Juha Kärkkäinen, Giovanni Manzini, and Simon J. Puglisi. 2009.  Permuted Longest-Common-Prefix Array. In _Proc. Annual Symposium on Combinatorial Pattern Matching (CPM)_ _(Lecture Notes in Computer Science)_ , Vol. 5577. Springer, Berlin, Heidelberg, 181–192.
  * Kieffer and Yang (2000) John C. Kieffer and En-Hui Yang. 2000.  Grammar-based codes: A new class of universal lossless source codes.  _IEEE Transactions on Information Theory_ 46, 3 (2000), 737–754.
  * Ko and Aluru (2003) Pang Ko and Srinivas Aluru. 2003.  Space efficient linear time construction of suffix arrays. In _Proc. Annual Symposium on Combinatorial Pattern Matching (CPM)_ _(Lecture Notes in Computer Science)_ , Vol. 2676. Springer, Berlin, Heidelberg, 200–210.
  * Kosolobov et al. (2020) Dmitry Kosolobov, Daniel Valenzuela, Gonzalo Navarro, and Simon J. Puglisi. 2020.  Lempel-Ziv like parsing in small space. (2020).  https://doi.org/10.1007/s00453-020-00722-6 Available On line and to appear in Algorithmica.
  * Kurpicz (2015) Florian Kurpicz. 2015\.  Sais-lite suffix and LCP arrays construction algorithm.  https://github.com/kurpicz/sais-lite-lcp.  Accessed: 06/2020.
  * Kurpicz (2016) Florian Kurpicz. 2016\.  Divsufsort suffix and LCP arrays construction algorithm.  https://github.com/kurpicz/libdivsufsort.  Accessed: 06/2020.
  * Larsson and Moffat (1999) [N.] Jesper Larsson and Alistair Moffat. 1999.  Offline Dictionary-Based Compression. In _Proc. IEEE Data Compression Conference (DCC)_. IEEE, NY, 296–305.
  * Liu et al. (2016) Weijun Liu, Ge Nong, Wai Hong Chan, and Yi Wu. 2016\.  Improving a lightweight LZ77 computation algorithm for running faster.  _Softw. Pract. Exp._ 46, 9 (2016), 1201–1217.
  * Louza et al. (2017a) Felipe A. Louza, Simon Gog, and Guilherme P. Telles. 2017a.  Inducing enhanced suffix arrays for string collections.  _Theor. Comput. Sci._ 678 (2017), 22–39.
  * Louza et al. (2017b) Felipe A. Louza, Simon Gog, and Guilherme P. Telles. 2017b.  Optimal suffix sorting and LCP array construction for constant alphabets.  _Inf. Process. Lett._ 118 (2017), 30–34.
  * Mahoney (2006) Matt Mahoney. 2006\.  Large Text Compression Benchmark.  http://mattmahoney.net/dc/text.html.  Accessed: 06/2020.
  * Manber and Myers (1993) Udi Manber and Eugene W. Myers. 1993.  Suffix Arrays: A New Method for On-Line String Searches.  _SIAM J. Comput._ 22, 5 (1993), 935–948.
  * Manzini (2003) Giovani Manzini. 2003\.  Manzini’s Lightweight Corpus.  http://people.unipmn.it/~manzini/lightweight/.  Accessed: 06/2020.
  * Maruyama and Tabei (2013) Shirou Maruyama and Yasuo Tabei. 2013.  Fully Online Grammar Compression in Constant Space. In _Proc. IEEE Data Compression Conference (DCC)_. IEEE, NY, 173–182.  https://doi.org/10.1109/DCC.2014.69
  * Mori (2008) Yuta Mori. 2008\.  Divsufsort suffix array construction algorithm.  https://github.com/y-256/libdivsufsort.  Accessed: 06/2020.
  * Mori (2010) Yuta Mori. 2010\.  Sais-lite suffix sorting algorithm.  https://sites.google.com/site/yuta256/sais.  Accessed: 06/2020.
  * NCBI (2007) NCBI. 2007.  Salmonella enterica subsp. enterica serovar Paratyphi B str. SPB7, complete sequence.  https://www.ncbi.nlm.nih.gov/nuccore/NC_010102.  Accessed: 06/2020, NCBI Reference Sequence: NC 010102.1.
  * NCBI (2020) NCBI. 2020.  Severe acute respiratory syndrome coronavirus 2 isolate Wuhan-Hu-1, complete genome.  https://www.ncbi.nlm.nih.gov/nuccore/NC_045512.  Accessed: 06/2020, NCBI Reference Sequence: NC 045512.2.
  * Nong (2013) Ge Nong. 2013.  Practical linear-time O(1)-workspace suffix sorting for constant alphabets.  _ACM Trans. Inform. Syst._ 31, 3 (2013), 1–15.
  * Nong et al. (2009) Ge Nong, Sen Zhang, and Wai H. Chan. 2009.  Linear Suffix Array Construction by Almost Pure Induced-Sorting. In _Proc. IEEE Data Compression Conference (DCC)_. IEEE, NY, 193–202.
  * Nong et al. (2011) Ge Nong, Sen Zhang, and Wai H. Chan. 2011.  Two Efficient Algorithms for Linear Time Suffix Array Construction.  _IEEE Trans. Comput._ 60, 10 (2011), 1471–1484.
  * Nunes et al. (2018) Daniel Saad Nogueira Nunes, Felipe Alves da Louza, Simon Gog, Mauricio Ayala-Rincón, and Gonzalo Navarro. 2018.  A Grammar Compression Algorithm Based on Induced Suffix Sorting. In _Proc. IEEE Data Compression Conference (DCC)_. IEEE, NY, 42–51.
  * Ohlebusch and Gog (2011) Enno Ohlebusch and Simon Gog. 2011.  Lempel-Ziv Factorization Revisited. In _Proc. Annual Symposium on Combinatorial Pattern Matching (CPM)_ _(Lecture Notes in Computer Science)_ , Vol. 6661. Springer, Berlin, Heidelberg, 15–26.
  * Okanohara and Sadakane (2009) Daisuke Okanohara and Kunihiko Sadakane. 2009.  A Linear-Time Burrows-Wheeler Transform Using Induced Sorting. In _Proc. International Symposium on String Processing and Information Retrieval (SPIRE)_ _(Lecture Notes in Computer Science)_ , Vol. 5721. Springer, Berlin, Heidelberg, 90–101.
  * Pavlov (2017) Igor Pavlov. Accessed: 10/2017.  The 7zip home page.  http://www.7-zip.org/.
  * Puglisi et al. (2007) Simon J. Puglisi, William F. Smyth, and Andrew H. Turpin. 2007.  A taxonomy of suffix array construction algorithms.  _ACM Comp. Surv._ 39, 2 (2007), 1–31.
  * Seward (1996) Julian Seward. 1996\.  The bzip home page.  http://www.bzip.org/.  Accessed: 3/2017.
  * Shkarin (2006) Dmitry Shkarin. 2006\.  PPMd algorithm variant j revision 1.  http://www.compression.ru/ds/.  Accessed: 07/2020.
  * Trigell (1998) Andrew Trigell. 1998\.  Andrew Trigell’s Large Corpus.  https://www.samba.org/ftp/tridge/large-corpus/.  Accessed: 06/2020.
  * Vigna (2013) Sebastiano Vigna. 2013\.  Quasi-succinct indices. In _Sixth ACM International Conference on Web Search and Data Mining, WSDM 2013, Rome, Italy, February 4-8, 2013_. ACM Digital Library, US, 83–92.
  * Wan (2014) Raymond Wan. 2014\.  Offline Dictionary-based Compression (RePair, Recursive Pairing) .  https://github.com/rwanwork/Re-Pair.  Accessed: 06/2020.
  * Wikipedia (2019) Wikipedia. 2019\.  Wikipedia’s Pages and Articles XML Dump.  http://wikipedia.c3sl.ufpr.br/enwiki/20191120/.  Accessed: 06/2020.
  * Witten et al. (1999) Ian H Witten, Alistair Moffat, and Timothy C. Bell. 1999\.  _Managing Gigabytes (2nd Ed.): Compressing and Indexing Documents and Images,_.  Morgan Kaufmann, San Francisco CA.
  * Ziv and Lempel (1977) Jacob Ziv and Abraham Lempel. 1977.  A universal algorithm for sequential data compression.  _IEEE Transactions on Information Theory_ 23, 3 (1977), 337–343.