A Succinct Grammar Compression\thanks{ This study was supported by KAKENHI(23680016,24700140) and JST PRESTO program. }
We solve an open problem related to an optimal encoding of a {\em straight line program} (SLP), a canonical form of grammar compression deriving a single string deterministically. We show that an information-theoretic lower bound for representing an SLP with $n$ symbols requires at least $2n+\log n!+o(n)$ bits. We then present a succinct representation of an SLP; this representation is asymptotically equivalent to the lower bound. The space is at most $2n\log\rho(1+o(1))$ bits for $\rho \leq 2\sqrt{n}$, while supporting random access to any production rule of an SLP in $O(\log\log n)$ time. In addition, we present a novel dynamic data structure associating a digram with a unique symbol. Such a data structure is called a {\em naming function} and has been implemented using a hash table that has a space-time tradeoff. Thus, the memory space is mainly occupied by the hash table during the development of production rules. Alternatively, we build a dynamic data structure for the naming function by leveraging the idea behind the {\em wavelet tree}. The space is strictly bounded by $2n\log n(1+o(1))$ bits, while supporting $O(\log n)$ query and update time.
main.tex
\documentclass[10pt]{llncs}
\usepackage[dvips]{graphicx}
\usepackage{latexsym,tabularx}
\usepackage{amsmath,amssymb}
\usepackage{url}
%\usepackage[margin=1.0in]{geometry}
%\usepackage[left=3cm,right=3cm,top=2.54cm,bottom=2.54cm]{geometry}

\newtheorem{fact}{{\em Fact}}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}

\begin{document}

\title{
A Succinct Grammar Compression\thanks{
This study was supported by KAKENHI(23680016,24700140) and JST PRESTO program.
}
}

%\author{}
%\institute{}
\author{
Yasuo Tabei\inst{1}, 
Yoshimasa Takabatake\inst{2}, and
Hiroshi Sakamoto\inst{2,3}
}
\institute{
%ERATO Minato Project, Japan Science and Technology Agency, Sapporo, Japan.
ERATO Minato Project, JST, Japan
\and
Kyushu Institute of Technology, Japan
\and PRESTO, JST, Japan\\
\email{
tabei.y.aa@m.titech.ac.jp,
\{takabatake, hiroshi\}@donald.ai.kyutech.ac.jp}
}

\maketitle

\begin{abstract}
We solve an open problem related to an optimal encoding of 
a {\em straight line program} (SLP), a canonical form of grammar compression
deriving a single string deterministically.
We show that an information-theoretic lower bound for representing an SLP with $n$ symbols 
requires at least $2n+\log n!+o(n)$ bits. 
We then present a succinct representation of an SLP; this representation is asymptotically equivalent to the lower bound.
The space is at most $2n\log\rho(1+o(1))$ bits for $\rho \leq 2\sqrt{n}$, while supporting random access to any production rule of 
an SLP in $O(\log\log n)$ time.
In addition, we present a novel dynamic data structure associating a digram with a unique symbol.
Such a data structure is called a {\em naming function} and has been implemented using a hash table that has a space-time tradeoff.
Thus, the memory space is mainly occupied by the hash table during the development of production rules.
Alternatively, we build a dynamic data structure for the naming function by leveraging the idea behind the {\em wavelet tree}.
The space is strictly bounded by $2n\log n(1+o(1))$ bits, while supporting $O(\log n)$ query and update time.
\end{abstract}

\section{Introduction}
Grammar compression has been an active research area since at least the seventies.
The problem consists of two phases: 
(i) building the smallest\footnote{This is almost equal to minimizing the number of variables in $G$.} 
context-free grammar (CFG) generating an input string uniquely 
and (ii) encoding an obtained CFG as compactly as possible. 

The phase (i) is known as an NP-hard problem which can not be approximated 
within a constant factor~\cite{Lehman-Shelat02}.
Therefore, many researchers have made considerable efforts to design grammar compressions 
achieving better approximation results in the last decade.
Charikar et al.~\cite{Charikar05} and Rytter~\cite{Rytter03} independently 
proposed the first $O(\log\frac{u}{g})$-approximation algorithms based on balanced 
grammar construction for the length $u$ of a string and the size $g$ of the smallest CFG. 
Later, Sakamoto~\cite{Sakamoto05} also developed an $O(\log\frac{u}{g})$-approximation algorithm 
based on an idea called pairwise comparison. 
In particular, Lehman~\cite{Lehman-Shelat02} proved that LZ77~\cite{LZ77} 
achieved the best approximation of $O(\log{n})$ under the condition of an unlimited window size.
Since the minimum {\em addition chain} problem is a special case of the problem 
of finding the smallest CFG~\cite{LehmanPhD}, modifying the approximation algorithms proposed so far is a difficult problem. 
Thus, the problem of grammar compression is pressing in the phase (ii). 

A straight line program (SLP) is a canonical form of a CFG, 
and has been used in many grammar compression algorithms~\cite{LZ78,Larsson00,LZ77,Apostolico00,ESP}.
The production rules in SLPs are in Chomsky normal form 
where the right hand side of a production rule in CFGs is a {\em digram}: a pair of symbols.
Thus, if $n$ symbols are stored in an array called a {\em phrase dictionary} 
consisting of $2n$ fixed-length codes each of which is represented by $\log{n}$ bits, 
the memory of the dictionary is $2n \log{n}$ bits, resulting in the memory for storing an input string usually being exceeded.
Although directly addressable codes achieving entropy bounds on strings whose memory consumption is the same as that of the fixed-length codes in the worst case have been presented~\cite{ferragina2007simple,sadakane2006squeezing,gonzalez2006statistical}, 
there are no codes that achieve an information-theoretic lower bound of storing an SLP in a phrase dictionary.
Since a nontrivial information-theoretic lower bound of directly addressable codes for a phrase dictionary remains unknown, 
establishing the lower bound and developing novel codes for optimally representing an SLP are challenges.
%Although one can use Huffman codes for encoding dictionaries, they are neither directly addressable nor decomposable, 
%Since such addressability and decomposability are necessary for practical grammar compressions,
%developing a novel phrase dictionary with such properties is a challenging issue.

We present an optimal and directly addressable SLP within a strictly bounded memory close to 
the amount of a plain representation of the phrase dictionary.
We first give an information-theoretic lower bound on the problem of encoding an SLP, 
which has been unknown thus far. 
Let $C$ be a class of objects.
Representing an object $c \in C$ requires at least $\log|C|$ bits.
%Let $L(c)$ be the information-theoretical minimum bits to represent an object $c$.
A representation of $c$ is succinct if it requires at most $\log{|C|}(1+o(1))$ bits.
Considering the facts and the characteristics of SLPs indicated in \cite{ESP}, 
one can predict that the lower bound for the class of SLPs with $n$ symbols 
would be between $2n$ and $4n+\log{n!}$. 
By leveraging this prediction, we derive that a lower bound of bits to represent SLPs is $2n+\log{n!}$.

We then present an almost optimal encoding of SLPs based on
{\em monotonic subsequence decomposition} of a sequence.
Any permutation of $[1,n]$ is decomposable into at most $\rho \leq 2\sqrt{n}$
monotonic subsequences in $O(n^{1.5})$ time~\cite{Yehuda1998} and
there is a $1.71$-approximation\footnote{Minimizing $\rho$ is NP-hard.} 
algorithm in $O(n^3)$ time~\cite{Fomin2002}. 
While the previous encoding method for SLPs presented in~\cite{Takabatake2012} 
is also based on the decomposition, the size is not asymptotically equal
to the lower bound when $\rho \simeq \sqrt{n}$.
We improve the data structure by using the {\em wavelet tree} (WT)~\cite{Grossi03} and its improved results~\cite{Jeremy2010,Golynski2006} such that
our novel data structure achieves the smaller bound of $\min\{2n+n\log n +o(1),2n\log\rho(1+o(1))\}$ 
bits for any SLP with $n$ symbols while supporting $O(\log\log\rho)$ access time.
Our method is applicable to any types of algorithm generating SLPs
including Re-Pair~\cite{Larsson00} and an online algorithm called LCA~\cite{Maruyama2012}.
Barbay et al.~\cite{Barbay2009} presented a succinct representation of a sequence using the monotonic subsequence decomposition. 
Their method uses the representation of an integer function built on a succinct representation of integer ranges. 
%Related to our study, other encoding based on the monotonic subsequence decomposition 
%was proposed in~\cite{Barbay2009}, where
%they proposed a succinct representation for a permutation of a range of integers, and
%applied it to the representation of an integer function.
Its size is estimated to be the {\em degree entropy} of an ordered tree~\cite{Jansson2012-JCSS}.

Another contribution of this paper is to present a dynamic data structure for checking whether or not a production rule in a CFG has been generated in execution. 
Such a data structure is called a {\em naming function}, and is also necessary for practical grammar compressions. 
When the set of symbols is static, we can construct a perfect hash as a naming function in linear time, which achieves 
an amount of space within around a factor of 2 from the information-theoretical minimum~\cite{Botelho2007}.
However, variables of SLPs are generated step by step in grammar compression.
While the function can be dynamically computed by a randomization~\cite{Karp87} or
a deterministic solution~\cite{Karp72} in $O(1)$ time and linear space,
a hidden constant in the required space was not clear.
We present a dynamic data structure to compute function values in $O(\log n)$ query time
and update time. The space is strictly bounded by $2n\log n(1+o(1))$ bits.

\section{Preliminaries}

\subsection{Grammar compression}
For a finite set $C$, $|C|$ denotes its cardinality.
{\em Alphabet} $\Sigma$ is a finite set of letters and $\sigma=|\Sigma|$ is a constant. 
$\cal X$ is a recursively enumerable set 
of {\em variables} with $\Sigma\cap \cal{X}=\emptyset$.
A sequence of symbols from $\Sigma\cup \cal{X}$ is called a string.
The set of all possible strings from $\Sigma$ is denoted by $\Sigma^*$.
For a string $S$, the expressions $|S|$, $S[i]$, and $S[i,j]$ 
denote the length of $S$, the $i$-th symbol of $S$,
and the substring of $S$ from $S[i]$ to $S[j]$, respectively.
Let $[S]$ be the set of symbols composing $S$.
A string of length two is called a {\em digram}.

A CFG is represented by ${\cal G}=(\Sigma,V,P,X_s)$ 
where $V$ is a finite subset of $\cal X$, $P$ is a finite subset of 
$V\times (V\cup\cal{X})^*$, and $X_s\in V$.
A member of $P$ is called a production rule and $X_s$ is called the start symbol.
The set of strings in $\Sigma^*$ derived from $X_s$ by ${\cal G}$ is 
denoted by $L({\cal G})$.

A CFG ${\cal G}$ is called {\em admissible} if exactly one $X\to \alpha\in P$ exists and $|L({\cal G})|=1$.
An admissible ${\cal G}$ deriving $S$ is called a grammar compression of $S$ for any $X\in V$.

We consider only the case $|\alpha|=2$ for any production rule $X\to \alpha$
because any grammar compression with $n$ variables can be transformed into 
such a restricted CFG with at most $2n$ variables.
Moreover, this restriction is useful for practical applications of compression algorithms, e.g.,
LZ78~\cite{LZ78}, REPAIR~\cite{Larsson00}, and LCA~\cite{Maruyama2012},
and indices, e.g., SLP~\cite{Claude09} and ESP~\cite{Maruyama2011}.


The derivation tree of $G$ is represented by a rooted ordered binary tree
such that internal nodes are labeled by variables in $V$ and
the {\em yields}, i.e., the sequence of labels of leaves is equal to $S$.
In this tree, any internal node $Z\in V$ has 
a left child labeled $X$ and a right child labeled $Y$, which 
corresponds to the production rule $Z\to XY$.

