\chapter{Introduction to succinct data structures}
\label{kap:kap1}

% TODO: mozno pridat konkretne struktury(Fenwick tree by \cite{bille2017succinct}, trie by \cite{grossi2015fast}),
% spomenut DS, pouzivajuce bit vector

\section{Motivation}

In many applications, people work with so large amounts of data that the choice of
the data structures is heavily influenced by their space usage. The field
of \textit{succinct data structures} focuses on representing data using as little
space as possible while trying to minimize the time and performance penalty on methods
that these structures support. Many succinct data structures for varied problems
have been devised such as succinct dictionaries~\citep{raman2007succinct},
graph representations~\citep{farzan2013succinct}, grid representations~\citep{chazelle1988functional},
text collections~\citep{ferragina2000opportunistic} and many more, nicely summarized by
\cite{navarro2016compact}. While many of the succinct data structures come with solid
theoretical bounds on the space they use, others look into real-world space usage and
performance.

Succinct data structures are very helpful in scenarios where we work with an immense amount
of data. In these scenarios, using the ordinary data structures may force us to place
the entire representation of data structure onto the slower type of memory storage. This
reduces the usability of data structure and often completely ruins runtime due to the
high amount of slow \textit{I/O operations}. Even if a succinct version of the data structure
may help us to store the data in a faster type of memory (e.g. fast RAM instead of the slower disk),
we pay some price for using it. The price mostly comes in the form of more complex implementation.

In succinct data structures, it is common to distinguish between the space efficiency of
representations more strictly. Suppose that $I$ is the number of bits that are needed to
store the data. We call the data representation
\begin{itemize}
	\item \textit{compact} -- if it uses $\BigO(I)$ bits of space.
	\item \textit{succinct} -- if it uses $I + o(I)$ bits of space,
	\item \textit{implicit} -- if it uses $I + \BigO(1)$ bits of space,
\end{itemize}

In this work, we are mainly concerned with \textit{bit vector}, one of the simplest
data structures that represents a sequence $S$ of zeroes and ones while supporting the
methods:
\begin{itemize}
	\item $\access(S, i)$ -- returning the $i$-th symbol of $S$,
	\item $\rank_c(S, j)$ -- returning the number of occurrences of symbol $c$ in $S$ before $j$-th index,
	\item $\select_c(S, k)$ -- returning the index of $k$-th occurrence of symbol $c$ in $S$.
\end{itemize}
Values of these methods are defined only for integers $i, j, k$ such that $0\leq i<|S|$, $0\leq j\leq |S|$
and $1\leq k\leq \#_c(S)$ where $\#_c(S)$ denotes the number of occurrences of symbol $c$ in $S$. If it is
clear on what sequence we are doing the operation, we use the variants $\access(i)$, $\rank_c(j)$ and $\select_c(k)$.

The reason behind our focus on bit vector and particularly its compressed version
is the fact that it is one of the main building blocks of many succinct data structures.

In the following sections, we introduce some interesting and useful applications of bit vectors.

Throughout our work, we use a unit-cost RAM model with word size of $\Theta(\log n)$ bits.
In this model, arithmetic and logic operations on and between memory words take constant time.

\section{Application 1: Sparse array}

Let $A$ be an array of $N$ elements, each taking $k$ bits of space. We would like
to support accessing the $i$-th element of $A$. For simplicity, we assume that
the elements of the array do not change after the initial construction. A straightforward
representation of this array takes $N\cdot k$ bits of space and in general, it is not
possible to make it better. However, imagine a scenario where a significant portion
of the array is empty and just a handful of elements are present. Take for example a
sparse vector of numbers, where most of the elements are 0. Then we could use a more
space-efficient approach. Let us assume that only $n$ out of $N$ elements are present
and also that $n\ll N$.

One approach considering the sparseness of an array is to store only the non-default
elements as $(\text{position}, \text{value})$ pairs, which takes $n\cdot (k+\lg N)$
bits of space, where by $\lg x$ we denote $\ceil{\log_2 x}$. If we just store these
pairs sorted by the position, accessing the $i$-th element takes time $\BigO(\log n)$.
We may also use a hash table to obtain a constant time solution but this comes with
additional memory overhead.

An alternative approach, using the bit vector, is to store non-default elements in
a packed array $P$ of length $n$ taking $n\cdot k$ bits of space. Alongside $P$, we
store a bit vector $B$ of length $N$ where
\[
   B[i]=
\begin{cases}
   1,& \text{if $A[i]$ is occupied} \\
   0,& \text{if $A[i]$ is empty/default value.}
\end{cases}
\]

Using this representation of $A$, if we want to access the $i$-th element, we first check for
the value of $B[i]$. If it is zero, we return the default value. Otherwise, we need to find
how many ones are preceding this particular one in $B$ to identify the location of the requested
element in array $P$. This is where we find the $\rank_1$ method useful. Similarly, to obtain
the position of $i$-th non-empty value in $A$, we can use the $\select_1$ method.

The total space used by this representation is $N+n\cdot k+R$ where $R$ is the space required
to support an efficient $\rank_1$ query over $B$. As we shall show in Section~\ref{section:rank},
$\rank$ can be implemented succinctly in constant time, i.e., with sublinear space overhead
$R = o(N)$. So if we are provided with bit vector implementation along with $\access$ and $\rank$
methods, we are able to reduce the total space used from $k\cdot N$ to $N+n\cdot k+o(N)$ bits.
Note that in practice, for a really small number of non-default values, the hashtable representation
takes up less space. On the other hand, bit vector provides us with a solution that is usable for
scenarios when $A$ is mediumly filled in, e.g., $n/N>0.1$.

\section{Application 2: Storing elements of non-uniform length}

Let us consider another problem of representing an array of elements of variable length.
Elements with variable lengths can often arise in succinct data structures. Even though
we can store these elements one after another in memory, with the variable-length elements,
we do not have an easy and fast way to tell where is the $i$-th element located.

Let us assume that we want to represent $n$ elements of variable length. The first solution
is to allocate the array of length $n\cdot k_{MAX}$ bits where $k_{MAX}$ is the number of
bits used for the element with the longest bit representation. This approach enables constant
time access but wastes a lot of space.

A second possible solution is to allocate a bit array $R$ where the elements are stored one
after another in their raw bit representation. To locate the $i$-th element, we add a helper
array $P$, such that $P[i]$ is the position where the $i$-th element begins in $R$. The helper
array $P$ takes roughly $\Theta(n\log |R|)$ bits of space as each entry contains an index into
the array $R$.

The helper array $P$ can be replaced by a bit vector of length $|R|$, storing
ones at positions where some element in $R$ begins (see an example in
Fig.~\ref{obr:VariableSizedElements}). Identifying the beginning of the $i$-th element now
comes down to efficiently locating the $i$-th one in the helper bit vector, which can be
answered using the $\select_1$ method. In Chapter~\ref{kap:kap2}, we shall see how this
method can be implemented efficiently.

\begin{figure}
	\centerline{
	\begin{tabular}{l|l|l|l|l|l|l|l|l|l|l|}
	\cline{2-11}
	\textbf{Raw binary representation $R$:} & 1          & 1 & 0 & 1 & 1          & 1 & 1          & 0 & 1 & 0          \\ \cline{2-11} 
	\textbf{Beginnings of elements}          & \textbf{1} & 0 & 0 & 0 & \textbf{1} & 0 & \textbf{1} & 0 & 0 & \textbf{1} \\ \cline{2-11} 
	\end{tabular}
	}
	\caption[TODO]{Raw binary representation of elements 1101, 11, 101 and 0 stored
	one after another. Note that the helper bit array is of the same size as $R$, with
	ones on the positions where a new element begins.}
	\label{obr:VariableSizedElements}
\end{figure}

\section{Application 3: FM-index}
% sources to help understand https://www.dcc.uchile.cl/TR/2005/TR_DCC-2005-004.pdf

Let us now consider a practically interesting application within a more complex data structure.
As we shall see, succinct data structure used to solve this problem also uses bit vector and other
building blocks commonly used in succinct data structures.

Let us consider a text $T$. After some initial preprocessing, we would like to quickly answer
questions such as ``how many times is some pattern $P$ contained in $T$'' and also ``where in $T$
are the occurrences of $P$ located''. This problem is generally called a \textit{text indexing}
problem and is particularly useful in bioinformatics, where we often have a very long sequence of DNA
and we are interested in searching for some subsequences in it, e.g., the problem of \emph{read alignment}
(\cite{langmead2009ultrafast} and \cite{li2010fast}).