If a CFG is obtained from any other CFG by a permutation 
$\pi:\Sigma\cup V\to \Sigma\cup V$, they are identical to each other
because the string derived from one is transformed to 
that from the other by the renaming.
For example, $P=\{Z\to XY,Y\to ab,X\to aa\}$ and
$P'=\{X\to YZ,Z\to ab,Y\to aa\}$ are identical each other.
On the other hand, they are clearly different from 
$P''=\{Z\to aY,Y\to bX,X\to aa\}$ because their depths are different.
Thus, we assume the following canonical form of CFG called 
{\em straight line program} (SLP).

\begin{definition}\label{SLP}(Karpinsk-Rytter-Shinohara~\cite{SLP})
An SLP is a grammar compression over $\Sigma\cup V$ 
whose production rules are formed by either 
$X_i\to a$ or $X_k\to X_iX_j$, where $a\in\Sigma$ and $1\leq i,j < k\leq |V|$.
%% An SLP is a grammar compression defined by $\Sigma\cup V$ with 
%% $V=\{X_1,X_2,\ldots,X_m\})$ that derives the string in $\Sigma^*$ 
%% by the following two types of production rules: 
%% $X_i\to a$ and $X_k\to X_iX_j$, where $a\in\Sigma$ and $1\leq i,j < k\leq n$.
\end{definition}


\subsection{Phrase/reverse dictionary}
For a set $P$ of production rules,
a {\em phrase dictionary} $D$ is a data structure for directly accessing
 the phrase $X_iX_j$ for any $X_k\in V$ if $X_k\to X_iX_j \in P$.
Regarding a triple $(k,i,j)$ of positive integers as $X_k\to X_iX_j$, 
we can store the phrase dictionary consisting of $n$ variables in an integer array $D[1,2n]$, 
where $D[2k-1]=D[2k]=0$ if $k$ belongs to an alphabet i.e., $1 \leq k \leq |\Sigma|$. 
$X_i$ and $X_j$ are accessible as $D[2k-1]$ and $D[2k]$ by indices $2k-1$ and $2k$ for $X_k$, 
respectively. 
A plain representation of $D$ using fixed-length codes requires $2n\log n$ bits of space to store 
$n$ production rules.

Reverse dictionary $D^{-1}$ is a data structure for directly accessing the variable $X_k$ 
given $X_iX_j$ for a production rule $X_k\to X_iX_j \in P$. 
Thus, $D^{-1}(X_iX_j)$ returns $X_k$ if $X_k \rightarrow X_iX_j \in P$.
A hash table is a representative data structure for $D^{-1}$ enabling $O(1)$ time access 
and achieving $O(n\log n)$ bits of space. 

\subsection{Rank/select dictionary}
We present a phrase dictionary based on the {\em rank/select dictionary}, 
a data structure for a bit string $B$~\cite{Jacobson89} supporting the following queries:
$\mbox{rank}_c(B,i)$ returns the number of occurrences of $c \in \{0,1\}$ in $B[1,i]$ and 
$\mbox{select}_c(B,i)$ returns the position of the $i$-th occurrence of $c \in \{0, 1\}$ in $B$.
For example, if $B=10110100111$ is given, then $\mbox{rank}_1(S,7)=4$ because the number of $1$s in 
$B[1,7]$ is $4$,
and $\mbox{select}_1(S,5)=9$ because the position of the fifth $1$ in $B$ is $9$.
Although naive approaches require the $O(|B|)$ time to compute a rank, 
several data structures with only the $|B|+o(|B|)$ bit storage to 
achieve $O(1)$ time~\cite{Navarro12,Okanohara07} have been presented. 
Most methods compute a select query by a binary search on a bit string $B$ in $O(\log |B|)$ time. 
A data structure for computing the select query in $O(1)$ time has also been presented~\cite{Ram02}.

\subsection{Wavelet tree}
A WT is a data structure for a string $S \in \Sigma^*$, and 
it can be used to compute the rank and select queries on a string $S$ over an ordinal alphabet 
in $O(\log{\sigma})$ time and $n\log\sigma(1+o(1))$ bits~\cite{Grossi03}.
Data structures supporting the rank and select queries in $O(\log\log{\sigma})$ time 
with the same space have been proposed~\cite{Golynski2006,Jeremy2010}. 
WT also supports $\mbox{access}(S,i)$ which returns $S[i]$ in $O(\log{\sigma})$ time.
Recently, WT has been extended to support various operations on strings~\cite{Navarro2012-cpm}.

A WT for a sequence $S$ over $\Sigma=\{1,...,\sigma\}$ is a binary tree that 
can be, recursively, presented over a sub-alphabet range $[a,b] \subseteq [1,\sigma]$. 
Let $S_v$ be a sequence represented in a node $v$, and let 
$left(v)$ and $right(v)$ be left and right children of node $v$, respectively. 
The root $v_{root}$ represents $S_{root}=S$ over the alphabet range $[1,\sigma]$.
At each node $v$, $S_{v}$ is split into two subsequences $S_{left(v)}$ consisting of 
the sub-alphabet range $[a,\lfloor \frac{(a+b)}{2} \rfloor]$ for $left(v)$ 
and $S_{right(v)}$ consisting of the sub-alphabet range $[\lfloor \frac{(a+b)}{2} \rfloor + 1, b]$ 
for $right(v)$ where $S_{left(v)}$ and $S_{right(v)}$ keep the order of elements in $S_v$. 
The splitting process repeats until $a=b$. 
Each node $v$ in the binary tree contains a rank/select dictionary on a bit string $B_v$. 
Bit $B_v[k]$ indicates whether $S_v[k]$ should be moved to $left(v)$ or $right(v)$. 
If $B_v[k]=0$, $S_{left(v)}$ contains $S_{v}[k]$. 
If $B_v[k]=1$, $S_{right(v)}$ inherits $S_v[k]$. 
Formally, $B_v[k]$ with an alphabet range $[a,b]$ is defined as:
\[
B_v[k] = \left\{ \begin{array}{ll}
1 & \mbox{if} \ S_v[k] > \lfloor (a+b)/2 \rfloor \\ 0 & \mbox{if} \ S_v[k] \le \lfloor
(a+b)/2 \rfloor \end{array}
\right. .
\]

An example of a WT is shown in Figure~\ref{fig:wavelet_tree_ex}.
In this example, since $S_{root}[2]=4$ belongs to the higher half $[3,4]$ of an alphabet range $[1,4]$ represented in the root; therefore, it is the second element of $S_{root}$ that must go to the right child of the root, $B_{root}[2]=1$ and $S_{right(root)}[2]=S_{root}[2]=4$.

\begin{figure*}[t]
\begin{center}
\includegraphics[width=0.4\textwidth]{./fig/wavelet_ex}
\end{center}
\vspace{-0.5cm}
\caption{Example of wavelet tree for a sequence $S=342112243$ over an alphabet $\{1,2,3,4\}$.}
\label{fig:wavelet_tree_ex}
\end{figure*}

%% \begin{itemize}
%% \item $\mbox{rank}_\sigma(S,k)$ is the number of $\sigma$s in $S[1,k]$, and
%% \item $\mbox{select}_\sigma(S,k)$ is the position in $S$ of the $k$-th $\sigma$.
%% \end{itemize}
%For example, if $S=10110100111$, $\mbox{rank}_1(S,7)=4$, 
%because the number of $1$s in $S[1,7]$ is $4$,
%and $\mbox{select}_1(S,5)=9$, because the position of the fifth $1$ in $S$ is $9$.
%When $S$ is a binary string, the time of each query is $O(1)$~\cite{Clark96,Jacobson89,Munro96}.
%An extended dictionary supporting access/rank/select for $S$ from $\sigma$ alphabets
%were introduced by {\em wavelet trees}~\cite{Grossi03}.
%For the wavelet tree, each query time is $O(\log\sigma)$
%and the space is $n\log\sigma(1 + o(1))$ bits.
%If $S$ is static, the query time can be improved to
%$O(\log\log\sigma)$ with the same space~\cite{Golynski2006,Jeremy2010}.

%For latter sections, we review the mechanism of wavelet tree
%for string in $\Sigma^*$, where $\Sigma=\{1,\ldots,\sigma\}$ (see, e.g.,~\cite{Navarro2012-cpm}).
%If necessary, it is easy to extend it to string in $(\Sigma\cup V)^*$.
%A wavelet tree for a string $S[1,n]\in\Sigma^*$ is a binary tree
%with left/right edges labeled $0/1$ defined as follows.
%The range $[1,\sigma]$ is partitioned into two sub-ranges $[1,\lfloor(1+\sigma)/2\rfloor]$ and 
%$[\lfloor(1+\sigma)/2\rfloor+1,\sigma]$, called left/right ranges.
%The root corresponds to the bit-vector ${\cal B}$ such that
%${\cal B}[i]= 0$ if $S[i]$ belongs to the left range, and ${\cal B}[i]= 1$ otherwise.
%By the labeling ${\cal B}$, $S$ is decomposed into two subsequences;
%One is assigned to the left child the other is the right child of the root.
%Sub-range is recursively partitioned and
%the above process is repeated on the left and right subtree,
%until each sub-range contains only a single alphabet.
%We show an example in Figure~\ref{wavelet_tree_ex}.

\section{Succinct SLP}

\subsection{Information-theoretic lower bound}
In this section, we present a tight lower bound to represent SLPs
having a set of production rules $P$ consisting of $n=|\Sigma \cup V|$ symbols.
Each production rule $Z\to XY \in P$ is considered as two directed edges $(Z,X)$ and $(Z,Y)$, 
the SLP can be seen as a directed acyclic graph (DAG) with a single source and $|\Sigma|$ sinks.
Here, we consider $(Z,X)$ as the left edge and $(Z,Y)$ as the right edge.
In addition, $P$ can be considered as a DAG with the single source and 
with a single sink 
by introducing a super-sink $s$ and drawing directed left and right edges from any sink to $s$~(Figure~\ref{fig:dag}). 
Let ${\cal DAG}(n)$ be the set of all possible $G$s with $n$ nodes and 
${\cal DAG}=\bigcup_{n\to\infty}{\cal DAG}(n)$. 
Since two SLPs are identical if an SLP can be converted to the other SLP by 
a permutation $\pi : \Sigma \cup V \rightarrow \Sigma \cup V$,
the number of different SLPs is $|{\cal DAG}(n)|$.
Any internal node of $G \in {\cal DAG}(n)$ has exactly two (left/right) edges.
Thus, the following fact remarked in~\cite{Maruyama2011} is true.

\begin{figure*}[t]
\begin{center}
\includegraphics[width=0.9\textwidth]{./fig/dag2}
\end{center}
\vspace{-0.7cm}
\caption{Example of DAG representation of an SLP and its spanning tree decomposition. 
An SLP is represented by a DAG $G$. $G$ is decomposed into the left tree $T_L$ and right tree $T_R$.}
\label{fig:dag}
\end{figure*}

\begin{fact}
An in-branching spanning tree is an ordered tree such that the out-degree of any node 
except the root is exactly one. 
For any in-branching spanning tree of $G$, the graph consisting of the
remaining edges and their adjacent vertices is also an in-branching spanning tree of $G$.
\end{fact}

The in-branching spanning tree consisting of the left edges (respectively the right edges) and their adjacent vertices is called the
{\em left tree} $T_L$ (respectively {\em right tree} $T_R$) of $G$.
Note that the source in $G$ is a leaf of both $T_L$ and $T_R$, and
the super-sink of $G$ is the root of both $T_L$ and $T_R$.
We shall call the operation of decomposing a DAG $G$ into two spanning trees $T_L$ and $T_R$ 
{\em spanning tree decomposition}. 
In Figure~\ref{fig:dag}, the source $x_5$ in $G$ is a leaf of both $T_L$ and $T_R$, and 
the super-sink $s$ in $G$ is the root of both $T_L$ and $T_R$.

Any ordered tree is an elements in ${\cal T}=\bigcup_{n\to\infty}{\cal T}_n$
where ${\cal T}_n$ is the set of all possible ordered trees with $n$ nodes.
As shown in~\cite{Asai2002,Zaki2002}, 
there exists an enumeration tree for ${\cal T}$ such that
any $T\in {\cal T}$ appears exactly once. 
The enumeration tree is defined by the {\em rightmost expansion}, i.e.,
in this enumeration tree, a node $T'\in {\cal T}_{n+1}$, 
which is a child of $T\in {\cal T}_n$, is obtained by adding a rightmost node to $T$.
In our problem, an ordered tree $T\in {\cal T}_{n+1}$ is 
identical to a left tree $T_L$ with $n+1$ nodes for $n=|\Sigma\cup V|$ symbols.

Let $G\oplus (u,v)$ be the DAG obtained by adding the edge $(u,v)$ to a DAG $G$.
If necessary, we write $G\oplus (u,v)_L$ to indicate that
$(u,v)$ is added as a left edge.
For a set $E$ of edges, the DAG $G\oplus E$ is defined analogously.
The DAG $G\oplus E$ is defined as adding all the edges $(u,v) \in E$ to $G$.
The DAG $G\ominus E$ is also defined as deleting all the edges $(u,v) \in E$ from $G$.

\begin{theorem}\label{th1}
The information-theoretic lower bound on the minimum number of bits needed to
represent an SLP with $n$ symbols is $2n + \log n! + o(n)$.
\end{theorem}
\begin{proof}
Let ${\cal S}(n)$ be the set of all possible DAGs with $n$ nodes
and a single source/sink such that any internal node has exactly two children.
This ${\cal S}(n)$ is a super set of ${\cal DAG}(n)$ because
the in-degree of the sink of any DAG in ${\cal DAG}(n)$ must be
exactly $2\sigma$, whereas ${\cal S}(n)$ does not have such a restriction.
By the definition, 
$|{\cal S}(n)|/n^\sigma \leq 
|{\cal DAG}(n)| \leq 
|{\cal S}(n)|$ holds.

Let ${\cal S}(n,T)=\{G\in {\cal S}(n)\mid G=T\oplus T_R,\;T_R\in {\cal T}_n\}$.
We show $|{\cal S}(n,T)|=(n-1)!$ for each $T\in {\cal T}_n$
by induction on $n\geq 1$.
Since the base case $n=1$ is clear, we assume that the induction hypothesis 
is true for some $n\geq 1$.

Let $T'_L$ be the rightmost expansion of $T_L$ such that
the rightmost node $u$ is added as the rightmost child of node $v$ in $T_L$,
and let $G'\in {\cal S}(n+1,T'_L)$ with a left tree $T'_L$. 
By the induction hypothesis,
the number of $G\in {\cal S}(n,T_L)$ is $(n-1)!$
and $T_L$ is embedded into $G$ as the left tree.
Then, $G'$ is constructed by adding the left edge $(u,v)$
and a right edge $(u,x)$ for a node $x$ in $T_L$.