One of the solutions that can be used for shorter texts is based on a \textit{suffix array} of~$T$.
This is a data structure which stores information about the lexicographical order of suffixes of $T$.
More precisely, the $i$-th position of suffix array $S$, stores the starting position of the suffix
that is $i$-th in the lexicographical order. For simplicity, in this section, we assume that every
text $T$ contains at the end a special symbol {\tt \$} and this symbol is also lexicographically
smaller than any other symbol contained in $T$. Searching for pattern $P$ in suffix array of $T$ uses
the fact that if $P$ is contained in $T$, it is located at the beginning of some suffixes. Since these
are lexicographically sorted, the result forms a consecutive subsequence of $S$. The suffix array consumes
$\BigO(n\log n)$ memory asymptotically and in practice uses about $5n$ bytes of space if the text symbol
can be encoded using 1 byte and offset of the suffix can be stored in the 32-bit integer. In practice, it
is possible to get to much lower number of bits, if we use succinct data structures.

\textit{FM-index}, proposed by \cite{ferragina2000opportunistic}, is a succinct data structure that
is in some aspects similar to suffix array. FM-index can find the pattern in the preprocessed text
in time complexity close to linear in $|P|$. Particular space usage depends on the compressibility
of the text but the resulting space used by FM-index is in many cases smaller than the space used for
the original text $T$. For instance, FM-index over a DNA sequence can take just 30--40\% of the space
taken by the original text $T$ as was observed by \cite{ferragina2001experimental}. 

In the rest of this section, we will explain how we construct the FM-index, how we search in it
and how/why FM-index uses bit vector with method $\rank$. This is particularly interesting for us
as later, in Chapter 4, we use FM-index to benchmark our new implementation of bit vector.

\paragraph{Burrows-Wheeler transform}

\textit{Burrows-Wheeler transform}(BWT; \cite{burrows1994block}) is a key
part of the FM-index. BWT of a text $T$ gives us a sequence $\mathit{T_{BWT}}$ of the same
length. Furthermore, this operation is reversible in a sense that we are able to reconstruct
the original text $T$ only using $\mathit{T_{BWT}}$. This transformation is used as a
preprocessing step of compression algorithms such as \textit{bzip2}~\citep{seward1996bzip2}
and was studied more by \cite{manzini2001analysis}, since $T_{BWT}$ is oftentimes easier
to compress than the original text. Let us first explain the construction and then provide
an intuition why it is easier to compress.

Consider a sequence $T$ of symbols over an arbitrary alphabet $\Sigma$. Take all the cyclical
rotations $T_1, T_2, \ldots , T_n$ of $T$, sort them lexicographically and form a (conceptual)
table $M$ (see an example in Fig.~\ref{obr:BWT}). Note that each column is a permutation of $T$.
The first column, $F$, consists of all the characters of $T$, sorted. The last column, $L$, is
the Burrows-Wheeler transform of $T$.

FM-index stores just columns $F$ and $L$ from matrix $M$. As the first column of $M$ consists of
runs of sorted symbols, it can be represented in FM-index using the helper array $\Count$ where
$\Count[c]$ is the number of occurrences of symbols \emph{preceding} $c$. Note that the run of
symbol $c$ in $F$ starts at the index $\Count[c]$.

\begin{figure}
	\centerline{
	\begin{tabular}{l|c|ccccc|c|}
	\cline{2-8}
	  & $F$ & \multicolumn{5}{l|}{} & $L$   \\ \cline{2-8} 
	0 & {\tt \$}	& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt b}}		& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt a}}	& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt n}}	& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt a}}	& {\color[HTML]{C0C0C0} \tt n}  & {\tt a}  \\ \cline{2-8} 
	1 & {\tt a}  		& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt \$}} 	& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt b}}	& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt a}}	& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt n}}	& {\color[HTML]{C0C0C0} \tt a}  & {\tt n}  \\ \cline{2-8} 
	2 & {\tt a}		& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt n}}		& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt a}}	& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt \$}}& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt b}}	& {\color[HTML]{C0C0C0} \tt a}	& {\tt n}  \\ \cline{2-8} 
	3 & {\tt a}		& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt n}}		& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt a}}	& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt n}}	& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt a}}	& {\color[HTML]{C0C0C0} \tt \$}	& {\tt b}  \\ \cline{2-8} 
	4 & {\tt b}		& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt a}}		& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt n}}	& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt a}}	& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt n}}	& {\color[HTML]{C0C0C0} \tt a}  & {\tt \$} \\ \cline{2-8} 
	5 & {\tt n}		& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt a}}		& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt \$}}& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt b}}	& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt a}}	& {\color[HTML]{C0C0C0} \tt n}  & {\tt a}  \\ \cline{2-8} 
	6 & {\tt n}		& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt a}}		& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt n}}	& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt a}}	& \multicolumn{1}{c|}{{\color[HTML]{C0C0C0} \tt \$}}& {\color[HTML]{C0C0C0} \tt b}  & {\tt a}  \\ \cline{2-8} 
	\end{tabular}
	\hspace{4em}
	\begin{tabular}{l l l}
		sorted suffixes\\
	\hline
		\tt \$ \\
		\tt a\$ \\
		\tt ana\$ \\
		\tt anana\$ \\
		\tt banana\$ \\
		\tt na\$ \\
		\tt nana\$ \\
	\end{tabular}
	}
	\caption[TODO]{On the left, we may observe the matrix $M$ filled with cyclic rotations of sequence
	$T = \mathtt{banana\$}$. On the right, we may observe the sorted suffixes of $T$(content of suffix array). The
	Burrows-Wheeler transform of $T$ is string $L=\mathtt{annb\$aa}$ -- the last column of $M$.
	Note that in practice, we do not need to construct the whole table as more efficient algorithms exist.
	It is also notable that matrix $M$ includes very similar information compared to suffix array as
	rows of $M$ basically start with individual suffixes. FM-index stores only representation of columns $F$
	and $L$, the grey area is not stored.
	}
	\label{obr:BWT}
\end{figure}

BWT is usually more compressible than the original text because it frequently contains runs of the same
symbol. This can be better explained on an example. Consider us having BWT of a text containing
a lot of mentions of the word {\tt house}. All the rotations prefixed with {\tt ouse} will form a
consecutive subsequence of rows of $M$. Some of these rows will end with symbol {\tt m} for word {\tt mouse},
some of them with {\tt p} for {\tt spouse} but many of these lines contain {\tt h} at the end as this
is very common symbol preceding {\tt ouse} in the text.

Generally, it is common for (natural) texts that symbols can be predicted quite well from the context
following them. If we sort these contexts (beginnings of rows of $M$), then the last row will often
contain runs of the same symbol but also subsequences where just a handful of symbols occur.

\paragraph{Searching in an FM-index}

Searching in an FM-index is based on two important properties of matrix $M$:

\begin{enumerate}
	\item Rotations starting with prefix $w$ form a consecutive subsequence of rows in $M$.
	\label{chapter1:fmindexprop:prop1}
	\item The $i$-th occurence of symbol $c$ in $F$ corresponds to the $i$-th occurence of $c$ in~$L$.
	\label{chapter1:fmindexprop:prop2}
\end{enumerate}

The first property also enabled us to search for a pattern in a suffix array. The second property
is less trivial to observe. Let us take two rows in $M$, namely $T_i$ and $T_j$ such that
$i<j$. Let $T_i$ be of the form $cA$ and $T_j$ of the form $cB$ where $c$ is a symbol from
the text and $A$ and $B$ are sequences of symbols. Since $i<j$, it follows that $A<B$ and
this means that rotated rows $Ac$ and $Bc$ are in the same relative order as the original rows.
From this observation, it follows that the relative ordering of the same symbol is preserved
between $F$ and $L$.

In the next part, we describe how we search for some arbitrary pattern $P=p_0p_1\ldots p_{n-1}$
in FM-index. Let us denote suffix of $P$ starting at $i$-th element $P_{i\ldots}$. The result of
the search for $P$ is a range of $M$’s rows that have $P$ as their prefix. The search for these
rows proceeds iteratively from the end of $P$ to its beginning. At first, we find the range of
rows starting with  $P_{n-1\ldots}$, then gradually continue by finding rows that start with
$P_{n-2\ldots}, P_{n-3\ldots}$ and so on up to $P_0=P$. In every step, these rows form a
consecutive subsequence of rows of $M$ so we will maintain just the beginning and the end of
the interval. This follows from the observation \ref{chapter1:fmindexprop:prop1}.