Let $s$ be the source of $G$.
For $v=s$, each $G'=G\oplus (u,v)_L\oplus (u,x)_R\in {\cal S}(n+1,T'_L)$ is admissible,
and the number of them is clearly $n|{\cal S}(n,T_L)|=n!$.
For $v\neq s$, if $x=s$, 
$G'=G\oplus (u,v)_L\oplus (u,x)_R\in {\cal S}(n+1,T'_L)$ is admissible.

Otherwise, there exists the lowest common ancestor $y$ of $s$ and $x$
on $T_R$ with $G=T_L\oplus T_R$.
Let $z$ be the unique child of $y$ and let $p(z',z)$ be the path of $T_R$ 
from $z'$ to $z$, where possibly $s=z$.
If the in-dgree of any node in $p(s,z)$ is at most one in $G$, 
we generate $G' = G\oplus (u,v)_L \oplus (u,x)_R \ominus (z,y)_R \oplus (z,u)_R$.
If $G'$ contains a cycle, it must contain the edge $(z,u)$.
However, there is no such a path because of the condition of $p(s,z)$.
Thus, $G'$ is an admissible DAG in ${\cal S}(n+1,T'_L)$.
Conversely, if some node in $p(s,z)$ is more than two in $G$, let $z'$ be the nearest one from $s$.
Analogously, $G' = G\oplus (u,v)_L \oplus (u,x)_R \ominus (z',z)_R \oplus (z',u)_R$
is an admissible DAG in ${\cal S}(n+1,T'_L)$.

%where $y'$ is the unique child of $y$ in the path from $y$ to $s$ in $T_R$.
In all the cases, the number of such $G'$s is also $n!$ because 
no edge is changed in $T_L$ and the pair $(T'_L,T'_R)$ 
containing the edge $(u,x)_R$ is unique for any fixed $T'_L$.
Thus, $|{\cal S}(n+1,T)|=n!$ is true for each $T\in {\cal T}_{n+1}$.

This result derives $|{\cal S}(n)|=C_n(n-1)!$
where $C_n=\frac{1}{n+1}{2n \choose n}\simeq 2^{2n}n^{-3/2}$
is the number of ordered trees with $n+1$ nodes.
Combining this with 
$|{\cal S}(n)|/n^\sigma \leq 
|{\cal G}(n)| \leq 
|{\cal S}(n)|$ as well,
we get the result that the information-theoretic minimum bits needed to represent
$G\in {\cal DAG}(n)$ is at least $2n + \log n! + o(n)$.
\hspace{\fill}$\Box$
\end{proof}

\subsection{An optimal SLP representation}
\begin{figure}[t]
\begin{center}
\includegraphics[width=0.7\textwidth]{./fig/phasedictionary2}
\end{center}
\vspace{-.5cm}
\caption{
{\bf Encoded phrase dictionary:}
$D$ indicates the remaining sequence $D[2],D[4],\ldots, D[2n]$.
$D$ is encoded by $(D_\rho,D_\pi,{\bf B},{\bf b})$
based on a monotonic decomposition ${\cal S}$ of $D$, i.e.,
each $s\in{\cal S}$ indicates a weakly monotonic subsequence in $D$;
$D_\rho$ is the sequence of $i$ indicating the membership for some $s_i\in{\cal S}$,
$D_\pi$ is a permutation of $D_\rho$ with respect to 
the corresponding value in $D$,
${\bf B}$ is a binary encoding of the sorted $D$ in increasing order.
We show only the case that $D[i]$ is a member of an increasing $s\in{\cal S}$, but 
the other case is similarly computed by ${\bf b}$.
}
\label{dic_enc}
\end{figure}

We present an optimal reresentation of an SLP as an improvement of the data structure recently presented in \cite{Takabatake2012}.
We apply the spanning tree decomposition to the DAG $G$ of a given SLP, and obtain the DAG $T_L \oplus T_R(=G)$.
We rename the variables in $T_L$ by breadth-first order 
and also rename variables in $T_R$ according to the $T_L$.
Let $G^\prime$ be the resulting DAG from $G$. 
Then, for the array representation $D[1,2n]$ of $G'$, we obtain
the condition $D[1]\leq D[3]\leq \ldots \leq D[2n-1]$.
Since this monotonic sequence is encoded by $2n + o(n)$ bits,
$D$ is represented by $2n + n\log n + o(n)$ bits supporting
${\mbox access}(D,k)$ $(1\leq k\leq 2n)$ in $O(1)$ time.
We focus on the remaining sequence of length $n$, i.e., $D[2],D[4],\ldots,D[2n]$.
For simplicity, we write $D$ instead of $[D[2],D[4],\ldots,D[2n]]$. 

Let ${\cal S}=\{s_1,\ldots,s_\rho\}$ be a disjoint set of subsequences of $[1,n]$ such that 
any $i  \in \{1,2,...,n\}$ is contained in some $s_k$ and any $s_i,s_j$ $(i \neq j)$ are disjoint.
Such an ${\cal S}$ is called a decomposition of $D$.
A sequence $D[s_{k_1}],\ldots,D[s_{k_p}]$ is weakly monotonic 
if it is {\em increasing}, i.e., $D[s_{k_1}]\leq\ldots\leq D[s_{k_p}]$ or {\em decreasing}, i.e., $D[s_{k_1}]\geq\ldots\geq D[s_{k_p}]$.
In addition, ${\cal S}$ is called {\em monotonic} if the sequence $D[s_{k_1}],\ldots,D[s_{k_p}]$ is weakly monotonic 
for any $s_k=[s_{k_1},\ldots,s_{k_p}]\in {\cal S}$.

\begin{theorem}\label{th2}
Any SLP with $n$ symbols can be represented using $2n\log\rho(1 + o(1))$ bits
for $\rho\leq 2\sqrt{n}$, while supporting $O(\log\log\rho)$ access time. 
\end{theorem}
\begin{proof}
It is sufficient to prove that any $D$ of length $n$ 
can be represented using $2n\log\rho + o(n)$ bits for some $\rho\leq 2\sqrt{n}$.
By the result in~\cite{Yehuda1998},
we can construct a monotonic decomposition ${\cal S}$ of $D$ such that
$\rho = |{\cal S}| \leq 2\sqrt{n}$.

We represent the sequence $D$ as a four-tuple $(D_\rho,D_\pi,{\bf B},{\bf b})$ using ${\cal S}$.
For each $1\leq p\leq  n$, $D_\rho [p]=k$ iff 
$p$ is a member of $s_k\in {\cal S}$ for some $1\leq k\leq \rho$.
Let $(D[1],D_\rho[1]),\ldots,(D[n],D_\rho[n])$ be the sequence of pairs $(D[p],D_{\rho}[p])$ $(1 \leq p \leq n)$.
We sort these pairs with respect to the keys $D[p]$ $(1 \leq p \leq n)$ and 
obtain the sorted sequence $(D[\ell_1],D_\rho[\ell_1]),\ldots,(D[\ell_n],D_\rho[\ell_n])$. 
We define $D_\pi$ as the permutation $D_\rho[\ell_1]\cdots D_\rho[\ell_n]$. 

${\bf B}\in\{0,1\}^*$ is defined as the bit string
\[{\bf B}
=0^{D[\ell_1]}10^{D[\ell_2]-D[\ell_1]}\cdots1
0^{D[\ell_n]-D[\ell_{n-1}]}1.
\]

Finally, ${\bf b}[k]=0$ if $s_k\in {\cal S}$ is increasing and
${\bf b}[k]=1$ otherwise for $1\leq k\leq \rho$.
$D$ and $D_{\rho}$ are represented by WTs, respectively, and ${\bf B}$ is a rank/select dictionary.

We recover $D[p]$ using $(D_\rho,D_\pi,{\bf B},{\bf b})$.
When $D_\rho[p]=k$ and ${\bf b}[k]=0$, i.e., $D[p]$ is included in the 
$k$-th monotonic subsequence $s_k \in {\cal S}$ that is increasing, 
we obtain 
\[D[p] =
\mbox{rank}_0({\bf B},
\mbox{select}_1({\bf B},\ell)) 
\] 
by $\ell = \mbox{select}_k(
D_\pi,\mbox{rank}_k(D_\rho, p))$.
When $D_\rho[p]=k$ and ${\bf b}[k]=1$, we can similarly obtain $D[p]$ 
replacing $\ell$ by $r = \mbox{select}_k(D_\pi, 
(
\mbox{rank}_k(D_\rho,n)+1 - \mbox{rank}_k(D_\rho,p)
)
)$.

The total size of the data structure formed by $(D_\rho,D_\pi , {\bf B}, {\bf b})$
is at most $2n\log\rho(1+o(1))$ bits. 
The rank/select/access operations of the WT for a static sequence over $\rho\leq 2\sqrt{n}$ symbols 
can be improved to achieve $O(\log\log\rho)$ time for each query~\cite{Jeremy2010,Golynski2006}.
\hspace{\fill}$\Box$
\end{proof}

In Figure~\ref{dic_enc}, for the sequence $(0,1),(1,2),(1,1),(0,2),(4,1)$ of pairs $(D[p],D_{\rho}[p])$ $(1\leq p \leq 5)$, 
the sorted sequence is $(0,1),(0,2),(1,2),(1,1),(4,1)$.
Thus, $D_\pi$ is $12211$. 
${\bf B}=0^010^{(0-0)}10^{(1-0)}10^{(1-1)}10^{(4-1)}1=110110001$.
$b[1]=0$ because $s_1$ is increasing, and $b[2]=1$ because $s_2$ is decreasing.

\section{Data Structure for Reverse Dictionary}

In this section, we present a data structure for simulating 
the naming function $H$ defined as follows.
For a phrase dictionary $D$ with $n$ symbols,
\[
H(X_iX_j)=\left\{
\begin{array}{ll}
D^{-1}(X_iX_j), & \;\; \mbox{if} \;D[k]=X_iX_j \;\mbox{ for some } 1\leq k\leq n, \\
X_{n+1}, & \;\; \mbox{otherwise.}
\end{array}
\right.
\]

For a sufficiently large $V$, 
we set a total order on $(\Sigma\cup V)^2=\{ XY \mid
X,Y\in \Sigma\cup V\}$, i.e., 
the lexicographical order of the $n^2$ digrams.
This order is represented by the range $[1,n^2]$.
Then, we recursively define WT $T_D$ for a phrase dictionary $D$ 
partitioning $[1,n^2]$.
On the root node, the initial range $[1,n^2]$ is partitioned into two parts: a left range
$L[1,\lfloor(1+n^2)\rfloor/2]$ and a right range $R[\lfloor(1+n^2)\rfloor/2+1,n^2]$.
The root is the bit string ${\bf B}$ such that
${\bf B}[i]=0$ if $D[i]\in L$ and ${\bf B}[i]=1$ if $D[i]\in R$.
By this, the sequence of digrams, $D$, is decomposed into two subsequences $D_L$ and $D_R$;
they are projected on the roots of the left and right subtrees, respectively.
Each sub-range is recursively partitioned and 
the subsequence of $D$ on a node is further decomposed
with respect to the partitioning on the node.
This process is repeated until the length of any sub-range is one.
Let ${\bf B}_i$ be the bit string assigned to the $i$-th node
of $T_D$ in the breadth-first traversal.
In Figure~\ref{wavelet_dic}, we show an example
of such a data structure for a phrase dictionary $D$.

\begin{figure}[tb]
\begin{center}
%\includegraphics[width=0.9\textwidth]{./fig/wavelet_dic}
\includegraphics[width=0.8\textwidth]{./fig/wt}
\end{center}
%\vspace{-.5cm}
\caption{
{\bf WT for reverse dictionary:}
The bit string ${\bf B}_i$ is assigned to 
the $i$-th node in breadth-first order.
For each internal node $i$,
we can move to the left child by $\mbox{rank}_0$
and to the right child by $\mbox{rank}_1$ on ${\bf B}_i$.
The upward traversal is simulated by $\mbox{select}_0$
and $\mbox{select}_1$ as shown.
The leaf for an existing digram is represented by $1$
and $null$ is represented by $0$, whereas
these bits are omitted in this figure.
}
%\vspace{-0.5cm}
\label{wavelet_dic}
\end{figure}


\begin{theorem}\label{wavelet-th}
The naming function for phrase dictionary $D$ over $n=|\Sigma\cup V|$ 
symbols can be computed by the proposed data structure $D_T$
in $O(\log n)$ time for any digram.
Moreover, when a digram does not exist in the current $D$,
$D_T$ can be updated in the same time and 
the space is at most $2n\log n(1+o(1))$ bits.
\end{theorem}
\begin{proof}
$D_T$ is regarded as a WT for 
a string $S$ of length $n$ such that any symbol is represented 
in $2\log n$ bits.
Thus, $H(XY)$ is obtained by $\mbox{select}_{XY}(S,1)$.
The query time is bounded by the number of
$\mbox{rank}$ and $\mbox{select}$ operations for bit strings
performed until the operation flow returns to the root.
Since the total range is $[1,n^2]$, i.e., the height of $T_D$ is at most $2\log n$,
the query time and the size are derived.
When $XY$ does not exist in $D$,
let $i_1,i_2,\ldots,i_k$ be the sequence of traversed nodes from the root $i_1$ to
a leaf $i_k$ and let ${\bf B}_{i_j}$ be the bit string on $i_j$. 
Given an access/rank/select dictionary for ${\bf B}_{i_j}$,
we can update it for ${\bf B}_{i_j}b$ and $b\in\{0,1\}$ in $O(1)$ time.
Therefore, the update time of $T_D$ for any digram is $O(k)=O(\log n)$.
\hspace{\fill}$\Box$
\end{proof}

\section{Discussion}

We have investigated three problems related to the construction of an SLP:
the information-theoretic lower bound for representing the phrase dictionary $D$,
an optimal representation of a directly addressable $D$,
and a dynamic data structure for $D^{-1}$.
Here, we consider the results of this study from the viewpoint of open questions.

For the first problem, we approximately estimated 
the size of a set of SLPs with $n$ symbols, which is
almost equal to the exact set.
This problem, however, has several variants, e.g.,
the set of SLPs with $n$ symbols deriving the same string,
which is quite difficult to estimate owing to the NP-hardness of the smallest CFG problem.
There is another variant obtained by a restriction:
Any two different variables do not derive the same digram, i.e.,
$Z\to XY$ and $Z'\to XY$ do not exist simultaneously for $Z\neq Z'$.
Although such variables are not prohibited in the definition of SLP,
they should be removed for space efficiency.
On the other hand, even if we assume this restriction,
the information-theoretic lower bound is never smaller than $\log n!$ bits because, 
given a directed chain of length $n$ as $T_L$,
we can easily construct $(n-1)!$ admissible DAGs.

For the second problem, we proposed almost optimal encoding of SLPs.
From the standpoint of massive data compression,
one drawback of the proposed encoding is that
the whole phrase dictionary must be stored in memory beforehand.
Since symbols must be sorted, we need a dynamic data structure
to allow the insertion of symbols in an array, e.g.,~\cite{Jansson2012}.
Such data structures, however, require $O(n\log n)$ bits of space.

For the last problem, the query time and update time of proposed 
data structure are both $O(\log n)$.
This cost is considerable and it is difficult to improve it
to $O(\log\log n)$ because $D$ is not static.
When focusing on the characteristics of SLPs, 
we can improve the query time probabilistically;
since any symbol $X$ appears in $D$ at least once and $|D|=2n$,
the average of frequency of $X$ is at most two.
Thus, using an additional array of size $n\log n$ bits,
we can check $H(XY)$ in $O(1)$ time with probability at least $1/2$.
However, improving this probability is not easy.
For this problem, achieving $O(1)$ amortized query time is also an interesting challenge.

%\input{sec6}


\bibliographystyle{plain}

{\small
\bibliography{main.bib}
}
\end{document}

main.bbl
\begin{thebibliography}{10}

\bibitem{Apostolico00}
A.~Apostolico and S.~Lonardi.
\newblock {Off-line Compression by Greedy Textual Substitution}.
\newblock {\em Proceedings of the IEEE}, 88:1733--1744, 2000.

\bibitem{Asai2002}
T.~Asai, K.~Abe, S.~Kawasoe, H.~Arimura, H.~Sakamoto, and S.~Arikawa.
\newblock {Efficient Substructure Discovery from Large Semi-structured Data}.
\newblock In {\em SDM}, pages 158--174, 2002.

\bibitem{Jeremy2010}
J.~Barbay, T.~Gagie, G.~Navarro, and Y.~Nekrich.
\newblock {Alphabet Partitioning for Compressed Rank/Select and Applications}.
\newblock In {\em ISAAC}, volume~2, pages 315--326, 2010.

\bibitem{Barbay2009}
J.~Barbay and G.~Navarro.
\newblock {Compressed Representations of Permutations, and Applications}.
\newblock In {\em STACS}, pages 111--122, 2009.

\bibitem{Botelho2007}
F.C. Botelho, R.~Pagh, and N.~Ziviani.
\newblock {Simple and Space-Efficient Minimal Perfect Hash Functions}.
\newblock In {\em WADS}, pages 139--150, 2007.

\bibitem{Charikar05}
M.~Charikar, E.~Lehman, D.~Liu, R.~Panigrahy, M.~Prabhakaran, A.~Sahai, and
  A.~Shelat.
\newblock The smallest grammar problem.
\newblock {\em IEEE Trans. Inform. Theory}, 51:2554--2576, 2005.

\bibitem{Claude09}
F.~Claude and G.~Navarro.
\newblock {Self-Indexed Grammar-Based Compression}.
\newblock {\em Fundam. Inform.}, 111:313--337, 2011.

\bibitem{ferragina2007simple}
P.~Ferragina and R.~Venturini.
\newblock A simple storage scheme for strings achieving entropy bounds.
\newblock {\em Theor. Comput. Sci.}, 372:115--121, 2007.

\bibitem{Fomin2002}
F.V. Fomin, D.~Kratsch, and J.-C. Novelli.
\newblock Approximating minimum cocolorings.
\newblock {\em Inf. Process. Lett.}, 84:285--290, 2002.

\bibitem{Golynski2006}
A.~Golynski, J.I. Munro, and S.S. Rao.
\newblock Rank/select operations on large alphabets: a tool for text indexing.
\newblock In {\em SODA}, pages 368--373, 2006.

\bibitem{gonzalez2006statistical}
R.~Gonz{\'a}lez and G.~Navarro.
\newblock {Statistical Encoding of Succinct Data Structures}.
\newblock In {\em CPM}, pages 294--305, 2006.

\bibitem{Grossi03}
R.~Grossi, A.~Gupta, and J.S. Vitter.
\newblock High-order entropy-compressed text indexes.
\newblock In {\em SODA}, pages 841--850, 2003.

\bibitem{Jacobson89}
G.~Jacobson.
\newblock {Space-efficient Static Trees and Graphs}.
\newblock In {\em FOCS}, pages 549--554, 1989.

\bibitem{Jansson2012-JCSS}
J.~Jansson, K.~Sadakane, and Wing-Kin Sung.
\newblock Ultra-succinct representation of ordered trees with applications.
\newblock {\em J. Comput. Syst. Sci.}, 78:619--631, 2012.

\bibitem{Jansson2012}
J.~Jansson, K.~Sadakane, and W.K. Sung.
\newblock {CRAM: Compressed Random Access Memory}.
\newblock In {\em ICALP}, volume~1, pages 510--521, 2012.

\bibitem{Karp72}
R.M. Karp, R.E. Miller, and A.L. Rosenberg.
\newblock {Rapid Identification of Repeated Patterns in Strings, Trees and
  Arrays}.
\newblock In {\em STOC}, pages 125--136, 1972.

\bibitem{Karp87}
R.M. Karp and M.O. Rabin.
\newblock {Efficient Randomized Pattern-Matching Algorithms}.
\newblock {\em IBM Journal of Research and Development}, 31:249--260, 1987.

\bibitem{SLP}
M.~Karpinski, W.~Rytter, and A.~Shinohara.
\newblock {An Efficient Pattern-Matching Algorithm for Strings with Short
  Descriptions}.
\newblock {\em Nordic J. Comp.}, 4:172--186, 1997.

\bibitem{Larsson00}
N.J. Larsson and A.~Moffat.
\newblock {Offline Dictionary-Based Compression}.
\newblock In {\em DCC}, pages 296--305, 1999.

\bibitem{LehmanPhD}
E.~Lehman.
\newblock {\em {Approximation Algorithms for Grammar-Based Compression}}.
\newblock PhD thesis, MIT, 2002.

\bibitem{Lehman-Shelat02}
E.~Lehman and A.~Shelat.
\newblock Approximation algorithms for grammar-based compression.
\newblock In {\em SODA}, pages 205--212, 2002.

\bibitem{Maruyama2011}
S.~Maruyama, M.~Nakahara, N.~Kishiue, and H.~Sakamoto.
\newblock {ESP-Index: A Compressed Index Based on Edit-Sensitive Parsing}.
\newblock In {\em SPIRE}, pages 398--409, 2011.

\bibitem{ESP}
S.~Maruyama, M.~Nakahara, N.~Kishiue, and H.~Sakamoto.
\newblock {ESP-Index: A Compressed Index Based on Edit-Sensitive Parsing}.
\newblock {\em J. Discrete Algorithms}, 18:100--112, 2013.

\bibitem{Maruyama2012}
S.~Maruyama, H.~Sakamoto, and M.~Takeda.
\newblock {An Online Algorithm for Lightweight Grammar-Based Compression}.
\newblock {\em Algorithms}, 5:213--235, 2012.

\bibitem{Navarro2012-cpm}
G.~Navarro.
\newblock {Wavelet Trees for All}.
\newblock In {\em CPM}, pages 2--26, 2012.

\bibitem{Navarro12}
G.~Navarro and E.~Providel.
\newblock {Fast, Small, Simple Rank/Select on Bitmaps}.
\newblock In {\em SEA}, pages 295--306, 2012.

\bibitem{Okanohara07}
D.~Okanohara and K.~Sadakane.
\newblock {Practical Entropy-Compressed Rank/Select Dictionary}.
\newblock In {\em ALENEX}, 2007.

\bibitem{Ram02}
R.~Raman, V.~Raman, and S.S. Rao.
\newblock Succinct indexable dictionaries with applications to encoding k-ary
  trees and multisets.
\newblock In {\em SODA}, pages 233--242, 2002.

\bibitem{Rytter03}
W.~Rytter.
\newblock Application of {Lempel-Ziv} factorization to the approximation of
  grammar-based compression.
\newblock {\em Theor. Comput. Sci.}, 302:211--222, 2003.

\bibitem{sadakane2006squeezing}
K.~Sadakane and R.~Grossi.
\newblock Squeezing succinct data structures into entropy bounds.
\newblock In {\em SODA}, pages 1230--1239, 2006.

\bibitem{Sakamoto05}
H.~Sakamoto.
\newblock A fully linear-time approximation algorithm for grammar-based
  compression.
\newblock {\em J. Discrete Algorithms}, 3:416--430, 2005.

\bibitem{Takabatake2012}
Y.~Takabatake, Y.~Tabei, and H.~Sakamoto.
\newblock {Variable-Length Codes for Space-Efficient Grammar-Based
  Compression}.
\newblock In {\em SPIRE}, pages 398--410, 2012.

\bibitem{Yehuda1998}
R.B. Yehuda and S.~Fogel.
\newblock {Partitioning a Sequence into Few Monotone Subsequences}.
\newblock {\em Acta Inf.}, 35:421--440, 1998.

\bibitem{Zaki2002}
M.J. Zaki.
\newblock Efficiently mining frequent trees in a forest.
\newblock In {\em KDD}, pages 71--80, 2002.

\bibitem{LZ77}
J.~Ziv and A.~Lempel.
\newblock {A Universal Algorithm for Sequential Data Compression}.
\newblock {\em IEEE Trans. Inform. Theory}, 23:337--343, 1977.

\bibitem{LZ78}
J.~Ziv and A.~Lempel.
\newblock Compression of individual sequences via variable-rate coding.
\newblock {\em IEEE Trans. Inform. Theory}, 24:530--536, 1978.

\end{thebibliography}

main.bib
@InBook{Ausiello99,
  author = 	 {G. Ausiello and P. Crescenzi and G. Gambosi and V.Kann and A. Marchetti-Spaccamela and M. Protasi},
  OPTeditor = 	 {},
  title = 	 {Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties},
  OPTchapter = 	 {},
  publisher = 	 {Springer},
  year = 	 {1999},
  OPTkey = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTtype = 	 {},
  OPTaddress = 	 {},
  OPTedition = 	 {},
  OPTmonth = 	 {},
  OPTpages = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InBook{Gusfield97,
  author = 	 {D. Gusfield},
  OPTeditor = 	 {},
  title = 	 {Algorithms on Strings, Trees, and Sequences},
  OPTchapter = 	 {},
  publisher = 	 {Cambridge University Press},
  year = 	 {1997},
  OPTkey = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTtype = 	 {},
  OPTaddress = 	 {},
  OPTedition = 	 {},
  OPTmonth = 	 {},
  OPTpages = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InBook{Knuth81,
  author = 	 {D.E. Knuth},
  OPTeditor = 	 {},
  title = 	 {The Art of Computer Programming, Volume II: Seminumerical Algorithms},
  OPTchapter = 	 {},
  publisher = 	 {Addison-Wesley},
  year = 	 {1981},
  OPTkey = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTtype = 	 {},
  OPTaddress = 	 {},
  OPTedition = 	 {},
  OPTmonth = 	 {},
  OPTpages = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InBook{Crochemore07,
  author = 	 {M. Crochemore and C. Hancart and T. Lecroq},
  ALTeditor = 	 {},
  title = 	 {Algorithms on Strings},
  OPTchapter = 	 {},
  publisher = 	 {Cambridge University Press},
  year = 	 {2007},
  OPTkey = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTtype = 	 {},
  OPTaddress = 	 {},
  OPTedition = 	 {},
  OPTmonth = 	 {},
  OPTpages = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InBook{Lothaire,
  author = 	 {M. Lothaire},
  ALTeditor = 	 {},
  title = 	 {Combinatorics on Words},
  OPTchapter = 	 {},
  publisher = 	 {Cambridge University Press},
  year = 	 {1983},
  OPTkey = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTtype = 	 {},
  OPTaddress = 	 {},
  OPTedition = 	 {},
  OPTmonth = 	 {},
  OPTpages = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Barbay2009,
  author = 	 {J. Barbay and G. Navarro},
  title = 	 {{Compressed Representations of Permutations, and Applications}},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {STACS},
  pages = 	 {111-122},
  year = 	 {2009},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Li04,
  author = 	 {M. Li and X. Chen and X. Li and B. Ma and P.M.B. Vitanyi},
  title = 	 {The similarity metric},
  journal = 	 {IEEE Trans. Inform. Theory},
  year = 	 {2004},
  OPTkey = 	 {},
  volume = 	 {50},
  number = 	 {12},
  pages = 	 {3250-3264},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Cilibrasi05,
  author = 	 {R. Cilibrasi and P.M.B. Vitanyi},
  title = 	 {Clustering by compression},
  journal = 	 {IEEE Trans. Inform. Theory},
  year = 	 {2005},
  OPTkey = 	 {},
  volume = 	 {51},
  number = 	 {4},
  pages = 	 {1523-1545},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Agostino96,
  author = 	 {S. De Agostino and J.A. Storer},
  title = 	 {On-Line versus Off-Line Computation in Dynamic Text Compression},
  journal = 	 {Inform. Process. Lett.},
  year = 	 {1996},
  OPTkey = 	 {},
  volume = 	 {59},
  OPTnumber = 	 {},
  Tpages = 	 {169-174},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Storer78,
  author = 	 {J.A. Storer and T.G. Szymanski},
  title = 	 {The Macro Model for Data Compression},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {STOC},
  pages = 	 {30-39},
  year = 	 {1978},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Lehman-Shelat02,
  author = 	 {E. Lehman and A. Shelat},
  title = 	 {Approximation algorithms for grammar-based compression},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle   =  {SODA},
  pages = 	 {205-212},
  year = 	 {2002},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{KidaTCS01,
  author = 	 {T. Kida and T. Matsumoto and Y. Shibata and M. Takeda and A. Shinohara and S. Arikawa},
  title = 	 {Collage System: a Unifying Framework  for Compressed Pattern Matching},
  journal = 	 {Theor. Comput. Sci.},
  year = 	 {2003},
  OPTkey = 	 {},
  volume = 	 {298},
  number = 	 {1},
  pages = 	 {253-272},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Welch84,
  author = 	 {T.A. Welch},
  title = 	 {A Technique for High Performance Data Compression},
  journal = 	 {IEEE Comput.},
  year = 	 {1984},
  OPTkey = 	 {},
  volume = 	 {17},
  OPTnumber = 	 {},
  pages = 	 {8-19},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Charikar05,
  author = 	 {M. Charikar and E. Lehman and D. Liu and R. Panigrahy and M. Prabhakaran and A. Sahai and A. Shelat},
  title = 	 {The smallest grammar problem},
  journal = 	 {IEEE Trans. Inform. Theory},
  year = 	 {2005},
  OPTkey = 	 {},
  volume = 	 {51},
  number = 	 {},
  pages = 	 {2554-2576},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Kieffer00,
  author = 	 {J.C. Kieffer and E.-H. Yang},
  title = 	 {Grammar-based codes: A new class of universal lossless source codes},
  journal = 	 {IEEE Trans. Inform. Theory},
  year = 	 {2000},
  OPTkey = 	 {},
  volume = 	 {46},
  number = 	 {3},
  pages = 	 {737-754},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Larsson00,
  author = 	 {N.J. Larsson and A. Moffat},
  title = 	 {{Offline Dictionary-Based Compression}},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle   = {DCC},
  pages = 	 {296-305},
  year = 	 {1999},
  OPTeditor = 	 {},
  OPTnumber = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@Article{Rytter03,
  author = 	 {W. Rytter},
  title = 	 {Application of {Lempel-Ziv} factorization to the approximation of grammar-based compression},
  journal = 	 {Theor. Comput. Sci.},
  year = 	 {2003},
  OPTkey = 	 {},
  volume = 	 {302},
  number = 	 {},
  pages = 	 {211-222},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Sakamoto05,
  author = 	 {H. Sakamoto},
  title = 	 {A Fully Linear-Time Approximation Algorithm for Grammar-Based Compression},
  journal = 	 {J. Discrete Algorithms },
  year = 	 {2005},
  OPTkey = 	 {},
  volume = 	 {3},
  number = 	 {},
  pages = 	 {416-430},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Yang03,
  author = 	 {E.-H. Yang and D.-K. He},
  title = 	 {Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform - Part two: with context models},
  journal = 	 {IEEE Trans. Inform. Theory},
  year = 	 {2003},
  OPTkey = 	 {},
  volume = 	 {49},
  number = 	 {11},
  pages = 	 {2874-2894},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Yang00,
  author = 	 {E.-H. Yang and J.C. Kieffer},
  title = 	 {Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform - Part one: without context models},
  journal = 	 {IEEE Trans. Inform. Theory},
  year = 	 {2000},
  OPTkey = 	 {},
  volume = 	 {46},
  number = 	 {3},
  pages = 	 {755-777},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@Article{Kieffer-others00,
  author = 	 {J.C. Kieffer and E.-H. Yang and G. Nelson and P. Cosman},
  title = 	 {Universal Lossless Compression via Multilevel Pattern Matching},
  journal = 	 {IEEE Trans. Inform. Theory},
  year = 	 {2000},
  OPTkey = 	 {},
  volume = 	 {IT-46},
  number = 	 {5},
  pages = 	 {1227-1245},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{LZ78,
  author = 	 {J. Ziv and A. Lempel},
  title = 	 {Compression of Individual Sequences via Variable-Rate Coding},
  journal = 	 {IEEE Trans. Inform. Theory},
  year = 	 {1978},
  OPTkey = 	 {},
  volume = 	 {24},
  number = 	 {},
  pages = 	 {530-536},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{LZ77,
  author = 	 {J. Ziv and A. Lempel},
  title = 	 {{A Universal Algorithm for Sequential Data Compression}},
  journal = 	 {IEEE Trans. Inform. Theory},
  year = 	 {1977},
  OPTkey = 	 {},
  volume = 	 {23},
  number = 	 {},
  pages = 	 {337-343},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@Article{Nevill97,
  author = 	 {C. Nevill-Manning and I. Witten},
  title = 	 {Compression and Explanation Using Hierarchical Grammars},
  journal = 	 {Computer Journal},
  year = 	 {1997},
  OPTkey = 	 {},
  volume = 	 {40},
  number = 	 {2/3},
  pages = 	 {103-116},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Manning97,
  author = 	 {C.G. Nevill-Manning and I.H. Witten},
  title = 	 {Identifying Hierarchical Strcture in Sequences: a linear-time algorithm},
  journal = 	 {J. Artif. Intell. Res.},
  year = 	 {1997},
  OPTkey = 	 {},
  volume = 	 {7},
  OPTnumber = 	 {},
  pages = 	 {67-82},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Sakamoto04,
  author = 	 {H. Sakamoto and T. Kida and S. Shimozono},
  title = 	 {A Space-Saving Linear-Time Algorithm for Grammar-Based Compression},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {SPIRE},
  pages = 	 {218-229},
  year = 	 {2004},
  OPTeditor = 	 {},
  volume = 	 {3246},
  OPTnumber = 	 {},
  series = 	 {LNCS},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Sakamoto09,
  author = 	 {H. Sakamoto and S. Maruyama and T. Kida and S. Shimozono},
  title = 	 {A space-saving approximation algorithm for grammar-based compression},
  journal = 	 {IEICE Trans. Inform. and Systems},
  year = 	 {2009},
  OPTkey = 	 {},
  volume = 	 {E92-D},
  number = 	 {2},
  pages = 	 {158-165},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Cormode07,
  author = 	 {G. Cormode and S. Muthukrishnan},
  title = 	 {The String Edit Distance Matching Problem With Moves},
  journal = 	 {ACM Trans. Algor.},
  year = 	 {2007},
  OPTkey = 	 {},
  volume = 	 {3},
  number = 	 {1},
  pages = 	 {Article 2},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Cormode05,
  author = 	 {G. Cormode and S. Muthukrishnan},
  title = 	 {Substring compression problems},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {SODA},
  pages = 	 {321-330},
  year = 	 {2005},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Sahinalp96,
  author = 	 {S.C. Sahinalp and U. Vishkin},
  title = 	 {Efficient approximate and dynamic matching of patterns using a labeling
paradigm},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {FOCS},
  pages = 	 {320-328},
  year = 	 {1996},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Batu03,
  author = 	 {T. Batu and F. Ergun and J. Kilian and A. Magen and S. Raskhodnikova and R. Rubinfeld and R. Sami},
  title = 	 {A sublinear algorithm for weakly approximating edit distance},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {STOC},
  pages = 	 {316-324},
  year = 	 {2003},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Bar-Yossef04,
  author = 	 {Z. Bar-Yossef and T. Jayram and R. Krauthgamer and R. Kumar},
  title = 	 {Approximating edit distance efficiently},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {FOCS},
  pages = 	 {550-559},
  year = 	 {2004},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@Article{Claude09,
  author = 	 {F. Claude and G. Navarro},
  title = 	 {{Self-Indexed Grammar-Based Compression}},
  journal = 	 {Fundam. Inform.},
  year = 	 {2011},
  OPTkey = 	 {},
  volume = 	 {111},
  number = 	 {},
  pages = 	 {313-337},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Navarro08,
  author = 	 {G. Navarro},
  title = 	 {Implementing the {LZ-index}: Theory versus practice},
  journal = 	 {ACM Journal of Experimental Algorithmics},
  year = 	 {2008},
  OPTkey = 	 {},
  volume = 	 {13},
  OPTnumber = 	 {},
  pages = 	 {Article No. 1.2},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}



@Article{Navarro07,
  author = 	 {G. Navarro and V. M\"{a}kinen},
  title = 	 {Compressed Full-Text Indexes},
  journal = 	 {ACM Computing Surveys},
  year = 	 {2007},
  OPTkey = 	 {},
  volume = 	 {39},
  number = 	 {1},
  pages = 	 {Article 2},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@Article{Karp87,
  author = 	 {R.M. Karp and M.O. Rabin},
  title = 	 {{Efficient Randomized Pattern-Matching Algorithms}},
  journal = 	 {IBM Journal of Research and Development},
  year = 	 {1987},
  OPTkey = 	 {},
  volume = 	 {31},
  number = 	 {},
  pages = 	 {249-260},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}



@InProceedings{Karp72,
  author = 	 {R.M. Karp and R.E. Miller and A.L. Rosenberg},
  title = 	 {{Rapid Identification of Repeated Patterns in Strings, Trees and Arrays}},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {STOC},
  pages = 	 {125-136},
  year = 	 {1972},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Navarro04JDA,
  author = 	 {G. Navarro},
  title = 	 {Indexing text using the {Ziv-Lempel} tire},
  journal = 	 {J. Discrete Algorithms },
  year = 	 {2004},
  OPTkey = 	 {},
  volume = 	 {2},
  number = 	 {1},
  pages = 	 {87-114},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Sadakane00,
  author = 	 {K. Sadakane},
  title = 	 {Compressed text databases with efficient query algorithms based on the compressed suffix array},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {ISAAC},
  pages = 	 {410-421},
  year = 	 {2000},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Ferragina00,
  author = 	 {P. Ferragina and G. Manzini},
  title = 	 {Opportunistic data structures with applications},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {FOCS},
  pages = 	 {390-398},
  year = 	 {2000},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@Article{Sadakane03,
  author = 	 {K. Sadakane},
  title = 	 {New Text Indexing Functionalities of the compressed Suffix Arrays},
  journal = 	 {J. Algorithms},
  year = 	 {2003},
  OPTkey = 	 {},
  volume = 	 {48},
  number = 	 {2},
  pages = 	 {294-313},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@Article{Ferragina07,
  author = 	 {P. Ferragina and G. Manzini and V. M\"{a}kinen and G. Navarro},
  title = 	 {Compressed representations of sequences and full-text indexes },
  journal = 	 {ACM Trans. Algor.},
  year = 	 {2007},
  OPTkey = 	 {},
  volume = 	 {3},
  number = 	 {2},
  OPTpages = 	 {},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}



@Article{Shapira07,
  author = 	 {D. Shapira and J.A. Storer},
  title = 	 {Edit distance with move operations},
  journal = 	 {J. Discrete Algorithms},
  year = 	 {2007},
  OPTkey = 	 {},
  volume = 	 {5},
  number = 	 {2},
  pages = 	 {380-392},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Bille11,
  author = 	 {P. Bille and G.M. Landau and R. Raman and K. Sadakane 
and S.S. Rao and O. Weimann},
  title = 	 {Random Access to grammar-Compressed Strings},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {SODA},
  pages = 	 {373-389},
  year = 	 {2011},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Unpublished{Claude-arXiv,
  author = 	 {F. Claude and G. Navarro},
  title = 	 {Improved Grammar-Based Compressed Indexes},
  note = 	 {arXiv:1110.4493},
  OPTkey = 	 {},
  OPTmonth = 	 {},
  OPTyear = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Kreft11,
  author = 	 {S. Kreft and G. Navarro},
  title = 	 {Self-indexing Based on {LZ77}},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {CPM},
  pages = 	 {41-54},
  year = 	 {2011},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Makinen00,
  author = 	 {V. M\"{a}kinen}, 
  title = 	 {Compact Suffix Array},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {CPM},
  pages = 	 {305-319},
  year = 	 {2000},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Grossi00,
  author = 	 {R. Grossi and J.S. Vitter},
  title = 	 {Compressed suffix arrays and suffix trees with applications to text indexing and string matching},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {STOC},
  pages = 	 {397-406},
  year = 	 {2000},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}



@InProceedings{Sahinalp94,
  author = 	 {S.C. Sahinalp and U. Vishkin},
  title = 	 {Symmetry breaking for suffix tree construction},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {STOC},
  pages = 	 {300-309},
  year = 	 {1994},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Apostolico00,
  author = 	 {A. Apostolico and S. Lonardi},
  title = 	 {{Off-line Compression by Greedy Textual Substitution}},
  journal = 	 {Proceedings of the IEEE},
  year = 	 {2000},
  OPTkey = 	 {},
  volume = 	 {88},
  pages = 	 {1733-1744},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Arroyuelo06,
  author = 	 {D. Arroyuelo and G. Navarro and K. Sadakane},
  title = 	 {Reducing the Space Requirement of {LZ-Index}},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {CPM},
  pages = 	 {318-329},
  year = 	 {2006},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}



@Article{Ferragina05,
  author = 	 {P. Ferragina and G. Manzini},
  title = 	 {Indexing compressed text},
  journal = 	 {J. ACM},
  year = 	 {2005},
  OPTkey = 	 {},
  volume = 	 {52},
  number = 	 {4},
  pages = 	 {552-581},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@Article{Russo08,
  author = 	 {L.M.S. Russo and A.L. Oliveira},
  title = 	 {A compressed self-index using a {Ziv-Lempel} dictionary},
  journal = 	 {Inf. Retr.},
  year = 	 {2008},
  OPTkey = 	 {},
  volume = 	 {11},
  number = 	 {4},
  pages = 	 {359-388},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}



@InProceedings{Gagie2012,
  author = 	 {T. Gagie and P. Gawrychowski and J. K\"{a}rkk\"{a}inen and Y. Nekrich and S.J. Puglisi},
  title = 	 {A Faster Grammar-Based Self-Index},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {LATA},
  pages = 	 {240-251},
  year = 	 {2012},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}



@PhdThesis{LehmanPhD,
  author = 	 {E. Lehman},
  title = 	 {{Approximation Algorithms for Grammar-Based Compression}},
  school = 	 {MIT},
  year = 	 {2002},
  OPTkey = 	 {},
  OPTtype = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Ferragina04,
  author = 	 {P. Ferragina and G. Manzini and V. M\"{a}kinen and G. Navarro},
  title = 	 {An Alphabet-Friendly {FM-index}},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {SPIRE},
  pages = 	 {150-160},
  year = 	 {2004},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Maruyama11,
  author = 	 {S. Maruyama and M. Takeda and M. Nakahara and H. Sakamoto},
  title = 	 {An Online Algorithm for Lightweight Grammar-Based Compression},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {CCP},
  pages = 	 {19-28},
  year = 	 {2011},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Cole86,
  author = 	 {R. Cole and U. Vishkin},
  title = 	 {Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {STOC},
  pages = 	 {206-219},
  year = 	 {1986},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Muthukrishnan02,
  author = 	 {S. Muthukrishnan},
  title = 	 {Efficient algorithms for document retrieval problems},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {SODA},
  pages = 	 {657-666},
  year = 	 {2002},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@TechReport{Makinen04,
  author = 	 {V. M\"{a}kinen and G. Navarro},
  title = 	 {New search algorithms and time/space tradeoffs for succinct suffix arrays},
  institution =  {University of Helsinki},
  year = 	 {2004},
  OPTkey = 	 {},
  OPTtype = 	 {},
  OPTnumber = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Hon09,
  author = 	 {W.-K. Hon and R. Shah and J. S. Vitter},
  title = 	 {Space-Efficient Framework for Top-$k$ String Retrieval Problems},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {FOCS},
  pages = 	 {713-722},
  year = 	 {2009},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Maruyama2012,
  author = 	 {S. Maruyama and H. Sakamoto and M. Takeda},
  title = 	 {{An Online Algorithm for Lightweight Grammar-Based Compression}},
  journal = 	 {Algorithms},
  year = 	 {2012},
  OPTkey = 	 {},
  volume = 	 {5},
  number = 	 {},
  pages = 	 {213-235},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Maruyama2011,
  author = 	 {S. Maruyama and M. Nakahara and N. Kishiue and H. Sakamoto},
  title = 	 {{ESP-Index: A Compressed Index Based on Edit-Sensitive Parsing}},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle   = {SPIRE},
  pages = 	 {398-409},
  year = 	 {2011},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTannote = 	 {}
}
@Article{ESP,
  author = 	 {S. Maruyama and M. Nakahara and N. Kishiue and H. Sakamoto},
  title = 	 {{ESP-Index: A Compressed Index Based on Edit-Sensitive Parsing}},
  journal = 	 {J. Discrete Algorithms},
  year = 	 {2013},
  OPTkey = 	 {},
  volume = 	 {18},
  OPTnumber = 	 {},
  pages = 	 {100-112},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{SLP,
  author = 	 {M. Karpinski and W. Rytter and A. Shinohara},
  title = 	 {{An Efficient Pattern-Matching Algorithm for Strings with Short Descriptions}},
  journal = 	 {Nordic J. Comp.},
  year = 	 {1997},
  OPTkey = 	 {},
  volume = 	 {4},
  number = 	 {},
  pages = 	 {172-186},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Takabatake2012,
  author = 	 {Y. Takabatake and Y. Tabei and H. Sakamoto},
  title = 	 {{Variable-Length Codes for Space-Efficient Grammar-Based Compression}},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {SPIRE},
  pages = 	 {398-410},
  year = 	 {2012},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@Book{Knuth1981,
  author = 	 {D.E. Knuth},
  ALTeditor = 	 {},
  title = 	 {Seminumerical Algorithms},
  publisher = 	 {Addison-Wesley},
  year = 	 {1981},
  OPTkey = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTedition = 	 {},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}



@InProceedings{Kieffer2000-BDD,
  author = 	 {J. Kieffer and P. Flajolet and E.-H. Yang},
  title = 	 {Data Compression Via Binary Decision Diagrams},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {IEEE Symposium on Information Theory},
  pages = 	 {296},
  year = 	 {2000},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@article{ferragina2007simple,
  title={A simple storage scheme for strings achieving entropy bounds},
  author={P. Ferragina and R. Venturini},
  journal={Theor. Comput. Sci.},
  volume={372},
  pages={115--121},
  year={2007},
  publisher={Elsevier}
}

@inproceedings{sadakane2006squeezing,
  title={Squeezing succinct data structures into entropy bounds},
  author={K. Sadakane and R. Grossi},
  booktitle={SODA},
  pages={1230--1239},
  year={2006},
  organization={}
}

@inproceedings{gonzalez2006statistical,
  title={{Statistical Encoding of Succinct Data Structures}},
  author={R. Gonz{\'a}lez and G. Navarro},
  OPTauthor={Gonz{\'a}lez, Rodrigo and Navarro, Gonzalo},
  booktitle={CPM},
  pages={294--305},
  year={2006},
  organization={}
}
This file was created with JabRef 2.2.
Encoding: MS932


@STRING{ciaa08 = {Proc. 13th International Conference on Implementation and Application of Automata (CIAA'08)}}

@STRING{ciac00 = {Proc. 4th Italian Conference on Algorithms and Complexity (CIAC'00)}}

@STRING{cpm00 = {Proc. 11th Annual Symposium on Combinatorial Pattern Matching (CPM'00)}}

@STRING{cpm01 = {Proc. 12th Annual Symposium on Combinatorial Pattern Matching (CPM'01)}}

@STRING{cpm02 = {Proc. 13th Annual Symposium on Combinatorial Pattern Matching (CPM'02)}}

@STRING{cpm94 = {Proc. 5th Annual Symposium on Combinatorial Pattern Matching (CPM'94)}}

@STRING{cpm95 = {Proc. 6th Annual Symposium on Combinatorial Pattern Matching (CPM'95)}}

@STRING{cpm97 = {Proc. 8th Annual Symposium on Combinatorial Pattern Matching (CPM'97)}}

@STRING{cpm99 = {Proc. 10th Annual Symposium on Combinatorial Pattern Matching (CPM'99)}}

@STRING{dcc92 = {Proc. Data Compression Conference '92 (DCC'92)}}

@STRING{dcc94 = {Proc. Data Compression Conference '94 (DCC'94)}}

@STRING{dcc98 = {Proc. Data Compression Conference '98 (DCC'98)}}

@STRING{dcc99 = {Proc. Data Compression Conference '99 (DCC'99)}}

@STRING{ja = {Journal of Algorithms}}

@STRING{jcss = {Journal of Computer and System Sciences}}

@STRING{jda = {Journal of Discrete Algorithms}}

@STRING{ndc = {Nordic Journal of Computing}}

@STRING{spire00 = {Proc. 7th International Symposium on String Processing and Information
	Retrieval}}

@STRING{spire99 = {Proc. 6th International Symposium on String Processing and Information
	Retrieval}}

@STRING{swat96 = {Proc. 5th Scandinavian Workshop on Algorithm Theory (SWAT'96)}}

@STRING{tcs = {Theoret. Comput. Sci.}}

@InProceedings{Gasieniec96,
  author = 	 {L. Gasieniec and M. Karpinski and W. Plandowski and W. Rytter},
  title = 	 {Efficient algorithms for Lempel-Ziv encoding},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {SWAT96},
  pages = 	 {392},
  year = 	 {1996},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Inenaga09,
  author = 	 {S. Inenaga and Hideo Bannai},
  title = 	 {Finding Characteristic Substrings from Compressed Texts},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {PSC09},
  pages = 	 {40-54},
  year = 	 {2009},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Matsubara09,
  author = 	 {W. Matsubara and S. Inenaga and A. Ishino and A Shinohara and T. Nakamura and K. Hashimoto},
  title = 	 {Efficient Algorithms to Compute Compressed Longest Common Substrings and Compressed Palindromes},
  journal = 	 {Theoretical Computer Science},
  year = 	 {2009},
  OPTkey = 	 {},
  volume = 	 {410},
  number = 	 {8-10},
  pages = 	 {900-913},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Karpinski97,
  author = 	 {M. Karpinski and W. Rytter and A. Shinohara },
  title = 	 {An efficient pattern-matching algorithm for strings with short descriptions},
  journal = 	 {Nordic Journal of Computing},
  year = 	 {1997},
  OPTkey = 	 {},
  volume = 	 {4},
  OPTnumber = 	 {},
  pages = 	 {172-186},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Inenaga05,
  author = 	 {S. Inenaga and A. Shinohara and M. Takeda},
  title = 	 {A fully compressed pattern matching algorithm for simple collage systems},
  journal = 	 {Int. J. Found. Comput. Sci.},
  year = 	 {2005},
  OPTkey = 	 {},
  volume = 	 {16},
  number = 	 {6},
  pages = 	 {1155-1166},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@ARTICLE{ManberACM97,
  author = {U. Manber},
  title = {A text compression scheme that allows fast searching directly in
	the compressed file},
  journal = {ACM Transactions on Information Systems},
  year = {1997},
  volume = {15},
  pages = {124-136},
  number = {2},
  optnote = {Preliminary version in {\em CPM'94}}
}


@ARTICLE{Amir96,
  author = {A. Amir and G. Benson and M. Farach},
  title = {Let Sleeping Files Lie: Pattern Matching in {Z}-Compressed Files},
  journal = {J. Comput. Syst. Sci.},
  year = {1996},
  volume = {52},
  pages = {299-307},
  number = {2}
}

@INPROCEEDINGS{AmirBensonDCC92,
  author = {A. Amir and G. Benson},
  title = {Efficient Two-Dimensional Compressed Matching},
  booktitle = dcc92,
  year = {1992},
  pages = {279}
}

@INPROCEEDINGS{AmirBensonSODA92,
  author = {A.~Amir and G.~Benson},
  title = {Two-Dimensional Periodicity and Its Application},
  booktitle = {Proc. of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms},
  year = {1992},
  pages = {440--452}
}

@ARTICLE{AmirJAlgorithms97,
  author = {Amihood Amir and Gary Benson and Martin Farach},
  title = {Optimal Two-Dimensional Compressed Matching},
  journal = ja,
  year = {1997},
  volume = {24},
  pages = {354--379},
  number = {2},
  optnote = {Preliminary version in {\em ICALP'94}}
}

@ARTICLE{AmirJCSS96,
  author = {Amihood Amir and Gary Benson and Martin Farach},
  title = {Let Sleeping Files Lie: Pattern Matching in {Z}-Compressed Files},
  journal = jcss,
  year = {1996},
  volume = {52},
  pages = {299--307},
  number = {2}
}


@ARTICLE{Horspool80,
  author = {R. N. Horspool},
  title = {Practical Fast Searching in Strings},
  journal = {Software-Practice and Experience},
  year = {1980},
  volume = {10},
  pages = {501-506}
}

@ARTICLE{KidaTCS2003,
  author = {T. Kida and T. Matsumoto and Y. Shibata and M. Takeda and A. Shinohara
	and S. Arikawa},
  title = {Collage systems: a unifying framework for compressed pattern matching},
  journal = tcs,
  year = {2003},
  volume = {298},
  pages = {253--272},
  number = {1},
  optnote = {Preliminary version in {\em SPIRE'99}}
}

@INPROCEEDINGS{MatsumotoCIAA2008,
  author = {T. Matsumoto and K. Hagio and M. Takeda},
  title = {A Run-Time Efficient Implementation of Compressed Pattern Matching Automata},
  booktitle = ciaa08,
  year = {2008},
  optvolume = {2373},
  optseries = {LNCS},
  optpages = {42--52},
  optpublisher = {Springer-Verlag},
  owner = {takeda},
  note  = {To appear},
  timestamp = {2007.11.13}
}


@TECHREPORT{Matsumoto2007,
  author = {T. Matsumoto and K. Hagio and M. Takeda},
  title = {More Speed and More Compression: Accelerating Pattern Matching by
	Text Compression},
  institution = {Department of Informatics, Kyushu University},
  year = {2007},
  number = {DOI-TR-CS-232},
  month = {November},
  optaddress = {??},
  optannote = {??},
  optcrossref = {??},
  optkey = {??},
  optnote = {??},
  opttype = {??}
}

@ARTICLE{Navarro04,
  author = {G. Navarro and M. Raffinot},
  title = {Practical and flexible pattern matching over {Ziv-Lempel} compressed
	text},
  journal = {J. Discrete Algorithms},
  year = {2004},
  volume = {2},
  pages = {347-371},
  number = {3}
}

@INPROCEEDINGS{RautioCPM2002,
  author = {J. Rautio and J. Tanninen and J. Tarhio},
  title = {String Matching with Stopper Encoding and Code Splitting},
  booktitle = cpm02,
  year = {2002},
  volume = {2373},
  series = {LNCS},
  pages = {42--52},
  optpublisher = {Springer-Verlag},
  owner = {takeda},
  timestamp = {2007.11.13}
}

@INPROCEEDINGS{ShibataCIAC2000,
  author = {Y. Shibata and T. Kida and S. Fukamachi and M. Takeda and A. Shinohara
	and T. Shinohara and S. Arikawa},
  title = {Speeding up pattern Matching by Text Compression},
  booktitle = ciac00,
  year = {2000},
  volume = {1767},
  series = {LNCS},
  pages = {306--315},
  optpublisher = {Springer-Verlag}
}

@INPROCEEDINGS{ShibataCPM2000,
  author = {Y. Shibata and T. Matsumoto and M. Takeda and A. Shinohara and S.
	Arikawa},
  title = {A {Boyer-Moore} type algorithm for compressed pattern matching},
  booktitle = cpm00,
  year = {2000},
  volume = {1848},
  series = {LNCS},
  pages = {181--194},
  optpublisher = {Springer-Verlag}
}

@INPROCEEDINGS{Yamamoto2011, 
  author = {T. Yamamoto and H. Bannai and S. Inenaga and M. Takeda}, 
  title  = {{Faster Subsequence and Don't-Care Pattern Matching on Compressed Texts}}, 
  booktitle = {CPM}, 
  volume = {6661}, 
  pages = {309-322},
  year  = {2011}
}

@INPROCEEDINGS{Tiskin2011,
 author = {A. Tiskin},
 title = {{Towards Approximate Matching in Compressed Strings}},
 booktitle = {CSR},
 year = {2011},
 pages = {401--414},
 numpages = {14},
 publisher = {Springer-Verlag},
 address = {Berlin, Heidelberg}
} 

@INPROCEEDINGS{Goto2011,
  title={{Fast q-Gram Mining on SLP Compressed Strings}},
  author={Goto, K. and Bannai, H. and Inenaga, S. and Takeda, M.},
  booktitle={SPIRE},
  pages={278--289},
  year={2011},
  organization={Springer}
}

@INPROCEEDINGS{Hermelin2009,
  title={{A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression}},
  author={Hermelin, D. and Landau, G.M. and Landau, S. and Weimann, O.},
  booktitle={STACS},
  pages={26--28},
  year={2009}
}

@article{Nevill1997,
  title={{Identifying hierarchical structure in sequences: A linear-time algorithm}},
  author={Nevill-Manning, C.G. and Witten, I.H.},
  journal={J. Artif. Intell. Res.},
  year={1997},
  pages={67-82}
}

@article{Larsson2000,
  title={Off-line dictionary-based compression},
  author={Larsson, N.J. and Moffat, A.},
  journal={Proceedings of the IEEE},
  volume={88},
  pages={1722--1732},
  year={2000},
  publisher={Ieee}
}

@article{Apostolico2000,
  title={Offline compression by greedy textual substitution},
  author={Apostolico, A. and Lonardi, S.},
  journal={Proceedings of the IEEE},
  volume={88},
  pages={1733--1744},
  year={2000},
  publisher={IEEE}
}

@article{Charikar2005,
  title={The smallest grammar problem},
  author={Charikar, M. and Lehman, E. and Liu, D. and Panigrahy, R. and Prabhakaran, M. and Sahai, A. and Shelat, A.},
  journal={IEEE Trans. Inf. Theory},
  volume={51},
  pages={2554--2576},
  year={2005}
}

@article{Rytter2003,
  title={{Application of Lempel-Ziv factorization to the approximation of grammar-based compression}},
  author={Rytter, W.},
  journal={Theor. Comput. Sci.},
  volume={302},
  pages={211--222},
  year={2003},
  publisher={Elsevier}
}

@article{Sakamoto2005,
  title={A fully linear-time approximation algorithm for grammar-based compression},
  author={Sakamoto, H.},
  journal={J. Discret. Algorithms},
  volume={3},
  pages={416--430},
  year={2005},
  publisher={Elsevier}
}

@INRPOCEEDINGS{Sakamoto2004,
  title={A Space-Saving Approximation Algorithm for Grammar-Based Compression},
  author={Sakamoto, H. and Kida, T. and Shimozono, S.},
  book={SPIRE'04},
  pages={218--229},
  year={2004}
}

@article{Sakamoto2009,
  title={A space-saving approximation algorithm for grammar-based compression},
  author={Sakamoto, H. and Maruyama, S. and Kida, T. and Shimozono, S.},
  journal={IEICE trans. inf. syst.},
  volume={92},
  number={2},
  pages={158--165},
  year={2009},
  publisher={Institute of Electronics, Information and Communication Engineers}
}@Article{Erdos1935,
  author = 	 {P. Erd\H{o}s and G. Szekeres},
  title = 	 {A combinatorial problem in geometry},
  journal = 	 {Compositio Mathematica},
  year = 	 {1935},
  OPTkey = 	 {},
  volume = 	 {2},
  OPTnumber = 	 {},
  pages = 	 {463-470},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Yehuda1998,
  author = 	 {R.B. Yehuda and S. Fogel},
  title = 	 {{Partitioning a Sequence into Few Monotone Subsequences}},
  journal = 	 {Acta Inf.},
  year = 	 {1998},
  OPTkey = 	 {},
  volume = 	 {35},
  OPTnumber = 	 {},
  pages = 	 {421-440},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}






@Article{Fomin2002,
  author = 	 {F.V. Fomin and D. Kratsch and J.-C. Novelli},
  title = 	 {Approximating minimum cocolorings },
  journal = 	 {Inf. Process. Lett.},
  year = 	 {2002},
  OPTkey = 	 {},
  volume = 	 {84},
  number = 	 {},
  pages = 	 {285-290},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Asai2002,
  author = 	 {T. Asai and K. Abe and S. Kawasoe and H. Arimura and H. Sakamoto and S. Arikawa},
  title = 	 {{Efficient Substructure Discovery from Large Semi-structured Data}},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {SDM},
  pages = 	 {158-174},
  year = 	 {2002},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}



Proc. Eighth ACM SIGKDD Int',l Conf. Knowledge Discovery and Data Mining, July 2002. 

@InProceedings{Zaki2002,
  author = 	 {M.J. Zaki},
  title = 	 {Efficiently Mining Frequent Trees in a Forest },
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {KDD},
  pages = 	 {71-80},
  year = 	 {2002},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Sadakane10,
  author = 	 {K. Sadakane and G. Navarro},
  title = 	 {Fully-Functional Succinct Trees},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {SODA},
  pages = 	 {134-149},
  year = 	 {2010},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Lu07,
  author = 	 {H.-I. Lu and C.-C. Yeh},
  title = 	 {Balanced parentheses strike back},
  journal = 	 {ACM Transactions on Algorithms},
  year = 	 {2008},
  OPTkey = 	 {},
  volume = 	 {4},
  number = 	 {3},
  pages = 	 {Article No 28},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Munro03,
  author = 	 {J.I. Munro and R. Raman and V. Raman and S.S. Rao},
  title = 	 {Succinct Representations of Permutations},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {ICALP},
  pages = 	 {345-356},
  year = 	 {2003},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Article{Benoit05,
  author = 	 {D.A. Benoit and E.D. Demaine and J.I. Munro and R. Raman and V. Raman and S.S. Rao},
  title = 	 {Representing Trees of Higher Degree},
  journal = 	 {Algorithmica},
  year = 	 {2005},
  OPTkey = 	 {},
  volume = 	 {43},
  OPTnumber = 	 {},
  pages = 	 {275-292},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Jacobson89,
  author = 	 {G. Jacobson},
  title = 	 {{Space-efficient Static Trees and Graphs}},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {FOCS},
  pages = 	 {549-554},
  year = 	 {1989},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@Article{Munro01,
  author = 	 {J.I. Munro and V. Raman},
  title = 	 {Succinct Representation of Balanced Parentheses and Static Trees},
  journal = 	 {SIAM Journal on Computing},
  year = 	 {2001},
  OPTkey = 	 {},
  volume = 	 {31},
  number = 	 {3},
  pages = 	 {762-776},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Munro96,
  author = 	 {J.I. Munro},
  title = 	 {Tables},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {FSTTCS},
  pages = 	 {37-42},
  year = 	 {1996},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Grossi03,
  author = 	 {R. Grossi and A. Gupta and J.S. Vitter},
  title = 	 {High-order entropy-compressed text indexes},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {SODA},
  pages = 	 {841-850},
  year = 	 {2003},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Delpratt06,
  author = 	 {O. Delpratt and N. Rahman and R. Raman},
  title = 	 {Engineering the LOUDS Succinct Tree Representation },
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {WEA},
  pages = 	 {134-145},
  year = 	 {2006},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@PhdThesis{Clark96,
  author = 	 {D. Clark},
  title = 	 {Compact Pat Trees},
  school = 	 {University of Waterloo},
  year = 	 {1996},
  OPTkey = 	 {},
  OPTtype = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{RRaman2002,
  author = 	 {R. Raman and V. Raman and S. Srinivasa Rao},
  title = 	 {Succinct indexable dictionaries with applications to encoding k-ary trees and multisets},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {SODA},
  pages = 	 {233-242},
  year = 	 {2002},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Brisaboa2009,
  author = 	 {N. R. Brisaboa and S. Ladra and G. Navarro},
  title = 	 {Directly Addressable Variable-Length Codes},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {SPIRE},
  pages = 	 {122-130},
  year = 	 {2009},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}



@Misc{dag-vector,
  OPTkey = 	 {},
  author = 	 {D. Okanohara},
  title = 	 {dag\_vector},
  howpublished = {https://github.com/pfi/dag\_vector},
  OPTmonth = 	 {},
  OPTyear = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Ferragina2007,
  author = 	 {P. Ferragina and R. Venturini},
  title = 	 {A simple storage scheme for strings achieving entropy bounds},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {SODA},
  pages = 	 {690-696},
  year = 	 {2007},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}



@InProceedings{Jeremy2010,
  author = 	 {J. Barbay and T. Gagie and G. Navarro and Y. Nekrich},
  title = 	 {{Alphabet Partitioning for Compressed Rank/Select and Applications}},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {ISAAC},
  pages = 	 {315-326},
  year = 	 {2010},
  OPTeditor = 	 {},
  volume = 	 {2},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Golynski2006,
  author = 	 {A. Golynski and J.I. Munro and S.S. Rao },
  title = 	 {Rank/select operations on large alphabets: a tool for text indexing },
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {SODA},
  pages = 	 {368-373},
  year = 	 {2006},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@Unpublished{AAAC2011,
  author = 	 {S.Maruyama and M.Baba and H.Sakamoto and K.Sadakane and M.Yamashita},
  title = 	 {A Practical Random Access to Grammar-Based Compression},
  note = 	 {The 4th Annual Meeting of Asian Association for Algorithms and Computation},
  OPTkey = 	 {},
  OPTmonth = 	 {},
  year = 	 {2011},
  OPTannote = 	 {}
}


@InProceedings{Navarro2012-cpm,
  author = 	 {G. Navarro},
  title = 	 {{Wavelet Trees for All}},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle   =  {CPM},
  pages = 	 {2-26},
  year = 	 {2012},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}



@InProceedings{Jansson2012,
  author = 	 {J. Jansson and K. Sadakane and W.K. Sung },
  title = 	 {{CRAM: Compressed Random Access Memory}},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {ICALP},
  pages = 	 {510-521},
  year = 	 {2012},
  OPTeditor = 	 {},
  volume = 	 {1},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

@InProceedings{Navarro12,
  title={{Fast, Small, Simple Rank/Select on Bitmaps}},
  author={Navarro, G. and Providel, E.},
  booktitle={SEA},
  pages = {295--306},
  year={2012}
}

@conference{Okanohara07,
  title={{Practical Entropy-Compressed Rank/Select Dictionary}},
  author={Okanohara, D. and Sadakane, K.},
  booktitle={ALENEX},
  year={2007}
}

@InProceedings{Ram02,
  author =       {R.~Raman and V.~Raman and S.S.~Rao},
  title =        {Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees and Multisets},
  booktitle =    {SODA},
  pages =        {233-242},
  year =         {2002}
}


@Article{Jansson2012-JCSS,
  author = 	 {J. Jansson and K. Sadakane and Wing-Kin Sung },
  title = 	 {Ultra-succinct representation of ordered trees with applications },
  journal = 	 {J. Comput. Syst. Sci. },
  year = 	 {2012},
  OPTkey = 	 {},
  volume = 	 {78},
  number = 	 {},
  pages = 	 {619-631},
  OPTmonth = 	 {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}


@InProceedings{Botelho2007,
  author = 	 {F.C. Botelho and R. Pagh and N. Ziviani },
  title = 	 {{Simple and Space-Efficient Minimal Perfect Hash Functions}},
  OPTcrossref =  {},
  OPTkey = 	 {},
  booktitle = {WADS},
  pages = 	 {139-150},
  year = 	 {2007},
  OPTeditor = 	 {},
  OPTvolume = 	 {},
  OPTnumber = 	 {},
  OPTseries = 	 {},
  OPTaddress = 	 {},
  OPTmonth = 	 {},
  OPTorganization = {},
  OPTpublisher = {},
  OPTnote = 	 {},
  OPTannote = 	 {}
}