First, let us show the process on an example (see Fig.~\ref{tab:fm_index_example}). Assume we are
searching for the word {\tt house} and we already found the range of rows in $M$ that start with
{\tt ouse} (rows 200--204). Symbols in the last column of this range correspond to the symbols
preceding {\tt ouse} in the text. We may observe different symbols in arbitrary order there such as
{\tt m} for the word {\tt mouse} or {\tt h} for {\tt house}.

To search for the range starting with {\tt house}, we look into the range of all rows beginning with the
symbol {\tt h}. Locating this range is easy as it starts at position $\Count[\texttt{h}]$ and ends before
$\Count[\texttt{i}]$. Rows in this range are sorted according to the second symbol so there will be for
example some lines continuing with symbol {\tt a} if the text contained word {\tt hashtag} or symbol {\tt e}
if the word {\tt head} was present in the text. Among them, lines starting with {\tt house} are located,
but we do not store anything except for $\Count$ and $L$. However, we already found the location of
suffixes starting with {\tt ouse}. All the symbols {\tt h} in the last column correspond to left rotations
of rows 100--105 by one. Note that rotations of row 103 and 104 are rows 201 and 204. Rotations of
\texttt{hashtag}/\texttt{head}/\texttt{hind} start with \texttt{ash}/\texttt{ead}/\texttt{ind}, so they
come \emph{before} row 200. On the other hand, rotation of row 105, starts with {\tt uge}, which comes
\emph{after} {\tt ouse}. To locate the offset of {\tt house} along the lines starting with {\tt h},
we need to count the number of occurences of {\tt h} in $L$ before the occurrences of {\tt ouse}.  

% https://docs.google.com/spreadsheets/d/1C7O2qsEEnjYkf2N1gX6HbS8sZu3UNl86VIxL3X9msVo/edit#gid=0
% TODO: pridat \tt ked sa to trosku zastabilizuje
\begin{figure}
	\centerline{
	\begin{tabular}{c|c|l|l|l|l|l|l|l|l|l|l|}
																	  \cline{5-10}\cline{2-3}\cline{12-12}
				    & Row n.     & F &  &   &   &   &   &   &   &   & L \\ \cline{5-10}\cline{2-3}\cline{12-12}
				    & 0          &   &  &   &   &   &   &   &   &   &   \\ \cline{5-10}\cline{2-3}\cline{12-12}
				    & \ldots     &   &  &   &   &   &   &   &   &   &   \\ \cline{5-10}\cline{2-3}\cline{12-12}
	$\Count{[}h{]}$ & 100        & h &  & a & s & h & t & \ldots   &   &   &   \\ \cline{5-10}\cline{2-3}\cline{12-12}
				    & 101        & h &  & e & a & d &   &   &   &   &   \\ \cline{5-10}\cline{2-3}\cline{12-12}
	                & 102        & h &  & i & n & d &   &   & b &   & e \\ \cline{5-10}\cline{2-3}\cline{12-12}
	$b_0$		    & 103        & h &  & o & u & s & e &   &   &   &   \\ \cline{5-10}\cline{2-3}\cline{12-12}
	                & 104        & h &  & o & u & s & e &   &   &   &   \\ \cline{5-10}\cline{2-3}\cline{12-12}
	$e_0$			& 105        & h &  & u & g & e &   &   &   &   &   \\ \cline{5-10}\cline{2-3}\cline{12-12}
	                & \ldots     &   &  &   &   &   &   & \ldots  &   &   &   \\ \cline{5-10}\cline{2-3}\cline{12-12}
	$b_1$           & 200        & o &  & u & s & e &   &   &   &   & m \\ \cline{5-10}\cline{2-3}\cline{12-12}
				    & 201        & o &  & u & s & e &   &   &   &   & h \\ \cline{5-10}\cline{2-3}\cline{12-12}
				    & 202        & o &  & u & s & e &   &   &   &   & m \\ \cline{5-10}\cline{2-3}\cline{12-12}
				    & 203        & o &  & u & s & e &   & \ldots  & s &   & p \\ \cline{5-10}\cline{2-3}\cline{12-12}
				    & 204        & o &  & u & s & e &   &   &   &   & h \\ \cline{5-10}\cline{2-3}\cline{12-12}
	$e_1$           & 205        &   &  &   &   &   &   &   &   &   &   \\ \cline{5-10}\cline{2-3}\cline{12-12}
	                & \ldots     &   &  &   &   &   &   &   &   &   &   \\ \cline{5-10}\cline{2-3}\cline{12-12}
	\end{tabular}
	}
	\caption[TODO]{We are counting occurences of \texttt{house} and we already found the
	range of rows starting with \texttt{ouse} given by $b_1$ and $e_1$. To find the range of rows starting
	with \texttt{house}, we first look at the position where rows starting with \texttt{h} begin in $F$ -- $\Count[h]$.
	However, not all of the rows starting with \texttt{h} continue with \texttt{ouse}. To find this subinterval,
	we use the information from previous iteration. We count the number of occurences of \texttt{h} in $L$ before
	position $b_1$ and use this as offset into run of symbol \texttt{h}. In this particular case,
	$b_0 = \Count[h] + rank_h(L, b_1) = 100 + 3 = 103$ and
	$e_0 = \Count[h] + rank_h(L, e_1) = 100 + 5 = 105$.
	}
	\label{tab:fm_index_example}
\end{figure}

In general, to count the number of occurrences of pattern $P$, we first find the subsequence of rows of $M$
beginning with $P_{n-1\ldots}$. As this is just one symbol, $p_{n-1}$, the initial subsequence is a run
of symbol $p_{n-1}$ in $F$ given by
\begin{align*}
	b_{n-1}&=\Count[p_{n-1}] \\
	e_{n-1}&=\Count[p_{n-1}+1].\\
\end{align*}

The next step is to find the subsequence of rows of $M$, given by $b_{n-2}$ and $e_{n-2}$, which has
$P_{n-2\ldots}$ as a prefix. As we already located rows beginning with $P_{n-1\ldots}$, we can use
this information. In a range from $b_{n-1}$ to $e_{n-1}$ some rows end with symbol $p_{n-2}$. These
are rows which after being rotated, create subsequence we are looking for. Subsequence we are looking
for is also subsequence of a run of symbol $p_{n-2}$ in $F$, starting from $\Count[p_{n-2}]$ spanning
rows up to $\Count[p_{n-2}+1]$. To find the beginning and end of our subsequence inside of this run, we
compute the number of occurrences of symbol $p_{n-2}$ in $L$ up to $b_{n-1}$, the start of previous
subsequence of rows and also the number of occurrences of symbol $p_{n-2}$ in $L$ up to $e_{n-1}$
giving us its end. This works thanks to the property \ref{chapter1:fmindexprop:prop2}. Thus giving us the
new subsequence
\begin{align*}
	b_{n-2}&=\Count[p_{n-2}] + \rank_{p_{n-2}}(L, b_{n-1}) \\
	e_{n-2}&=\Count[p_{n-2}] + \rank_{p_{n-2}}(L, e_{n-1}).\\
\end{align*}
We continue and repeat the previous step until we compute $b_0$ and $e_0$ or until $b_i=e_i$ for some $i$
(in this case, the searched word is not present in the text). The possible pseudocode for counting the number
of occurrences of $P$ in $T$ is in listing \ref{alg:fm_index_count}.

\begin{algorithm}
\caption{Count number of occurrences of pattern $P$ in an FM-index}\label{alg:fm_index_count}
\SetKw{KwDownto}{downto}
\KwData{$P\in \Sigma^n$}
$b \gets \Count[P[n-1]]$\;
$e \gets \Count[P[n-1]+1]$\;
\For{$i=n-2$ \KwDownto $0$} {
	\If{$b = e$}{
		break\;
	}
	$b \gets \Count[P[i]] + \rank_{P[i]}(L, b)$\;
	$e \gets \Count[P[i]] + \rank_{P[i]}(L, e)$\;
}
\KwRet{$e-b$}
\end{algorithm}

As we can see, the FM-index requires the method $\rank$ on a general string. In the next
paragraph, we show that we can use bit vectors to provide a reasonable implementation of
the $\rank$/$\select$ methods on a sequence over a general alphabet.

\paragraph{Wavelet tree}
\label{section:WaweletTree}

Let us assume for a moment that we have a bit vector implementation supporting methods $\access$,
$\rank$ and $\select$. We have a sequence $S$ of length $n$ over an arbitrary alphabet $\Sigma$.
Our goal is to build vector over this sequence supporting the methods $\access$, $\rank$ and $\select$.

A straightforward approach that uses bit vector is to have one bit vector $B_c$ for every
symbol $c$ from the alphabet $\Sigma$, storing ones at positions where $c$ occurs in $S$
\[
    B_c[j]= 
\begin{cases}
	1,& \text{if } S[j]=c \\
    0,& \text{otherwise.}
\end{cases}
\]

This is very fast because each $\rank$ and $\select$ operation can be answered using only a single
binary $\rank$ or $\select$. However, we use roughly $|\Sigma|$ times more space than the single bit
vector over this sequence would use. Or in other words, the space usage is growing linearly with the
alphabet size.

\textit{Wavelet tree} data structure proposed by \cite{grossi2003high} uses a divide-and-conquer
approach to solve this problem. It takes the alphabet $\Sigma$ of size $\sigma$ and recursively
splits the alphabet into two subsets creating a hierarchical partitioning of an alphabet. In the
root node of the tree, the alphabet $\Sigma$ is split into two subsets $\Sigma_0$ and $\Sigma_1$
of roughly equal size. A bit vector $B$ of size $n$ is stored in this node such that
\[
    B[i]= 
\begin{cases}
    0,& \text{if } S[i]\in \Sigma_0\\
    1,              & \text{otherwise.}
\end{cases}
\]

Then two strings $S_0$ and $S_1$ are created from $S$ by taking just symbols
from $\Sigma_0$ and $\Sigma_1$, respectively. The left and right child of the root node
are then built by recursively applying the same idea on subsequences $S_0$ and $S_1$ until
we end up with a trivial unary alphabet at the leaves. An example of this partitioning is
shown in Fig.~\ref{obr:WaveletTreeExample}. It follows that the depth of the wavelet tree
is $\BigO(\log \sigma)$.
\begin{figure}
	\centerline{
		\includegraphics[width=0.9\textwidth, height=0.3\textheight]{images/wavelet_tree}
	}
	\caption[TODO]{Wavelet tree representation of text $S=\mathit{aabadacdc}$. We can see how
	the recursive partitioning of the alphabet works. In every node, we also show the
	subsequence represented (grey text) in the subtree of the node. Note that we include the
	grey parts in the visualisation to help in understanding but they are not stored by
	the data structure.
	}
	\label{obr:WaveletTreeExample}
	% based on https://simongog.github.io/assets/data/sdsl-slides/tutorial#23
	% source at https://docs.google.com/drawings/d/1cJyda3bdTluajr3iXu1x1iL5HF0JPZqAHw6jwct9KLI/edit
\end{figure}

In a wavelet tree, both $\rank_c$ and $\select_c$ methods on the original sequence can
be implemented using $\rank$/$\select$ methods applied on bit sequences that are stored
in nodes along the path from the root to the leaf containing symbol $c$. Thus, the
number of $\rank$ and $\select$ queries on individual bit vectors depends on the depth of
a leaf containing queried symbol $c$. Regarding the space usage of wavelet tree; as on every
level of the wavelet tree, we store roughly a bit vector of length $n$, it is possible
for this representation to use just $n\lg \sigma+o(n)$ bits of space.

Even if this version of wavelet tree can be used inside of the FM-index, it is possible to
make a solution that is faster and more space efficient in some scenarios. Time complexity
of both methods, $\rank_c$ and $\select_c$, depends on the time complexity of the bit vector
implementation used in the nodes, but also on the depth of symbol $c$ in the tree. This depth
is now for every single symbol $\BigO(\log \sigma)$.

To obtain a better solution, let us give another perspective on the wavelet tree and assign
a single bit to every edge -- {\tt 0} for left and {\tt 1} for right (see Fig.~\ref{obr:WaveletTreeExample}).
Now, we can think of the wavelet tree as an assignment of a binary code to every alphabet symbol.
The code of a symbol $c$ is obtained by concatenating bits along the path from the root to the leaf
for symbol $c$.

The idea proposed by~\cite{makinen2005succinct} is to shape the wavelet tree in such a way that
a code of every symbol is equal to its Huffman code. The first advantage is that the space used
decreases from $\BigO(n\log \sigma)$ to $\BigO(nH_0(S))$. The second advantage is that if
we query for each symbol according to its frequency, then on average, we need to visit
$\BigO(H_0)$ nodes rather than $\BigO(\log \sigma)$, where $H_0$ is the empirical zero-order
entropy, defined as $$H_0(S)=\sum_{c\in\Sigma} \frac{n_c}{n} \log \frac{n}{n_c},$$
where $n_c$ denotes number of occurrences of symbol $c$ in sequence $S$ of length $n$. The value
of zero-order entropy is a lower bound for the number of bits that $S$ can be compressed to by
compressor that considers only frequencies of symbols and $H_0(S)\leq \lg\sigma$. In the worst
case, we need $\lg \sigma$ bits to store every symbol. In some cases, however, it is the case
that frequencies of symbols are not even and thus $H_0(S)\ll \lg\sigma$.

The maximum depth of a Huffman shaped wavelet tree may be bigger compared to the original, however,
\cite{grabowski2004first} showed that we can enforce the maximum depth to be $\BigO(\log \sigma)$
with the average depth limited by $H_0+2$. This is, however, as they claimed, not very practical.
The important fact is that with Huffman shaped wavelet tree, it is possible to decrease the space
usage in some scenarios but also average number of nodes accessed and thus decrease the average
query time of $\rank$ and $\select$.

It was shown by \cite{grossi2003high} that it is also possible for the wavelet tree of original shape
to achieve space usage of $nH_0(S) + o(n\log\sigma)$ bits, if the bit vector implementation that takes
space close to the zero-order entropy is used inside of the tree nodes.

In practice, it is beneficial to combine these two ideas and use the Huffman shaped wavelet tree with
compressed bit vector inside.

\paragraph{Space usage of FM-index}

We already showed how FM-index is constructed and how the searching in FM-index works and can be
supported should we have a data structure that supports $\rank$ and $\select$ on sequences over the general
alphabet. We also showed how wavelet tree, one such data structure works.

\cite{karkkainen2011fixed} showed that combining Huffman shaped wavelet tree and compressed bit vector taking
space close to zero-order entropy brings down the total space used by FM-index to $nH_k(T)+o(n)\log\sigma$ for
the text $T$ of length $n$ over alphabet of size $\sigma$ where $H_k$ is $k$-th order empirical entropy. This
quantity is defined as $$H_k(S) = \frac{1}{n} \sum_{w\in \Sigma^k} |w_S| H_0(w_S)$$ where $w_S$ is the string
consisting of concatenation of symbols following $w$ in $S$. This measure gives us the lower bound for number
of bits that $S$ can be compressed to by compressor that considers context of length $k$ when encoding each
symbol of $S$.

In this chapter, we presented some useful applications of the bit vector. We looked more closely on
FM-index, the data structure used for the problem of text indexing. There, we encountered the
problem of answering $\rank$ and $\select$ over the general alphabet and described wavelet tree,
one possible data structure that can be used to solve it, assuming we have an implementation of
bit vector supporting $\access$, $\rank$ and $\select$ methods. We also showed that compressed bit
vector that takes space close to zero-order entropy can be used to obtain succinct representation of
a wavelet tree but also very space efficient version of FM-index.

\section{Outline of the Thesis}

The goal of this thesis is to describe the current state of the bit vector implementations
supporting $\access$, $\rank$ and $\select$ methods and come up with improvements that
make bit vectors more usable in practice. This can be either by speeding up the current
implementations, saving some additional space but also by combination of these two as
obtaining some new trade-offs of query time and space used by the implementation can
also open doors to new applications.

In the second chapter, we describe the state-of-the-art implementations of $\rank$ and
$\select$ methods over bit sequence. We discuss what are the theoretically optimal
solutions but also what are their practical drawbacks. We then proceed to describe one
of the widely used implementations of a compressed bit vector called \textit{RRR}.

In the third chapter, we propose our own modifications to the implementation of
a compressed bit vector based on RRR and we discuss theoretical aspects of these
modifications.

In the fourth chapter, we show our proposed implementation of previously devised
methods and experimentally test and evaluate them. We measure the performance
of our solution on artificial as well as real-world data. Finally, we demonstrate
the capabilities of our new bit vector inside of the FM-index.