text:
\subsubsection{\stid{3.12} Sub-project: SUNDIALS}
\label{subsubsect:SUNDIALS-hypre}

\paragraph{Overview}

This project is enhancing the SUNDIALS library of numerical software packages for integrating differential systems in time using state-of-the-art time step technologies for use on exascale systems.

The SUNDIALS suite of packages provides efficient and adaptive time integrators and nonlinear solvers.  The packages are written using encapsulation of both data structures and solvers, thus allowing easy incorporation into existing codes and flexibility to take advantage of new solver technologies and packages.  SUNDIALS provides both multistep and multistage methods designed to evolve stiff or nonstiff ordinary (ODE) and differential algebraic (DAE) systems
with efficient accuracy-driven time step selection.
SUNDIALS also provides both Newton and fixed point (with optional acceleration) nonlinear solvers and scaled Krylov methods with hooks for user-supplied preconditioners.  Users can also supply their own nonlinear and linear solvers under the integrators.  SUNDIALS is released with data structures supporting several programming environments.  Users can employ these supplied structures or provide their own.

Through software infrastructure developments, this project is enabling the efficient and robust SUNDIALS time integrator packages to easily interoperate with applications evolving time dependent systems as well as with external linear and nonlinear solver packages developed for exascale computing.  In addition, this project is providing support for integrating several independent ordinary differential equation systems simultaneously on GPUs as part of multiphysics applications.  Lastly, this project is supporting the deployment and use of SUNDIALS packages within ECP applications, mainly through incorporation into the discretization-based Co-Design Centers, AMReX and CEED.

%% Efficient time integrators are essential for ECP because they are at the core of every time-dependent simulation application.  However, many applications do not use state-of-the-art methods, and if they do, they often do not yet use them fully on their systems.  For example, at the start of the ECP the astrophysics code, Nyx, used an adaptive integration package for solving individual reactions.  However, by applying a time integration package to a larger reaction system, the code is able to derive significant speedups through use of GPUs that execute more calculations concurrently thus getting an accurate solution much faster.  By allowing for solvers tuned to exascale systems and vectors that are heterogeneous, SUNDIALS will be more applicable for use in multiphysics systems running on exascale platforms.

\paragraph{Key Challenges}

Current implementations of efficient time integrators face challenges on many fronts.
First, applications need both efficient integrators and ones that can interface easily with efficient linear algebra
packages to solve subservient linear systems.  In addition, integrators and their interfaces to both solver libraries
and applications must be frequently updated to keep up with rapid advances in system architectures. Some ECP applications require solution of many small systems of ODEs in parallel on GPUs giving rise to the need for
a GPU-enabled ODE integrator that can be used in parallel for many systems at once. Lastly, ECP applications are in need of ODE integrators that can provide increasing functionalities, such as non-identity mass matrices for solving systems of ODEs with finite element spatial discretizations, and maintaining solutions on a constraint manifold.

\paragraph{Solution Strategy}

This project includes a number of implementation activities that will prepare the SUNDIALS suite of time integrators for exascale systems found in ECP applications.  A major activity is the development of support for using the CVODE multistep
ODE integration package to evolve multiple systems of ODEs in parallel using GPUs.  Two strategies are being pursued for this capability.  First, multiple ODE systems are being integrated in each CVODE instance with multiple instances started on a GPU, each with a different CUDA stream.  In this case, CVODE is being equipped with a batched direct linear
solver capable of using a GPU.  In addition, differing methods of choosing time steps and nonlinear solver convergence strategies are being investigated to help optimize performance of CVODE on these aggregated systems.  The second strategy is development of a version of CVODE callable on a GPU, although this strategy is most appropriate for very small ODE systems.

This project is also developing efficient ways of handling time-dependent mass matrices for use by the ARKode multistage integrator package and use from within the MFEM library.  This capability will likely be supported at the system function evaluation level and will make finite element methods much more efficient with the
SUNDIALS multistage integrator.  In order to handle ODE systems with constraint manfiolds, an older package, CPODES, is being evaluated and rewritten with the current SUNDIALS interfaces.  This constraint manifold capability will be interfaced with ECP application codes for method evaluation and testing.

Lastly, the SUNDIALS team will support ECP applications in interfacing SUNDIALS packages into their
software and in the optimal use of the time integration algorithms.  This support will also include working with the application teams to help them install SUNDIALS and adjust their build systems to appropriately link with the SUNDIALS library.

%%  A major activity is a redesign of all linear solver interfaces and encapsulation of the nonlinear solvers within the time integrators in SUNDIALS.  The new linear solver interfaces make it much easier to interface external solver packages while maintaining the efficiency of SUNDIALS integrators. Encapsulating the nonlinear solvers reduces redundant code and allows the time integrators to better leverage common code resulting in a lower code maintenance burden within SUNDIALS.  In addition, the integrators are able to take advantage of outside nonlinear solvers.

%% This project also introduced a set of optional fused vector kernels into SUNDIALS.  These kernels execute multiple vector operations at once thereby reducing the number of kernel launches in GPU environments and also reducing the number of communications required for reduction operations.  These new kernels were added to all supplied SUNDIALS vectors and are invoked through optional interfaces.

%% Lastly, this project is developing a many-vector capability for SUNDIALS.  Due to the tight data encapsulation within SUNDIALS, users are able to supply any vector they would like underneath the integrators.  This project will supply the infrastructure needed to make it easy to place a vector of vectors underneath the integrators.  This vector of vectors is essential for later implementation of time integrators that will advance various parts of the system with different time step sizes.  This many-vector capability will also ease the use of different programming environments as differing vectors can be instantiated on different parts of a hybrid machine.

\paragraph{Recent Progress}

In October of 2019, SUNDIALS 5.0.0 was released, including new vector structures that support flexible partitioning of solution data among different processing elements (e.g., CPU + GPU) or for multi-physics problems, an additional vector structure that supports MPI+X paradigms, and interfaces
to high performance algebraic solver packages (SUPERLU\_DIST, the NVIDIA CUDA-based
batched sparse QR direct linear solver, and the PETSc nonlinear solver SNES package).
In September of 2019, the SUNDIALS team released a document quantifying performance of SUNDIALS codes on
a demonstration problem that solves the three-dimensional nonlinear compressible Euler equations combined with advection and reaction of chemical species run using 40 cores on each of 2 to 3,456 nodes of the ORNL Summit machine.
Figure \ref{fig:sun-many-demo} shows a diagram of the many-vector used in the demonstration problem where some solution components are distributed across the MPI processor decomposition and some are fully local.
In addition to these activities, the SUNDIALS team has been collaborating closely with the AMReX Co-Design Center team to
design effective interfaces to SUNDIALS time integrators from AMReX for applications using ODE integrators,
such as for chemistry reaction systems as in Nyx, Castro, and PELE.  The PELELM and Nyx applications have both demonstrated use of the CVODE package from SUNDIALS within test runs utilizing new capabilities from SUNDIALS to run on Summit with GPUs.

%% In May of 2018, SUNDIALS 4.0.0-dev was released, including new fused vector kernels in the vector API and in all supplied vectors.  Results show speedup from using these routines, especially for parallel reductions.  In September of 2018, SUNDIALS 4.0.0-dev.2 was released, including a full redesign of the nonlinear solver interfaces to the time integrators and encapsulation of the nonlinear solevrs.  Figure \ref{fig:sunorg1} shows the new organization of SUNDIALS where separate nonlinear solver interfaces are provided for Newton and fixed point nonlinear solver methods.  These interfaces are shared across all SUNDIALS integrators.
%% Individual integrators have the freedom to supply specific information from the integrator that controls the solver.  In addition, the SUNDIALS team has been collaborating closely with the AMReX Co-Design Center team to
%% design effective interfaces to SUNDIALS time integrators from AMReX for applications using ODE integrators,
%% such as for chemistry reaction systems as in Nyx, Castro, and PELE.

\begin{figure}[htb]
	\centering
	\includegraphics[width=6in]{projects/2.3.3-MathLibs/2.3.3.12-SUNDIALS-hypre/manyvector_v2.pdf}
	\caption{\label{fig:sun-many-demo}The demonstration code uses the new many-vector capability to store the solution as a collection of distributed ($\rho,m_i, e_t$) and purely local ($c$) vectors.}
\end{figure}

\paragraph{Next Steps}

During the remainder of FY20, this project team will:
\begin{enumerate}
\item Release SUNDIALS with new CVODE options for solving multiple ODE systems in parallel on GPUs.
\item Complete a prototype of CPODES.
\item Release of SUNDIALS with a time-dependent mass matrix capability.
\item Continue to support AMReX and CEED Co-Design Centers in their use of SUNDIALS for ECP applications.
\end{enumerate}

ext: tex

max_stars_repo_name: Franckcappello/ECP-ST-CAR-PUBLIC

max_issues_repo_name: Franckcappello/ECP-ST-CAR-PUBLIC

max_forks_repo_name: Franckcappello/ECP-ST-CAR-PUBLIC


text:
%\documentclass[12pt]{article}
\documentclass[final,3p,12pt]{elsarticle}
\usepackage{enumerate}
\usepackage{courier}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{float}
\usepackage{setspace}
\usepackage{fancyvrb}
\usepackage[font=footnotesize,labelfont=bf]{caption}
\usepackage[numbers]{natbib}

\onehalfspacing
%\doublespacing
\restylefloat{table}

\begin{document}

\thispagestyle{empty}
\begin{center}

\huge

Utilizing Maximum Entropy Classification for Sentiment Analysis in Twitter Messages

\large
\vspace{2.0cm}
By

\vspace{1.0cm}
Douglas Anderson

0703557

dander01@uoguelph.ca

\vspace{1.5cm}
CIS*4900 - Undergraduate Research Project

August 7th, 2014 %TODO fix this

\vspace{1.5cm}

Supervisor:

Professor Fei Song

\vspace{1.5cm}

Second Reader:

Professor Xining Li

\end{center}

\newpage
\setcounter{page}{1}

\section{Introduction}
\label{section:intro}

Social media allows people to discuss topics and disseminate their opinions
with a near negligible cost. Social media's low barrier of entry allows
everyone to share their opinions as much as they please. The scale of textual
data from social media is enormous. In order to gain insight into the `overall'
opinion on particular topics, the process of determining sentiment must be
automated.

Performing sentiment analysis is becoming a very important field of study for
many businesses. If a company can determine what consumers think of their
products they can take actions such as improve their products or appease an
unsatisfied customer.

Sentiment analysis is simply a classification task that attempts to correctly
label fragments of text to appropriately summarizes the attitude of the text.
Natural Language Processing (NLP) provides a number of method for performing
sentiment analysis. Many of these methods, such as Naive Bayes and Maximum
Entropy, take a probabilistic approach to performing the task. Another commonly
used method of performing sentiment analysis is the uses of a support vector
machine (SVM).

\subsection{Specific Problem}
\label{ssection:specificproblem}

The focus of this undergraduate research project has been to perform sentiment
analysis in data from the microbloging website Twitter. All of the messages,
known as Tweets, are constrained in length to 140 characters. This limit forces
many users of Twitter to use abbreviations and contractions. This data presents
some interesting problems to performing good sentiment analysis due to the
short and informal nature of the text. Twitter makes it extremely easy to
publish a Tweet and has no way to edit a Tweet once published. This results in
more spelling mistakes and inconsistent grammar then other sources of text.
Tweets often also contain URLs to other websites. Tweets also contain a certain
amount of OOV (Out-Of-Vocabulary) words, such as Hashtags, a tagging system for
topics allowing Tweets in a similar vein of conversation to be found. Other OOV
words include mentions (e.g. `@BarackObama') which are a method to direct a
Tweet to one or more users, as well as `RT' which is an acronym for `retweet'
communicating that this particular Tweet is a reissuing of another users Tweet.
Another issue that is out of the scope of this project is that Twitter
currently supports 35+ languages, meaning that in order to determine the
sentiment most systems must first determine which language the Tweet is in.

\subsection{Task Description}
\label{ssection:taskdescription}

Organizers of the SemEval-2013 workshop created various sentiment analysis
tasks to be preformed. The task focused on for this project was task-2b:
Message polarity classification. The organizers used the Amazon service
``Mechanical Turk" to get many humans to annotate English language Tweets as
`positive', `negative' or `neutral'. In Tweets with mixed sentiments, the
prevailing sentiment was chosen. Participants were tasked with creating a
classifier to establish labels for Tweets not in the training dataset. The
various submissions of the participants were then evaluated by the average of
the F-positive and the F-negative (explained in depth in Section
\ref{ssection:performancemeasurement}). The submissions were allowed
categorized as `unconstrained' or `constrained' depending on if they did or did
not use supplemental data, respectively.

\section{Background}
\label{section:background}

According to `Opinion Mining and Sentiment Analysis' \cite{Pang2008}: ``The
year 2001 or so seems to mark the beginning of widespread awareness of the
research problems that sentiment analysis and opinion mining raise''. This
explosion in research has happened very recently, and as such the field is
moving very quickly. Much of the earlier work in the field involved data from
other contexts such as Movie reviews \cite{Pang2002}, and blog posts
\cite{Melville2009}. The challenges associated with classifying Twitter data
has only attracted researchers in the past few years \cite{Jianfeng2013}
\cite{Barbosa2010} \cite{Gokulakrishnan2012}.

Sentiment analysis is a very specific type of \textbf{text classification}, a
problem that is well summarized in chapter 6 of \textit{Mining Text Data} by
Aggarwal and Zhai \cite{Aggarwal2012} as:

\begin{quote}
    We have a set of training records $\mathcal{D} = \{X_{1} , . . .\ , X_{N}
    \}$, such that each record is labeled with a class value drawn from a set
    of k different discrete values indexed by $\{1 . . . k\}$. The training
    data is used in order to construct a classification model, which relates
    the features in the underlying record to one of the class labels.
\end{quote}

In the case of sentiment analysis, the class labels being applied to the
records denote the attitude or opinion in the text. The focus of this project
is determining sentiment at the document level, which assumes that the document
expresses a predominate sentiment. This is a somewhat reasonable assumption
given the fact that Tweets are limited in size, making it difficult to express
mixed sentiment. Sentiment analysis is very closely linked with opinion mining,
which is the practice of extracting sentiment on a particular topic in order to
gain insights into public opinion on the topic.

Much of the previous research make use of Naive Bayes, Maximum Entropy, and SVM
classifiers. The Naive Bayes classifier uses the occurrences of features in the
\textit{training set} to calculate the probability that an example in the
\textit{test set} belongs in a given class. This method has the benefit of
linear time training since there is no iterative process, but it makes the
assumption that all features are independent, which is not the case in natural
language. The Maximum Entropy approach is explained in detail in section
\ref{ssection:summaryofmaxent}. While Maximum Entropy and Naive Bayes are both
probabilistic approaches the to problem, Support Vector Machine (SVM)
classifiers take a different approach to the problem. ``SVM Classifiers attempt
partition the data space with the use of linear or non-linear delineations
between the different classifiers.''\cite{Aggarwal2012}.

In order to perform text classification of any kind one of the most important
aspects is deciding how to represent a document and how to select
representative features. A document is often represented as a
\textit{bag-of-words}, which is defined a set of strings with no apparent
order. The \textit{bag-of-words} method of representation was selected for this
project.

There are many established methods of selecting features such as document
frequency, which is simply the number of documents that a word occurs at least
once in. Document frequency has the added benefit of not requiring a class
labels to select features. While document frequency is the only method employed
for this project, many other methods exist, such as Gini Index, Information
Gain, and $\chi^{2}$-statistic \cite{Aggarwal2012}. Each of these more complex
methods rely on the class label in the \textit{training set} in order to
determine how well the feature discriminates between classes.

\section{Our Implementation}
\label{section:implementation}

\subsection{Summary of Maximum Entropy}
\label{ssection:summaryofmaxent}

The Maximum Entropy classification method was focused on due to the limited
duration of the project, however a Naive Bayes classifier was also implemented
to provide a point of comparison. This supervised machine learning method
calculates the probability that a given document $d$ belongs to the class $c$.
The Maximum Entropy approach is summarized below (for a more detailed
description, see: Nigam et al. \cite{Nigam1999}).

The training data is used to establish constraints in the following fashion:

\begin{equation}
    P(c | d) = \frac{1}{Z(d)} \mathrm{exp}(\sum\limits_{i} \lambda _{i,c} F_{i,c}(d,c) )
\end{equation}

where $Z(d)$ is a normalization function, $F_{i,c}$ is a feature function for
feature $f_{i}$ and class $c$, and $\lambda_{i}$ is a feature parameter.

In order to establish reasonable $\lambda_{i}$ for each feature the Improved
Iterative Scaling (IIS) is employed. Given a set of training data
$\mathcal{D}$, IIS trains a model $\Lambda$ by performing a hillclimbing
procedure with the function $l(\Lambda|\mathcal{D})$, where:

\begin{equation}
    l(\Lambda | \mathcal{D}) = \sum\limits_{d\in\mathcal{D}} \sum\limits_{i}
    \lambda_{i} f_{i}(d,c(d)) - \sum\limits_{d\in\mathcal{D}} \mathrm{log}
    \sum\limits_{c} \mathrm{exp} \sum\limits_{i} \lambda_{i} f_{i}(d,c)
\end{equation}

Starting with any initial vector of parameters $\Lambda$, at each iteration
we improve the parameters by setting $\Lambda = \Lambda + \Delta$.

\subsection{Preprocessing and Feature Selection}
\label{ssection:featureselection}

The classifier produced for this project is implemented in \textit{python} and
make extensive use of the \textit{nltk} (Natural Language Toolkit) library. As
well the implementation makes use of the \textit{flex} tool to create a lexer
for tokenization. The classifier does not make uses of any supplemental
datasets and therefore should be considered constrained within the context of
the task. The classifier adheres to the following procedure:

\begin{enumerate}

    \item \textbf{Tokenization} - The text is read into memory and separated into
        tokens. Each token represents an atom of text. Token types include
        word, number, user, hashtag, url, emoticon and punctuation.

    \item \textbf{Normalizing} - Each token is simplified to assist in
        classification by reducing the number of tokens.

        \begin{itemize}

            \item \textbf{Words} are coerced into lowercase

            \item \textbf{Numbers} are replaced with ``\#NUM''

            \item \textbf{User} are replaced with ``@USER''

            \item \textbf{Hashtags} are replaced with ``\#OCTOTHORPE''

            \item \textbf{URLs} are replaced with ``@URL''

            \item \textbf{Emoticon} are grouped into four different groups
                based on their intended meaning. Each group is then replaced
                with a representation. [e.g. `:)' $\rightarrow$ `EM\_HAPPY' and
                `;-p' $\rightarrow$ `EM\_WINK']

            \item most \textbf{Punctuation} is replaced with ``PUNCT'' however
                question marks, punctuation marks, and ellipsis are each
                replaced with their own representation.

        \end{itemize}

    \item \textbf{Feature Selection} - The number of tokens retained as
        features is further reduced.
        \begin{itemize}

            \item By \textbf{Removing Stopwords}, words that do not
                discriminate between classes are eliminated. Because of the
                limited size of the dataset only 28 stopwords are used. For a
                full list of stopwords see section \ref{ssection:stopwords}.

            \item Then \textbf{Uncommon words} are removed. Words that do not
                meet a certain document frequency threshold are eliminated.
                Many of these words are proper nouns that, if retained are
                likely to cause the classifier to overfit to the training set.
                A threshold of one was used throughout the testing process.

        \end{itemize}

    \item \textbf{Splitting} - The corpus of documents are random separated
        into three sets: the \textit{training set}, the \textit{validation set},
        and the \textit{testing set}. Respectively, each dataset is 60\%, 20\%,
        and 20\% of the corpus.

    \item \textbf{Training} - The classifier is trained using the
        \textit{training set}.  The classifier uses the \textit{validation set}
        to evaluate the training process and attempt to curtail overfitting.

    \item \textbf{Testing} - The performance of the dataset is evaluated
        against the \textit{testing set}.

\end{enumerate}

\subsection{Training Optimization}
\label{ssection:optimization}

The implementation created for this project used a \textit{validation set} during
training as the primary mechanism to avoid overfitting. While training, the
effectiveness of the classifier was evaluated after every iteration using the
accuracy or F-positive measure. During the training process the following
procedure was followed:

\begin{enumerate}

    \item The classifier was trained for 5 iterations to establish reasonable
        initial weights.

    \item Evaluate the classifier using the validation set. Like the
        \textit{testing set} that will evaluate the classifiers final
        performance, the \textit{validation set} shares no common examples with
        the \textit{training set} and will therefore give a reasonable
        indication of how the classifier will perform with unseen examples.

    \item Repeat the following until performance degrades for a specified
        number of iterations

    \begin{enumerate}

        \item Train the classifier for another iteration.

        \item Evaluate performance with the \textit{validation set}.

    \end{enumerate}

    \item Restore the $\Lambda$ value of the best performing iteration.

\end{enumerate}

\section{Experiments and Discussion}
\label{section:experiments}

\subsection{Dataset}
\label{ssection:dataset}

The dataset for the task consists of 6225 labelled Tweets. 36.66\% of the
corpus has `positive' label, 14.04\% has a `negative' label, 49.30\% has a
label that conveys neutral sentiment. This neutral label is one of `neutral',
`objective', or `objective-OR-neutral'. The following is an example of a
positive Tweet:

\begin{Verbatim}[fontsize=\footnotesize]
"positive", "Gas by my house hit $3.39!!!! I'm going to Chapel Hill on Sat. :)"
\end{Verbatim}

\subsection{Evaluation Measures}
\label{ssection:evaluation}

After the SemEval-2013 workshop the organizers released a paper discussing the
proceedings and the results of the task \cite{Nakov2013}. The paper establishes
baseline in terms of $F$. $F$ can be calculated as:

\begin{equation}
    F = \frac{2 \frac{P_{pos}R_{pos}}{P_{pos} + R_{pos}} +
    2 \frac{P_{neg}R_{neg}}{P_{neg} + R_{neg}}}{2}
\end{equation}

Which can be simplified to:

\begin{equation}
    F = \frac{P_{pos}R_{pos}}{P_{pos} + R_{pos}} + \frac{P_{neg}R_{neg}}{P_{neg} + R_{neg}}
\end{equation}

The \textit{Precision} measure for the positive label is $P_{pos} =
\frac{\mathrm{\# of\ true\ positive}}{\mathrm{\# of\ true\ positive} + \mathrm{\#
of\ false\ positive} }$. The \textit{Recall} measure for the positive label is
defined as $R_{pos} = \frac{\mathrm{\# of\ true\ positive}}{\mathrm{\# of\ true\
positive} + \mathrm{\# of\ false\ negative} }$. $P_{neg}$ and $R_{neg}$ can be
calculated in a similar fashion.

Accuracy is used as a secondary performance measure. Accuracy, henceforth
referred to as $Acc$, can be calculate with the following formula:

\begin{equation}
    Acc = \frac{\mathrm{\# of\ true\ positive} + \mathrm{\# of\ true\ negative}}{N}
\end{equation}

Where $N$ is equal to the total number of documents in the \textit{test set}.
While more intuitive, it is not used as the primary evaluation measure due to
it's tendency to be biased by uneven numbers of examples of particular labels
in the dataset.

\subsection{Improving Performance Measurement}
\label{ssection:performancemeasurement}

    Testing the performance of the system with a single run can produce skewed
    results since whether `easy' Tweets end up in \textit{training set} or the
    \textit{test set} will affect performance. To combat this the following
    \textbf{exhaustive cross-validation} method is used:

        \begin{enumerate}

        \item \textbf{Partitioning} - The corpus of documents are shuffled and
            separated into 5 or 10 sections.

        \item \textbf{Folding} - The training and testing process are run
            multiple times with sections used for various roles. The roles are
            permuted so that the classifier is trained and tested with the
            sections in all possible configurations. In each fold 60\% of the
            partitions are designated as part of the \textit{training set},
            20\% as the \textit{validation set}, and 20\% as the \textit{test set}.
            Since the Naive Bayes classifier does not use a \textit{validation set},
            40\% of the partitions are designated as part of the
            \textit{test set}

        \begin{enumerate}

            \item \textbf{Training} - The classifier is trained with the
                partitions designated as part of the \textit{training set} for
                the fold. The Maximum Entropy classifier also uses the
                \textit{validation set} to determine when to stop the training
                process.

            \item \textbf{Testing} - The performance of the classifier is
                evaluated using the \textit{test set} and the results are recorded.

        \end{enumerate}

        \item \textbf{Aggregating} - The results from all folds are averaged.

        \end{enumerate}

\subsection{Baseline}
\label{ssection:baseline}

The baseline for this project is established by running the Maximum Entropy
classifier without any stopword removal, rare word removal (words with a
document frequency $<$ 1), Or feature normalization. The F-score that is
achieved is \textbf{50.72}.

\subsection{Experimental Results}
\label{ssection:results}

The following experiments examine the results of the Maximum Entropy classifier
and the Naive Bayes classifier with various feature selection methods turned on
or off. The `Baseline' experiment refers to no feature selection. The `Only
Stopword Removal' experiment refers the only removing stopwords as feature
selection. The `Only Rare Word Removal' experiment refers to only removing
words with a document frequency of 1. The `Only Normalization' experiment
refers to only applying feature normalization mechanisms. The `All Feature
Selection' experiment refers to testing the classifier with all of the previous
feature selection methods turned on.

\subsubsection{Number of Features}
\label{ssection:numfeatures}

The number of features retained after feature selection varies from Tweet to Tweet.
To summarize the number of features retained after different processes, Table
\ref{table:numfeatures} presents the mean number of features per Tweet for
positive, neutral, negative examples as well as an overall average.

\begin{table}[H]
    \begin{center}
    \begin{tabular}{|r||c|c|c|c|}
        \hline
        Description            & Positive & Neutral & Negative & Overall \\
        \hline
        Baseline               & 20.65    & 20.45   & 20.96    & 20.58 \\
        Only Stopword Removal  & 17.13    & 16.86   & 17.41    & 17.04 \\
        Only Rare Word Removal & 18.43    & 17.87   & 18.85    & 18.21 \\
        Only Normalization     & 19.65    & 19.16   & 20.06    & 19.46 \\
        All Feature Selections & 14.85    & 14.06   & 15.10    & 14.49 \\
        \hline
    \end{tabular}
    \end{center}
    \caption{`Positive', `Neutral', `Negative', and `Overall' refer to the
    average number of features per Tweet in each experiment.}
    \label{table:numfeatures}
\end{table}

Interestingly `negative' Tweets contain more features then `positive' Tweets
which, in turn, contain more features than `neutral' tweets. Normalization does
not appear to significantly reduce the number of features per Tweet. This makes
sense since the number of features in the \textit{bag-of-words} would only be
reduced if two or more of the features are normalized to the same thing (e.g.
A Tweet that contained `2' and `3' before normalization would only contain the
feature `\#NUM' after normalization).

\subsubsection{Maximum Entropy Classifier}

\begin{table}[H]
    \begin{center}
    \begin{tabular}{|r||c|c|c|c|c|}
        \hline
        Description    & $\mu F$ & $\sigma F$ & $\delta\ \mu F$ & $\mu Acc$ & $\sigma Acc$ \\
        \hline
        Baseline               & 48.37   & 2.15 &     - & \textbf{63.89} & 1.13 \\
        Only Stopword Removal  & 48.27   & 1.83 & -0.10 & 62.07 & 1.69 \\
        Only Rare Word Removal & 49.02   & 1.96 &  0.65 & 62.47 & 1.91 \\
        Only Normalization     & 49.55   & 2.10 &  1.18 & 63.57 & 1.75 \\
        All Feature Selections & \textbf{50.96}  & 1.93  &  2.59 & 63.82 & 0.91 \\
        \hline
    \end{tabular}
    \end{center}
    \caption{Performance of the Maximum Entropy classifier using exhaustive
    cross-validation with 5 partitions}
    \label{table:maxent-results}
\end{table}

As Table \ref{table:maxent-results} shows, the `All Feature Selections'
experiment provides the best results over the baseline. The `Only Stopword
Removal' experiment actually provides slightly worse results then the baseline
indicating that in context of Tweets with so few features in each example every
feature counts. The `Only Rare Words Removal ' experiment does not provide very
significant gains when used alone.  This is potentially due to the fact that
without normalization turned, features such as `just' are `Just' are determined
to be different and may be removed if each only occur once.

\begin{figure}[H]
    \begin{center}
    \includegraphics[scale=0.75]{figures/maxent_boxplot.png}
    \caption{This boxplot shows the F-score of each of twenty folds in all five
    Maximum Entropy experiments}
    \label{figure:maxent}
    \end{center}
\end{figure}

\subsubsection{Naive Bayes Classifier}

\begin{table}[H]
    \begin{center}
    \begin{tabular}{|r||c|c|c|c|c|}
        \hline
        Description    & $\mu F$ & $\sigma F$ & $\delta\ \mu F$ & $\mu Acc$ & $\sigma Acc$ \\
        \hline
        Baseline               & 48.11  & 0.74 & -     & 53.13 & 1.48 \\
        Only Stopword Removal  & 47.29  & 0.76 & -0.82 & 52.71 & 1.16 \\
        Only Rare Word Removal & 48.34  & 1.11 &  0.23 & 53.92 & 1.32 \\
        Only Normalization     & \textbf{49.44} & 1.00 & 1.33 & \textbf{55.92} & 0.99 \\
        All Feature Selections & 49.28  & 0.81 &  1.17 & 54.91 & 1.05 \\
        \hline
    \end{tabular}
    \end{center}
    \caption{Performance of the Naive Bayes classifier using exhaustive
    cross-validation with 5 partitions}
    \label{table:bayes-results}
\end{table}

\begin{figure}[H]
    \begin{center}
    \includegraphics[scale=0.75]{figures/bayes_boxplot.png}
    \caption{This boxplot shows the F-score of each of ten folds in all five
    Naive Bayes experiments}
    \label{figure:bayes}
    \end{center}
\end{figure}

As Table \ref{table:bayes-results} and Figure \ref{figure:bayes} indicates both
removing stopwords and removing rare words appear to negatively affect
performance of the naive bayes classifier.

\subsection{Most Informative Features}
\label{ssection:informativefeatures}

The implementation created for this project has the ability to show which
features are the most discriminatory. The following is a list of the top 30
most informative features from one run of the Maximum Entropy classifier (note
that some of the weights are negative):

\begin{Verbatim}[fontsize=\footnotesize]
  -3.176 excited==True and label is 'neutral'
   2.328 lied==True and label is 'negative'
   2.279 availability==True and label is 'negative'
  -2.258 excited==True and label is 'negative'
  -2.180 EM_HAPPY==True and label is 'negative'
  -2.171 happy==True and label is 'neutral'
  -2.098 birthday==True and label is 'negative'
   2.016 shitty==True and label is 'negative'
  -1.836 8th==True and label is 'positive'
  -1.801 international==True and label is 'positive'
   1.789 embarrassing==True and label is 'negative'
  -1.762 went==True and label is 'negative'
   1.702 releases==True and label is 'negative'
  -1.672 love==True and label is 'negative'
   1.650 lack==True and label is 'negative'
   1.650 oneil==True and label is 'neutral'
  -1.638 fun==True and label is 'neutral'
   1.599 replay==True and label is 'negative'
  -1.585 great==True and label is 'neutral'
   1.577 asses==True and label is 'positive'
   1.570 garlic==True and label is 'negative'
  -1.564 pass==True and label is 'negative'
   1.560 den==True and label is 'negative'
   1.560 accepting==True and label is 'negative'
  -1.557 sure==True and label is 'negative'
   1.551 insensitive==True and label is 'negative'
   1.547 calvin==True and label is 'negative'
   1.532 jailed==True and label is 'negative'
   1.520 lookin==True and label is 'neutral'
   1.515 2c==True and label is 'negative'
\end{Verbatim}

Some of the features listed above make perfect sense, such as `excited' not
being associated with the neutral class and `embarrassing' being associated
with the negative class. However some of the most discriminating features
appear in the dataset infrequently, such as `calvin' and `oneil'.

\subsection{Comparison to Other Systems}
\label{ssection:comparison}

Table \ref{table:comparison} shows the performance of the classifier produced
for this project compared to results of the workshop participants. The full
table (with out this project's results) can be found in Nakov et al. as Table 9
\cite{Nakov2013}.

\begin{table}[H]
    \begin{center}
        \small
    \begin{tabular}{|r|l|}
        \hline
        Team            & F \\
        \hline
        NRC-Canada      & 69.02 \\
        GU-MLT-LT       & 65.27 \\
        teragram        & 64.86 \\
        BOUNCE*         & 63.53 \\
        KLUE*           & 63.06 \\
        AMI\&ERIC       & 62.55 \\
        FBM             & 61.17 \\
        AVAYA           & 60.84 \\
        SAIL*           & 60.14 \\
        UT-DB           & 59.87 \\
        FBK-irst        & 59.76 \\
        nlp.cs.aueb.gr  & 58.91 \\
        UNITOR          & 58.27 \\
        LVIC-LIMSI      & 57.14 \\
        Unigon          & 56.96 \\
        NILC\_USP       & 56.31 \\
        DataMining      & 55.52 \\
        ECNUCS          & 55.05 \\
        nlp.cs.aueb.gr  & 54.73 \\
        ASVUniOfLeipzig & 54.56 \\
        SZTE-NLP        & 54.33 \\
        CodeX           & 53.89 \\
        Oasis           & 53.84 \\
        NTNU            & 53.23 \\
        UoM             & 51.81 \\
        \textbf{MaxEnt} & \textbf{50.96} \\
        SSA-UO          & 50.17 \\
        SenselyticTeam  & 50.10 \\
        \textbf{Naive Bayes} & \textbf{49.44} \\
        \textit{9 more teams}&  \textless\ 49 \\
        \hline
    \end{tabular}
    \end{center}
    \caption{Comparison of constrained classifiers submitted to the SemEval-2013
        workshop. Sorted by F-score. * denotes other Maximum Entropy classifiers}
    \label{table:comparison}
\end{table}

\section{Conclusions and Future Work}
\label{section:conclusionsandfuturework}

\subsection{Conclusions}
\label{ssection:conclusions}

As shown in Table \ref{table:comparison}, there is a lot of room for improvement
before this system is a completive solution. However, only simple methods have
been employed including: stopword removal of only 28 words, words with a
document frequency lower than one removed, and normalization of words, emoticons,
and OOV words. These simple preprocessing and feature selection methods in
combination with a Maximum Entropy classifier have demonstrated reasonable
results.

\subsection{Future Work}
\label{ssection:futurework}

There is room for a number of improvement in the implementation of the system.
The following sections are a number of improvements as future work. Many of the
ideas are from the other submissions to the SemEval-2013 workshop.

\subsubsection{Hashtags}
\label{sssection:hashtags}

Hashtags are a way that Twitter users tag a Tweet as part of a particular
conversation. Hashtags refer to proper nouns such as events, places, or people.
Hashtags can also denote modifiers (such as `\#sarcasm') to the sentiment of the
Tweet, or even raw sentiment (e.g. `\#yay').

While it is likely infeasible to retain Hashtags about proper nouns,
classification performance could be improved by including modifiers and
Hashtags with raw sentiment. The following Tweet (not from the dataset) is a
great example of a Tweet that Hashtags could help improve classification
accuracy.

\begin{verbatim}
    Well I have an ear infection #good #sarcasm
\end{verbatim}

The words in the previous Tweet carry no inherent sentiment, however the
message is clearly negative. While a simple approach could be to strip the
octothorpe from the front of the Hashtag (e.g. `\#good' $\rightarrow$ `good'),
the semantic meaning of the two are different. Hashtags often have message
level meaning while simple words have local context withing the sentence. Since
the dataset created for the SemEval-2013 workshop mostly contained examples of
Hashtags used as proper nouns, more annotated Tweets would be needed for
training and testing.

Hashtags sometimes use CamelCase to create multi-word tags (e.g.
`\#SorryNotSorry'). It could prove worthwhile to attempt the decompose
CamelCase Hashtags into its component words during feature selection.

The top solution from the National Research Council of Canada made use of a
Hashtag lexicon that they developed between April of 2012 and December 2012
\cite{Mohammad2013}. The final \textit{NRC Hashtag Sentiment Lexicon} has more
than 350,00 entries and is available at Saif Mohammad's website
\footnote{http://www.saifmohammad.com/WebDocs/NRC-Hashtag-Sentiment-Lexicon-v0.1.zip}.

\subsubsection{Users}
\label{sssection:users}

Nearly all Twitter users have published more than one Tweet. A more advanced
classifier could establish a particular users propensity to publishing a
prevailing sentiment in all of their Tweets.

As well, some Twitter users may be frequently be referred to with a particular
sentiment. For a hypothetical example, Tweets addressed to Emma Watson
(`@EmWatson') are more likely to have a positive sentiment, while Tweets to
Barack Obama (`@BarackObama') may contain extremely mixed sentiment.

A challenge that this method could introduce is the introduction of a temporal
element since people's outlooks, and therefore sentiment's in Tweets, will
change over time. As well as public perception of a individual changes, the
prevailing sentiment may change as well.

\subsubsection{Negation}
\label{sssection:negation}

One problem with the current implementation is that it lack support for
negation. In it's current form the classifier would likely misunderstand the
sequence ``not perfect'' since `not' is a vaguely negative word and `perfect'
is a very positive word. It would likely be classified as positive when in fact
the sentiment is quite clearly negative. A common approach to this problem is
to add a suffix (such as "\_NEG") to word that appear between a negation word
and a section delimiting punctuation mark (such as `,', `.', `:', `;', `!',
`?'). By separating negated features from their non-negated instances, features
can do a better job of distinguishing classes.

\subsubsection{N-gram Features}
\label{sssection:ngram}

One way that many of the other \textit{bag-of-words} solutions capture word order is by
creating features consisting of sequences of words called bigrams. Adding
bigram features adds a large number of features which can add complexity to
training. This concept can also be extended to sequences of length n, called
ngrams.

The added complexity associated with ngrams did not deter the National Research
Council of Canada from using ngrams of length 1, 2, 3, and 4 as well as
`non-contiguous' ngrams which are described as `ngrams with one token replaced
by *' \cite{Mohammad2013}.

\subsubsection{Employing Sentiment Lexicon}
\label{sssection:sentimentlexicon}

Most of the more complex solutions submitted to the SemEval-2013 workshop made
uses of sentiment lexicons that capture a term's polarity. These lexicons, such
as SentiWordNet \footnote{http://sentiwordnet.isti.cnr.it/}, express the
positive, neutral, and negative sentiment of each homonym. An example of this
from SentiWordNet, is `good' meaning `morally admirable' having an entirely
positive sentiment versus `good' meaning `having the normally expected amount'
having an entirely neutral sentiment
\footnote{http://sentiwordnet.isti.cnr.it/search.php?q=good}.

\subsubsection{Support Vector Machine}
\label{sssection:svm}

Many of the top solutions submitted to the workshop, such as NRC-Canada made
use of a Support Vector Machine for classification \cite{Mohammad2013}.  This
indicates that when used effectively a SVM solution can out-perform a Maximum
Entropy solution. The KLUE team, on the other hand, found that their Maximum
Entropy solution outperform their linear SVM solution \cite{Proisl2013}.

\section{References}
\label{section:referances}

\nocite{*}
\bibliographystyle{ieeetr}
\bibliography{paper}

\section{Appendices}
\label{section:appendices}

\subsection{Running the Implementation}
\label{ssection:runningtheimplementation}

To acquire your own copy of the implementation discussed above. The following
instructions are written for Ubuntu 14.04 GNU/Linux, however it should be able
to run on any Unix-like system.

\begin{enumerate}

    \item \textbf{Download Source} - The source code is hosted on github.com
        and can be viewed there
        \footnote{https://github.com/hockeybuggy/twitter-sentiment/tree/dist}.
        To download a zip file and open it:

\begin{Verbatim}[fontsize=\footnotesize]
wget https://github.com/hockeybuggy/twitter-sentiment/archive/dist.zip
unzip dist.zip
cd twitter-sentiment-dist
\end{Verbatim}

    \item \textbf{Install Prerequisites} - If \textit{python 2.7},
        \textit{pip}, and \textit{flex} are not installed, they can be
        installed easily via a package manger:

\begin{Verbatim}[fontsize=\footnotesize]
sudo apt-get install python2.7 pip flex
\end{Verbatim}

Then various required python packages can be installed with:

\begin{Verbatim}[fontsize=\footnotesize]
sudo pip install numpy nltk
\end{Verbatim}

    \item \textbf{Compile Tokenizer} - The tokenizer is written in C for
        performance reasons and can be compiled with:
\begin{Verbatim}[fontsize=\footnotesize]
make
\end{Verbatim}

    \item \textbf{Run the Program} - The classifier can be executed in a number
        of ways. There are two python programs that are executable:
        `conductor.py' and `crossval.py'. These two programs run the classifier
        in a simple fashion or with cross validation. There are a large number
        of command line arguments that can be viewed with:

\begin{Verbatim}[fontsize=\footnotesize]
python conductor -h
\end{Verbatim}

Since the command line arguments can be cumbersome many of the experiments can
be run via the make file:

\begin{Verbatim}[fontsize=\footnotesize]
make tiny            # Quick running with only 100 examples
make crossfolds-m000 # The MaxEnt baseline with cross-validation
make crossfolds-m111 # MaxEnt with cross-validation & feature selection
make crossfolds-b000 # The Naive Bayes baseline with cross-validation
make crossfolds-b111 # Naive Bayes with cross-val & feature selection
make crossfolds      # Run all of the cross-validation experiments
\end{Verbatim}

\end{enumerate}

\subsection{Stopword list}
\label{ssection:stopwords}

The list of stopwords was acquired online\footnote{www.ranks.nl/stopwords} and is
as follows:

\begin{Verbatim}[fontsize=\footnotesize]
         a                   of
         about               on
         an                  or
         are                 that
         as                  the
         at                  this
         be                  to
         by                  was
         com                 what
         for                 when
         from                where
         how                 who
         in                  will
         is                  with
         it
\end{Verbatim}

\end{document}

max_stars_repo_name: hockeybuggy/twitter-sentiment

max_issues_repo_name: hockeybuggy/twitter-sentiment

max_forks_repo_name: hockeybuggy/twitter-sentiment


text:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% KOMA-Script Presentation
% LaTeX Template
% Version 1.0 (3/3/13)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% Original Authors:
% Marius Hofert (marius.hofert@math.ethz.ch)
% Markus Kohm (komascript@gmx.info)
% Described in the PracTeX Journal, 2010, No. 2
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%saPACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass[
paper=128mm:96mm, % The same paper size as used in the beamer class
fontsize=11pt, % Font size
pagesize, % Write page size to dvi or pdf
parskip=half-, % Paragraphs separated by half a line
]{scrartcl} % KOMA script (article)

\linespread{1.12} % Increase line spacing for readability

%------------------------------------------------
% Colors
\usepackage{xcolor} % Required for custom colors
% Define a few colors for making text stand out within the presentation
\definecolor{mygreen}{RGB}{44,85,17}
\definecolor{myblue}{RGB}{34,31,217}
\definecolor{mybrown}{RGB}{194,164,113}
\definecolor{myred}{RGB}{255,66,56}
% Use these colors within the presentation by enclosing text in the commands below
\newcommand*{\mygreen}[1]{\textcolor{mygreen}{#1}}
\newcommand*{\myblue}[1]{\textcolor{myblue}{#1}}
\newcommand*{\mybrown}[1]{\textcolor{mybrown}{#1}}
\newcommand*{\myred}[1]{\textcolor{myred}{#1}}
%------------------------------------------------

%------------------------------------------------
% Margins
\usepackage[ % Page margins settings
includeheadfoot,
top=3.5mm,
bottom=3.5mm,
left=5.5mm,
right=5.5mm,
headsep=6.5mm,
footskip=8.5mm
]{geometry}
%------------------------------------------------

%------------------------------------------------
% Fonts
\usepackage[T1]{fontenc} % For correct hyphenation and T1 encoding
\usepackage{lmodern} % Default font: latin modern font
%\usepackage{fourier} % Alternative font: utopia
%\usepackage{charter} % Alternative font: low-resolution roman font
\renewcommand{\familydefault}{\sfdefault} % Sans serif - this may need to be commented to see the alternative fonts
%------------------------------------------------

%------------------------------------------------
% Various required packages
\usepackage{amsthm} % Required for theorem environments
\usepackage{bm} % Required for bold math symbols (used in the footer of the slides)
\usepackage{graphicx} % Required for including images in figures
\usepackage{tikz} % Required for colored boxes
\usepackage{booktabs} % Required for horizontal rules in tables
\usepackage{multicol} % Required for creating multiple columns in slides
\usepackage{lastpage} % For printing the total number of pages at the bottom of each slide
\usepackage[english]{babel} % Document language - required for customizing section titles
\usepackage{microtype} % Better typography
\usepackage{tocstyle} % Required for customizing the table of contents
\usepackage{minted} % Code listings
\newmintedfile[coffee]{coffee}{mathescape, linenos, numbersep=1pt, fontfamily=tt, fontsize=\tiny, frame=lines, framesep=3mm}
\newmintedfile[ruby]{ruby}{mathescape, linenos, numbersep=1pt, fontfamily=tt, fontsize=\tiny, frame=lines, framesep=3mm}
\newmintedfile[python]{python}{mathescape, linenos, numbersep=1pt, fontfamily=tt, fontsize=\tiny, frame=lines, framesep=3mm}
\newmintedfile[text]{text}{mathescape, numbersep=1pt, fontfamily=tt, fontsize=\tiny, frame=lines, framesep=3mm}
\newminted{ruby}{mathescape, gobble=2, linenos, numbersep=1pt, fontfamily=tt, fontsize=\tiny, frame=lines, framesep=3mm}
%------------------------------------------------

%------------------------------------------------
% Slide layout configuration
\usepackage{scrpage2} % Required for customization of the header and footer
\pagestyle{scrheadings} % Activates the pagestyle from scrpage2 for custom headers and footers
\clearscrheadfoot % Remove the default header and footer
\setkomafont{pageheadfoot}{\normalfont\color{black}\sffamily} % Font settings for the header and footer

% Sets vertical centering of slide contents with increased space between paragraphs/lists
\makeatletter
\renewcommand*{\@textbottom}{\vskip \z@ \@plus 1fil}
\newcommand*{\@texttop}{\vskip \z@ \@plus .5fil}
\addtolength{\parskip}{\z@\@plus .25fil}
\makeatother

% Remove page numbers and the dots leading to them from the outline slide
\makeatletter
\newtocstyle[noonewithdot]{nodotnopagenumber}{\settocfeature{pagenumberbox}{\@gobble}}
\makeatother
\usetocstyle{nodotnopagenumber}

\AtBeginDocument{\renewcaptionname{english}{\contentsname}{\Large Outline}} % Change the name of the table of contents
%------------------------------------------------

%------------------------------------------------
% Header configuration - if you don't want a header remove this block
\ihead{
\hspace{-2mm}
\begin{tikzpicture}[remember picture,overlay]
\node [xshift=\paperwidth/2,yshift=-\headheight] (mybar) at (current page.north west)[rectangle,fill,inner sep=0pt,minimum width=\paperwidth,minimum height=2\headheight,top color=mygreen!64,bottom color=mygreen]{}; % Colored bar
\node[below of=mybar,yshift=3.3mm,rectangle,shade,inner sep=0pt,minimum width=128mm,minimum height =1.5mm,top color=black!50,bottom color=white]{}; % Shadow under the colored bar
shadow
\end{tikzpicture}
\color{white}\runninghead} % Header text defined by the \runninghead command below and colored white for contrast
%------------------------------------------------

%------------------------------------------------
% Footer configuration
% \newlength{\footheight}
\setlength{\footheight}{8mm} % Height of the footer
\addtokomafont{pagefoot}{\footnotesize} % Small font size for the footnote

\ifoot{% Left side
\hspace{-2mm}
\begin{tikzpicture}[remember picture,overlay]
\node [xshift=\paperwidth/2,yshift=\footheight] at (current page.south west)[rectangle,fill,inner sep=0pt,minimum width=\paperwidth,minimum height=3pt,top color=mygreen,bottom color=mygreen]{}; % Green bar
\end{tikzpicture}
\myauthor\ \raisebox{0.2mm}{$\bm{\vert}$}\ \myuni % Left side text
}

\ofoot[\pagemark/\pageref{LastPage}\hspace{-2mm}]{\pagemark/\pageref{LastPage}\hspace{-2mm}} % Right side
%------------------------------------------------

%------------------------------------------------
% Section spacing - deeper section titles are given less space due to lesser importance
\usepackage{titlesec} % Required for customizing section spacing
\titlespacing{\section}{0mm}{0mm}{0mm} % Lengths are: left, before, after
\titlespacing{\subsection}{0mm}{0mm}{-1mm} % Lengths are: left, before, after
\titlespacing{\subsubsection}{0mm}{0mm}{-2mm} % Lengths are: left, before, after
\setcounter{secnumdepth}{0} % How deep sections are numbered, set to no numbering by default - change to 1 for numbering sections, 2 for numbering sections and subsections, etc
%------------------------------------------------

%------------------------------------------------
% Theorem style
\newtheoremstyle{mythmstyle} % Defines a new theorem style used in this template
{0.5em} % Space above
{0.5em} % Space below
{} % Body font
{} % Indent amount
{\sffamily\bfseries} % Head font
{} % Punctuation after head
{\newline} % Space after head
{\thmname{#1}\ \thmnote{(#3)}} % Head spec

\theoremstyle{mythmstyle} % Change the default style of the theorem to the one defined above
\newtheorem{theorem}{Theorem}[section] % Label for theorems
\newtheorem{remark}[theorem]{Remark} % Label for remarks
\newtheorem{algorithm}[theorem]{Algorithm} % Label for algorithms
\makeatletter % Correct qed adjustment
%------------------------------------------------

%------------------------------------------------
% The code for the box which can be used to highlight an element of a slide (such as a theorem)
\newcommand*{\mybox}[2]{ % The box takes two arguments: width and content
\par\noindent
\begin{tikzpicture}[mynodestyle/.style={rectangle,draw=mygreen,thick,inner sep=2mm,text justified,top color=white,bottom color=white,above}]\node[mynodestyle,at={(0.5*#1+2mm+0.4pt,0)}]{ % Box formatting
\begin{minipage}[t]{#1}
#2
\end{minipage}
};
\end{tikzpicture}
\par\vspace{-1.3em}}
%------------------------------------------------

%----------------------------------------------------------------------------------------
%3emPRESENTATION INFORMATION
%----------------------------------------------------------------------------------------

\newcommand*{\mytitle}{ChatOps: Operations meet chat} % Title
\newcommand*{\runninghead}{ChatOps: Operations meet chat} % Running head displayed on almost all slides
\newcommand*{\myauthor}{Jose Luis Salas} % Presenters name(s)
\newcommand*{\mydate}{\today} % Presentation date
\newcommand*{\myuni}{Valencia DevOps -- April 2015} % University or department

%----------------------------------------------------------------------------------------

\begin{document}

%----------------------------------------------------------------------------------------
%documentTITLE SLIDE
%----------------------------------------------------------------------------------------

% Title slide - you may have to tweak a few of the numbers if you wish to make changes to the layout
\thispagestyle{empty} % No slide header and footer
\begin{tikzpicture}[remember picture,overlay] % Background box
\node [xshift=\paperwidth/2,yshift=\paperheight/2] at (current page.south west)[rectangle,fill,inner sep=0pt,minimum width=\paperwidth,minimum height=\paperheight/3,top color=mygreen,bottom color=mygreen]{}; % Change the height of the box, its colors and position on the page here
\end{tikzpicture}
% Text within the box
\begin{flushright}
\vspace{0.6cm}
\color{white}\sffamily
{\bfseries\Large\mytitle\par} % Title
\vspace{0.5cm}
\normalsize
\myauthor\par % Author name
\mydate\par % Date
\vfill
\end{flushright}

\clearpage

%----------------------------------------------------------------------------------------
%clearpageTABLE OF CONTENTS
%----------------------------------------------------------------------------------------

\thispagestyle{empty} % No slide header and footer

\small\tableofcontents % Change the font size and print the table of contents - it may be useful to shrink the font size further if the presentation is full of sections
% To exclude sections/subsections from the table of contents, put an asterisk after \(sub)section like so: \section*{Section Name}

\clearpage

%----------------------------------------------------------------------------------------
%clearpagePRESENTATION SLIDES
%----------------------------------------------------------------------------------------

\section{whoami}

I'm Jose Luis Salas

Work as SRE at peerTransfer, programming in Ruby and Shell mostly

Open source contributor: josacar/chef-babushka, josacar/lita-campfire, josacar/lita-jobs, fog/fog, sethvargo/chefspec, rumblelabs/asset\_sync, aetrion/chef-dnsimple, jesseadams/sphinx-cookbook, opscode-cookbooks/client-rekey, librato/papertrail-cookbook, sstephenson/ruby-build, hw-cookbooks/route53, josephruscio/twke, geokit/geokit, collectiveidea/tinder, berkshelf/berkshelf, librato/collectd-librato-cookbook, chef/ohai, opscode-cookbooks/rsyslog, peter-murach/github

Twitter: @josacar

GitHub: josacar

\clearpage

%------------------------------------------------

\section{What is ChatOps}

Doing Operations in a Chat tool

\subsection{What does ChatOps provide?}

\begin{enumerate}
\item Everyone sees all of that happen since their first day
\item Place tools in the middle of the conversation
\item Teaching by doing by making things visible
\item Communicate by doing
\end{enumerate}

\clearpage

%------------------------------------------------

\subsection{Questions I haven't asked since ChatOps}
\begin{itemize}
\item How is the deployment doing?
\item Should I deploy or are you deploying that?
\item Can I deploy to this environment?
\item Is the smoke suite green?
\item Is anyone checking the sensu alert?
\item Has CI passed in that branch?
\item Is the system load ok?
\item Is anyone using this environment?
\end{itemize}

\clearpage

%------------------------------------------------

\section{ChatOps in practice}
\subsection{What do you need?}

\begin{itemize}
  \item A chat client: IRC, HipChat, Slack, Flowdock, and Campfire
  \item Chat bots ( all FLOSS ):
  \begin{itemize}
    \item Hubot
    \item Lita
    \item Err
  \end{itemize}
\end{itemize}
\clearpage

%------------------------------------------------

\subsection{Hubot}
\begin{itemize}
\item Written in CoffeeScript and JavaScript
\item Runs on top of NodeJS
\item Created and used by GitHub
\item Supports multiple chats: Campfire, Slack, HipChat
\item Storage ( brain ) : Redis, PostgreSQL, MySQL
\item Supports chat and HTTP routes
\end{itemize}
\clearpage

%------------------------------------------------

pugme.coffee
\coffee{pugme.coffee}
\clearpage

%------------------------------------------------

\subsection{Lita}
\begin{itemize}
\item Written in Ruby ( requires Ruby >= 2.0 )
\item Runs on top of MRI / JRuby / Rubinius
\item Created by JimmyCuadra
\item Supports multiple chats: Campfire, Slack, HipChat, IRC
\item Storage: Redis
\item Supports chat and HTTP routes
\item Testable with RSpec
\item Extensible using plugins through Bundler
\end{itemize}
\clearpage

%------------------------------------------------

\subsubsection{\$ lita new bot}
\ruby{lita_config.rb}
\clearpage

%------------------------------------------------

\ruby{Gemfile}
\clearpage

%------------------------------------------------

\subsubsection{\$ lita handler myhandler }
\text{myhandler.txt}
\clearpage

%------------------------------------------------

lib/lita/handlers/myhandler.rb
\ruby{myhandler.rb}
\clearpage

%------------------------------------------------

spec/lita/handlers/myhandler\_spec.rb
\ruby{myhandler_spec.rb}
\clearpage

%------------------------------------------------

\subsubsection{Handler usage}
\begin{rubycode}
  route(/^echo\s+(.+)/, :echo, command: true, restrict_to: [:testers, :committers], help: {
    'echo TEXT' => 'Replies back with TEXT.'
  })
\end{rubycode}
\begin{rubycode}
  http.get "/builds/:id", :build_info

  def build_info(request, response)
    id = request.env["router.params"][:id]
    build = MyBuildSystem.find(id)
    response.headers["Content-Type"] = "application/json"
    response.write(MultiJson.dump(build))
  end
\end{rubycode}
\begin{rubycode}
  on :connected, :greet
  def greet(payload)
    target = Source.new(room: payload[:room])
    robot.send_message(target, "Hello #{payload[:room]}!")
  end
\end{rubycode}
\begin{rubycode}
  module Lita
    module Handlers
      class HandlerWithConfig < Handler
        config :api_key
        route(/call api/, command: true) do |response|
          response.reply(ThirdPartyAPI.new(config.api_key).call)
        end
      end
      Lita.register_handler(HandlerWithConfig)
    end
  end
\end{rubycode}
\clearpage

%------------------------------------------------

pugme.rb
\ruby{pugme.rb}
\clearpage

%------------------------------------------------

\subsection{Err}
\begin{itemize}
\item Written in Python
\item Runs on top of Python 2.7 and 3.2+
\item Created by Guillaume Binet
\item Supports multiple chats: Campfire, HipChat, IRC
\item Storage ( brain ) : File
\item Supports chat and HTTP routes
\end{itemize}
\clearpage

%------------------------------------------------

hello.py
\python{hello.py}
\clearpage

%------------------------------------------------

\section{Examples}
\subsection{Nagios}
\begin{itemize}
  \item bot nagios ack database01/mysqld
  \item bot nagios check database01/mysqld
  \item bot nagios status database01/mysqld
  \item bot nagios downtime database01/mysqld
  \item bot nagios mute database01/mysqld
  \item bot nagios unmute database01/mysqld
\end{itemize}
\clearpage

%------------------------------------------------

\subsection{Deploying}
\begin{itemize}
  \item bot deploy myapp to prod/front01
  \item bot log me smoke front01
  \item bot status yellow Issue deploying.
  \item bot lbctl disable front01
  \item bot deploy myapp to prod/front01
  \item bot log me smoke front01
  \item bot status green Everything is ok.
  \item bot lbctl enable front01
\end{itemize}
\clearpage

%------------------------------------------------

\subsection{More examples}
\begin{itemize}
\item bot pingdom checks
\item bot who is on call
\item bot conns loadbalancer
\item bot graph me -10min @collectd.load(rabbitmq*)
\item bot procs unicorn
\item bot whois 1.2.3.4
\item bot ci status rails/rails
\item bot log me hooks front01
\end{itemize}

\clearpage

%------------------------------------------------

% How to include a theorem in this presentation:
% \begin{verbatim}
% \mybox{0.8\textwidth}{
% \begin{theorem}[Murphy (1949)]
% Anything that can go wrong, will go wrong.
% \end{theorem}
% }
% \end{verbatim}

% \clearpage

%------------------------------------------------

% \section{Displaying Information}

% \clearpage

%------------------------------------------------

% \subsection{Table}

% \begin{table}[h]
% \centering
% \begin{tabular}{l l l}
% \toprule
% \textbf{Treatments} & \textbf{Response 1} & \textbf{Response 2}\\
% \midrule
% Treatment 1 & 0.0003262 & 0.562 \\
% Treatment 2 & 0.0015681 & 0.910 \\
% Treatment 3 & 0.0009271 & 0.296 \\
% \bottomrule
% \end{tabular}
% \caption{Table caption}
% \end{table}

% \clearpage

%------------------------------------------------

\subsection{ChatOps @ peerTransfer}

\begin{figure}[h]
\centering\includegraphics[width=0.8\linewidth]{cibuild.png}
\end{figure}

\clearpage

%------------------------------------------------

\begin{figure}[h]
\centering\includegraphics[width=0.8\linewidth]{librato.png}
\end{figure}

\clearpage

%------------------------------------------------

\begin{figure}[h]
\centering\includegraphics[width=0.8\linewidth]{pagerduty.png}
\end{figure}

\clearpage

%------------------------------------------------

\begin{figure}[h]
\centering\includegraphics[width=1.0\linewidth]{papertrail.png}
\end{figure}

\clearpage

%------------------------------------------------

\begin{figure}[h]
\centering\includegraphics[width=0.9\linewidth]{deploy.png}
\end{figure}

\clearpage

%------------------------------------------------

\begin{figure}[h]
\centering\includegraphics[width=0.8\linewidth]{deploy_mono.png}
\end{figure}

\clearpage

%------------------------------------------------

% \subsection{Theorem}

% The most common definition of \mygreen{Murphy's Law} is as follows.

% \mybox{0.8\textwidth}{ % Example of encapsulating text in a colored box
% \begin{theorem}[Murphy (1949)]
% Anything that can go wrong, will go wrong.
% \end{theorem}
% }

% \begin{proof}
% A special case of this theorem is proven in the textbook.
% \end{proof}

% \begin{remark}
% This is a remark.
% \end{remark}

% \begin{algorithm}
% This is an algorithm.
% \end{algorithm}

% \clearpage

%------------------------------------------------

% \section{Citations}

% An example of the \texttt{\textbackslash cite} command to cite within the presentation:

% This statement requires citation \cite{Smith:2012qr}.

% \clearpage

%------------------------------------------------

\thispagestyle{empty} % No slide header and footer

\section{Bibliography}

\bibliographystyle{unsrt}
http://www.pagerduty.com/blog/what-is-chatops/

http://blog.librato.com/posts/fire-in-the-hole

http://blog.librato.com/posts/confessions-of-a-chatbot

http://slides.com/carolnichols/chatops

http://tech.toptable.co.uk/blog/2013/11/22/beginning-a-journey-to-chatops-with-hubot/

http://docs.lita.io/plugin-authoring/handlers/

\bibliography{sample}
\clearpage

%------------------------------------------------

\thispagestyle{empty} % No slide header and footer

\begin{tikzpicture}[remember picture,overlay] % Background box
\node [xshift=\paperwidth/2,yshift=\paperheight/2] at (current page.south west)[rectangle,fill,inner sep=0pt,minimum width=\paperwidth,minimum height=\paperheight/3,top color=mygreen,bottom color=mygreen]{}; % Change the height of the box, its colors and position on the page here
\end{tikzpicture}
% Text within the box
\begin{flushright}
\vspace{0.6cm}
\color{white}\sffamily
{\bfseries\LARGE Questions?\par} % Request for questions text
\vfill
\end{flushright}

\clearpage

%----------------------------------------------------------------------------------------

\thispagestyle{empty} % No slide header and footer

\begin{tikzpicture}[remember picture,overlay] % Background box
\node [xshift=\paperwidth/2,yshift=\paperheight/2] at (current page.south west)[rectangle,fill,inner sep=0pt,minimum width=\paperwidth,minimum height=\paperheight/2,top color=mygreen,bottom color=mygreen]{}; % Change the height of the box, its colors and position on the page here
\end{tikzpicture}
% Text within the box
\begin{flushright}
\vspace{0.6cm}
\color{white}\sffamily
{\bfseries\LARGE Thanks!\par}
{\bfseries\LARGE Valencia DevOps\par}
{\bfseries\LARGE April 2015\par}
\vfill
\end{flushright}

\end{document}


text:
% The MIT License (MIT)
%
% Copyright (c) 2020-2021 Yegor Bugayenko
%
% Permission is hereby granted, free of charge, to any person obtaining a copy
% of this software and associated documentation files (the "Software"), to deal
% in the Software without restriction, including without limitation the rights
% to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
% copies of the Software, and to permit persons to whom the Software is
% furnished to do so, subject to the following conditions:
%
% The above copyright notice and this permission notice shall be included
% in all copies or substantial portions of the Software.
%
% THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
% IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
% FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL THE
% AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
% LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
% OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
% SOFTWARE.

\documentclass[sigplan,nonacm=true]{acmart}
\settopmatter{printfolios=false,printccs=false,printacmref=false}
\usepackage[utf8]{inputenc}
\usepackage{ffcode}
\usepackage{CJKutf8}
\usepackage{paralist}
\usepackage{anyfontsize} % To get rid of font not found warnings
\usepackage{tabularx} % for special tables
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{tcolorbox} % for algorithm
  \tcbuselibrary{skins}
\usepackage{fdsymbol} % for \mathbb
\usepackage{algpseudocode} % for algorithms
\usepackage{multicol} % for two cols in BNF
\usepackage{pgffor} % to enable \foreach
\usepackage{stmaryrd}
\usepackage{mathtools}
\newtheoremstyle{theorems}
  {} % Space above
  {} % Space below
  {} % Theorem body font % (default is "\upshape")
  {} % Indent amount
  {\scshape} % Theorem head font % (default is \mdseries)
  {.} % Punctuation after theorem head % default: no punctuation
  { } % Space after theorem head
  {} % Theorem head spec
\theoremstyle{theorems}
\newtheorem{eodefinition}{Definition}
\newtheorem{eotheorem}{Theorem}

\tolerance=1500
\raggedbottom

\newcommand\nospell[1]{#1}
\newcommand\br{\\[-4pt]}
\newcommand\figcap[1]{\caption{#1}\Description{#1}}
\newcommand\phic{{$\varphi$-calculus}}
\newcommand\eo{{\sffamily EO}}
\newcommand\XMIR{{\sffamily XMIR}}
\newcommand\tbd[1]{{\color{red}#1}}
\newcommand\lref[1]{the line no.~\ref{ln:#1}}
\newcommand\lrefs[2]{the lines~\ref{ln:#1}--\ref{ln:#2}}

\newenvironment{twocols}{}{}

\acmBooktitle{untitled}
\title{EOLANG and \texorpdfstring{$\varphi$}{phi}-calculus}
\author{Yegor Bugayenko}{}{}
\email{yegor256@gmail.com}
\affiliation{
  \institution{}
  \city{Moscow}
  \country{Russia}
}
\ccsdesc[300]{Software and its engineering~Software notations and tools~Formal language definitions}
\keywords{Object-Oriented Programming, Object Calculus}

\input{sections/tikz-config}
\begin{document}

\begin{abstract}
Object-oriented programming (OOP) is one of the most popular
paradigms used for building software systems. However, despite
its industrial and academic popularity, OOP is still missing
a formal apparatus similar to $\lambda$-calculus, which functional
programming is based on. There were a number of attempts to formalize
OOP, but none of them managed to cover all the features available in
modern OO programming languages, such as C++ or Java.
We have made yet another attempt and created \phic{}. We also
created EOLANG (also called \eo{}), an experimental
programming language based on \phic{}.
\end{abstract}

\maketitle

\section{Introduction}
\label{sec:intro}
\input{sections/intro}
\input{sections/overview}

The rest of the paper is dedicated to the discussion of the
syntax of the language we created based on the calculus,
the calculus itself, its semantics, and pragmatics.
In order to make it easier to understand, we start
the discussion with the syntax of the language, while the calculus
is derived from it. Then, we discuss the
key features of \eo{} and the differences between it and other
programming languages. We also discuss how the absence of traditional
OOP features, such as mutability or inheritance, affect the complexity of code.
At the end of the paper we overview the work done by others in the area of
formalization of OOP.

\section{Syntax}
\label{sec:syntax}
\input{sections/syntax}

\section{Calculus}
\label{sec:calculus}
\input{sections/calculus}

\section{Semantics}
\label{sec:semantics}
\input{sections/semantics}

\section{Pragmatics}
\label{sec:pragmatics}
\input{sections/pragmatics}

\section{Examples}
\label{sec:examples}
\input{sections/examples}

\section{Mappings}
\label{sec:mappings}
\input{sections/mappings}

\section{Key Features}
\label{sec:features}
\input{sections/features}

\section{Four Principles of OOP}
\label{sec:four}
\input{sections/four}

\section{Complexity}
\label{sec:complexity}
\input{sections/complexity}

\section{Related Works}
\label{sec:related}
\input{sections/related}

\section{Acknowledgments}
\input{sections/acks}

\bibliographystyle{ACM-Reference-Format}
\raggedright
\bibliography{main}
\clearpage

\end{document}

max_stars_repo_name: nikololiahim/eo

max_issues_repo_name: nikololiahim/eo

max_forks_repo_name: nikololiahim/eo


text:
\section{Background}

A \emph{string} $S[1,n] = s_{1} \dotso s_{n}$ is a sequence of
\emph{characters} over an \emph{alphabet} $\Sigma = \set{1, \dotsc, \sigma}$.
For indexing purposes, we often consider \emph{text} strings $T[1,n]$ that are
terminated by an \emph{endmarker} $T[n] = \$ = 0$ not occurring elsewhere in
the text. \emph{Binary} sequences are sequences over the alphabet $\set{0,1}$.
If $B[1,n]$ is a binary sequence, its \emph{complement} is binary sequence
$\complement{B}[1,n]$, with $\complement{B}[i] = 1 - B[i]$.

For any binary sequence $B[1,n]$, we define the \emph{subsequence} $S[B]$ of
string $S[1,n]$ as the concatenation of the characters $s_{i}$ with $B[i] = 1$.
The complement $\complement{S}[B]$ of subsequence $S[B]$ is the subsequence
$S[\complement{B}]$. Contiguous subsequences $S[i,j]$ are called
\emph{substrings}. Substrings of the form $S[1,j]$ and $S[i,n]$, $i,j \in
[1,n]$, are called \emph{prefixes} and \emph{suffixes}, respectively. We
define the \emph{lexicographic order} among strings in the usual way.

\subsection{Full-text indexes}

The \emph{suffix tree} (\ST)~\cite{Weiner1973} of text $T$ is a trie
containing the suffixes of $T$, with unary paths compacted into single edges.
Because the degree of every internal node is at least two, there can be at most
$2n-1$ nodes, and the suffix tree can be stored in $\Oh(n \log n)$ bits. In
practice, this is at least $10n$ bytes for small texts~\cite{Kurtz1999}, and
more for large texts as the pointers grow larger. If $v$ is a node of a suffix
tree, we write $\pi(v)$ to denote the concatenation of the labels of the path
from the root to $v$.

\emph{Suffix arrays} (\SA)~\cite{Manber1993} were introduced as a
space-efficient alternative to suffix trees. The suffix array $\mSA_{T}[1,n]$ of
text $T$ is an array of pointers to the suffixes of the text in lexicographic
order.\footnote{We drop the subscript if the text is evident from the context.}
In its basic form, the suffix array requires $n \log n$ bits in
addition to the text, but its functionality is more limited than that of the
suffix tree. In addition to the suffix array, many algorithms also use the
\emph{inverse suffix array} $\mISA[1,n]$, with $\mSA[\mISA[i]] = i$ for all
$i$.

Let $\mlcp(S_{1}, S_{2})$ be the length of the \emph{longest common prefix}
(\LCP) of strings $S_{1}$ and $S_{2}$. The \LCP{}
\emph{array}~\cite{Manber1993} $\mLCP[1,n]$ of text $T$ stores the \LCP{}
lengths for lexicographically adjacent suffixes of $T$ as $\mLCP[i] =
\mlcp(T[\mSA[i-1],n], T[\mSA[i],n])$ (with $\mLCP[1] = 0$). Let $v$ be an internal node of the
suffix tree, $\ell = \abs{\pi(v)}$ the \emph{string depth} of node $v$, and
$\mSA[sp,ep]$ the corresponding suffix array interval. The following
properties hold for the \emph{lcp-interval} $\mLCP[sp,ep]$: i) $\mLCP[sp] <
\ell$; ii) $\mLCP[i] \ge \ell$ for all $sp < i \le ep$; iii) $\mLCP[i] = \ell$
for at least one $sp < i \le ep$; and iv) $\mLCP[ep+1] <
\ell$~\cite{Abouelhoda2004}.

Abouelhoda et al.~\cite{Abouelhoda2004} showed how traversals on the suffix
tree could be simulated using the suffix array, the \LCP{} array, and a
representation of the suffix tree topology based on lcp-intervals, paving
the way for more space-efficient suffix tree representations.

\subsection{Compressed text indexes}

Data structures supporting \rank{} and \select{} queries over sequences are
the main building blocks of compressed text indexes. If $S$ is a sequence, we
define $\mrank_{c}(S,i)$ as the number of occurrences of character $c$ in
the prefix $S[1,i]$, while $\mselect_{c}(S,j)$ is the position of the occurrence
of rank $j$ in sequence $S$. A \emph{bitvector} is a representation of a
binary sequence supporting fast \rank{} and \select{} queries.
\emph{Wavelet trees} (\WT)~\cite{Grossi2003} use bitvectors to support \rank{}
and \select{} on general sequences.

The \emph{Burrows-Wheeler transform} (\BWT)~\cite{Burrows1994} is a reversible
permutation $\mBWT[1,n]$ of text $T$. It is defined as $\mBWT[i] = T[\mSA[i] -
1]$ (with $\mBWT[i] = T[n]$ if $\SA[i] = 1$). Originally intended for data
compression, the Burrows-Wheeler transform has been widely used in
space-efficient text indexes, because it shares the combinatorial structure of
the suffix tree and the suffix array.

Let \LF{} be a function such that $\mSA[\mLF(i)] = \mSA[i] - 1$ (with
$\mSA[\mLF(i)] = n$ if $\mSA[i] = 1$). We can compute it as $\mLF(i) =
\mC[\mBWT[i]] + \mrank_{\mBWT[i]}(\mBWT, i)$, where $\mC[c]$ is the number of
occurrences of characters with lexicographical values smaller than $c$ in
\BWT. The inverse function of \LF{} is $\mPsi$, with $\mPsi(i) =
\mselect_{c}(\mBWT, i - \mC[c])$, where $c$ is the largest character value
with $\mC[c] < i$. With functions $\mPsi$ and \LF, we can move forward and
backward in the text, while maintaining the lexicographic rank of the current
suffix. If the sequence $S$ is not evident from the context, we write $\mLF_{S}$
and $\mPsi_{S}$.

\emph{Compressed suffix arrays} (\CSA) \cite{Sadakane2003,Ferragina2005a,Grossi2005} are
text indexes supporting a functionality similar to the suffix array. This
includes the following queries: i) $\mfind(P) = [sp,ep]$ determines the
lexicographic range of suffixes starting with \emph{pattern} $P[1,\ell]$; ii)
$\mlocate(sp,ep) = \mSA[sp,ep]$ returns the starting positions of these
suffixes; and iii) $\mextract(i,j) = T[i,j]$ extracts substrings of the text.
In practice, the \find{} performance of {\CSA}s can be
competitive with suffix arrays, while \locate{} queries are orders of
magnitude slower~\cite{Ferragina2009a}. Typical index sizes are less than the
size of the uncompressed text.

The \emph{FM-index} (\FMI) \cite{Ferragina2005a} is a common type of
compressed suffix array. A typical implementation \cite{Ferragina2007a}
stores the \BWT{} in a
wavelet tree \cite{Grossi2003}. The index implements \find{} queries via
\emph{backward searching}. Let $[sp,ep]$ be the lexicographic
range of the suffixes of the text starting with suffix $P[i+1,\ell]$ of the
pattern. We can find the range matching suffix $P[i,\ell]$ with a
generalization of function \LF{} as
\begin{eqnarray*}
\mLF([sp,ep],P[i]) &\!\!\!=\!\!\!&
[\mC[P[i]] + \mrank_{P[i]}(\mBWT, sp\!-\!1) \!+\! 1, \\
&& \,\,\mC[P[i]] + \mrank_{P[i]}(\mBWT, ep)].
\end{eqnarray*}

We support \locate{} queries by \emph{sampling} some suffix array pointers. If
we want to determine a value $\mSA[i]$ that has not been sampled, we can
compute it as $\mSA[i] = \mSA[j]+k$, where $\mSA[j]$ is a sampled pointer
found by iterating \LF{} $k$ times, starting from position $i$. Given
\emph{sample interval} $d$, the samples can be chosen in \emph{suffix order},
sampling $\mSA[i]$ at positions divisible by $d$, or in \emph{text order},
sampling $T[i]$ at positions divisible by $d$ and marking the sampled \SA{}
positions in a bitvector. Suffix-order sampling requires less space, often
resulting in better time/space trade-offs in practice, while text-order
sampling guarantees better worst-case performance. We also sample the \ISA{}
pointers for \extract{} queries. To extract $T[i,j]$, we find the nearest
sampled pointer after $T[j]$, and traverse backwards to $T[i]$ with
function \LF.

\begin{table*}
\centering{}
\caption{Typical compressed suffix tree operations.}\label{table:cst
operations}

\begin{tabular}{ll}
\hline
\noalign{\smallskip}
\textbf{Operation}  & \textbf{Description} \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
$\mRoot()$          & The root of the tree. \\
$\mLeaf(v)$         & Is node $v$ a leaf? \\
$\mAncestor(v,w)$   & Is node $v$ an ancestor of node $w$? \\
\noalign{\smallskip}
$\mCount(v)$        & Number of leaves in the subtree with $v$ as the root. \\
$\mLocate(v)$       & Pointer to the suffix corresponding to leaf $v$. \\
\noalign{\smallskip}
$\mParent(v)$       & The parent of node $v$. \\
$\mFChild(v)$       & The first child of node $v$ in alphabetic order. \\
$\mNSibling(v)$     & The next sibling of node $v$ in alphabetic order. \\
$\mLCA(v,w)$        & The lowest common ancestor of nodes $v$ and $w$. \\
\noalign{\smallskip}
$\mSDepth(v)$       & \emph{String depth}: Length $\ell = \abs{\pi(v)}$ of the
label from the root to node $v$. \\
$\mTDepth(v)$       & \emph{Tree depth}: The depth of node $v$ in the suffix
tree. \\
$\mLAQ_{S}(v,d)$    & The highest ancestor of node $v$ with string depth at
least $d$. \\
$\mLAQ_{T}(v,d)$    & The ancestor of node $v$ with tree depth $d$. \\
\noalign{\smallskip}
$\mSLink(v)$        & \emph{Suffix link}: Node $w$ such that $\pi(v) = c \pi(w)$ for
a character $c \in \Sigma$. \\
$\mSLink^{k}(v)$    & Suffix link iterated $k$ times. \\
\noalign{\smallskip}
$\mChild(v,c)$      & The child of node $v$ with edge label starting with
character $c$. \\
$\mLetter(v,i)$     & The character $\pi(v)[i]$. \\
\noalign{\smallskip}
\hline
\end{tabular}
\end{table*}

\emph{Compressed suffix trees} (\CST) \cite{Sadakane2007} are compressed text
indexes supporting the full functionality of a suffix tree (see
Table~\ref{table:cst operations}). They combine a compressed suffix array, a
compressed representation of the \LCP{} array, and a compressed representation
of suffix tree topology. For the \LCP{} array, there are several common
representations:
\begin{itemize}
\item \LCPbyte{} \cite{Abouelhoda2004} stores the \LCP{} array as a byte
array. If $\mLCP[i] < 255$, the \LCP{} value is stored in the byte array.
Larger values are marked with a $255$ in the byte array and stored separately.
As many texts produce small \LCP{} values, \LCPbyte{} usually requires
$n$ to $1.5n$ bytes of space.
\item We can store the \LCP{} array by using variable-length codes. \LCPdac{}
uses \emph{directly addressable codes} \cite{Brisaboa2009} for the purpose,
resulting in a structure that is typically somewhat smaller and somewhat
slower than \LCPbyte.
\item The \emph{permuted} \LCP{} (\PLCP) \emph{array} \cite{Sadakane2007}
$\mPLCP[1,n]$ is the \LCP{} array stored in text order and used as $\mLCP[i] =
\mPLCP[\mSA[i]]$. Because $\mPLCP[i+1] \ge \mPLCP[i]-1$, the array can be
stored as a bitvector of length $2n$ in $2n+\oh(n)$ bits. If the text is
repetitive, run-length encoding can be used to compress the bitvector to take
even less space \cite{Fischer2009a}. Because accessing \PLCP{} uses \locate,
it is much slower than the above two encodings.
\end{itemize}

Suffix tree topology representations are the main difference between the
various \CST{} proposals. While the compressed suffix arrays and the \LCP{} arrays
are interchangeable, the tree representation determines how various suffix tree
operations are implemented. There are three main families of compressed suffix
trees:
\begin{itemize}
\item \emph{Sadakane's compressed suffix tree} (\CSTsada) \cite{Sadakane2007}
uses a \emph{balanced parentheses} representation for the tree. Each node is
encoded as an opening parenthesis, followed by the encodings of its children
and a closing parenthesis. This can be encoded as a bitvector of length $2n'$,
where $n'$ is the number of nodes, requiring up to $4n+\oh(n)$ bits.
\CSTsada{} tends to be larger and faster than the other compressed suffix
trees \cite{Gog2011a,Abeliuk2013}.
\item The \emph{fully compressed suffix tree} (\FCST) of Russo et
al.~\cite{Russo2011,Navarro2014a} aims to use as little space as possible. It
does not require an \LCP{} array at all, and stores a balanced parentheses
representation for a sampled subset of suffix tree nodes in $\oh(n)$ bits.
Unsampled nodes are retrieved by following suffix links. \FCST{} is smaller
and much slower than the other compressed suffix trees
\cite{Russo2011,Abeliuk2013}.
\item Fischer et al.~\cite{Fischer2009a} proposed an intermediate
representation, \CSTnpr, based on lcp-intervals. Tree navigation is handled
by searching for the values defining the lcp-intervals. \emph{Range minimum
queries} $\mrmq(sp,ep)$ find the leftmost minimal value in $\mLCP[sp,ep]$,
while \emph{next/previous smaller value} queries $\mnsv(i)$/$\mpsv(i)$ find
the next/previous \LCP{} value smaller than $\mLCP[i]$. After the improvements
by various authors \cite{Ohlebusch2009,Fis10,Ohlebusch2010,Gog2011a,Abeliuk2013},
the \CSTnpr{} is perhaps the most practical compressed suffix tree.
\end{itemize}

For typical texts and component choices, the size of compressed suffix trees
ranges from the $1.5n$ to $3n$ bytes of \CSTsada{} to the $0.5n$ to $n$ bytes
of \FCST{} \cite{Gog2011a,Abeliuk2013}. There are also some \CST{} variants
for repetitive texts, such as versioned document collections and collections
of individual genomes. Abeliuk et al.~\cite{Abeliuk2013} developed a variant
of \CSTnpr{} that can sometimes be smaller than $n$ bits, while achieving
performance similar to the \FCST. Navarro and Ordóñez \cite{Navarro2015} used
grammar-based compression for the tree representation of \CSTsada. The
resulting compressed suffix tree (\GCT) requires slightly more space than the
\CSTnpr{} of Abeliuk et al., while being closer to the non-repetitive
\CSTsada{} and \CSTnpr{} in performance.

\subsection{Relative Lempel-Ziv}\label{sect:rlz}

\emph{Relative Lempel-Ziv} (\RLZ) parsing \cite{Kuruppu2010} compresses
\emph{target} sequence $S$ relative to \emph{reference} sequence $R$. The
target sequence is represented as a concatenation of $z$ \emph{phrases} $w_{i}
= (p_{i}, \ell_{i}, c_{i})$, where $p_{i}$ is the starting position of the
phrase in the reference, $\ell_{i}$ is the length of the copied substring, and
$c_{i}$ is the \emph{mismatch} character. If phrase $w_{i}$ starts from
position $p'$ in the target, then $S[p',p'+\ell_{i}-1] =
R[p_{i},p_{i}+\ell_{i}-1]$ and $S[p'+\ell_{i}] = c_{i}$.

The shortest \RLZ{} parsing of the target sequence can be found in
(essentially) linear time. The algorithm builds a \CSA{} for the reverse of
the reference sequence, and then parses the target sequence greedily by using
backward searching. If the edit distance between the reference and the target
is $s$, we need at most $s$ phrases to represent the target sequence. On the
other hand, because the relative order of the phrases can be different in
sequences $R$ and $S$, the edit distance can be much larger than the number of
phrases in the shortest \RLZ{} parsing.

In a straightforward implementation, the \emph{phrase pointers} $p_{i}$ and
the mismatch characters $c_{i}$ can be stored in arrays $W_{p}$ and
$W_{c}$. These arrays take $z \log \abs{R}$ and $z \log \sigma$ bits,
respectively. To support random access to the target sequence, we can encode
phrase lengths as a bitvector $W_{\ell}$ of length $\abs{S}$ \cite{Kuruppu2010}:
we set $W_{\ell}[j] = 1$ if $S[j]$ is the first character of a phrase. The
bitvector requires $z \log \frac{n}{z} + \Oh(z)$ bits if we use the
\sdarray{} representation \cite{Okanohara2007}. To extract $S[j]$, we first
determine the phrase $w_{i}$, with $i = \mrank_{1}(W_{\ell}, j)$. If
$W_{\ell}[j+1] = 1$, we return the mismatch character $W_{c}[i]$. Otherwise
we determine the phrase offset with a \select{} query, and return the character
$R[W_{p}[i] + j - \mselect_{1}(W_{\ell}, i)]$.

Ferrada et al.~\cite{Ferrada2014} showed how, by using \emph{relative pointers} instead of absolute pointers, we can avoid the use of \select{} queries. They also achieved better compression of DNA collections, in which most of the differences between the target sequences and the reference sequence are single-character \emph{substitutions}. By setting $W_{r}[i] = p_{i} - \mselect_{1}(W_{\ell}, i)$, the general case simplifies to $S[j] = R[W_{r}[i] + j]$.  If most of the differences are single-character substitutions, $p_{i+1}$ will often be $p_{i} + \ell_{i} + 1$. This corresponds to $W_{r}[i+1] = W_{r}[i]$ with relative pointers, making \emph{run-length encoding} of the pointer array worthwhile.

When we sort the suffixes in lexicographic order, substitutions in the text move suffixes around, creating \emph{insertions} and \emph{deletions} in the suffix array and related structures. In the \LCP{} array, an insertion or deletion affecting $\mLCP[i]$ can also change the value of $\mLCP[i+1]$. Hence \RLZ{} with relative pointers is not enough to compress the \LCP{} array.

Cox et al.~\cite{CoxEtAl16} modified Ferrada et al.'s version of \RLZ{} to handle other small variations in addition to single-character substitutions. After adding a phrase to the parse, we look ahead a bounded number of positions to find potential phrases with a relative pointer $W_{r}[i]$ close to the previous \emph{explicit} relative pointer $W_{r}[j]$. If we can find a sufficiently long phrase this way, we encode the pointer \emph{differentially} as $W_{r}[i] - W_{r}[j]$. Otherwise we store $W_{r}[i]$ explicitly. We can then save space by storing the differential pointers separately using less bits per pointer. Because there can be multiple mismatch characters between phrases $i$ and $i+1$, we also need a prefix-sum data structure $L$ for finding the range $W_{c}[a,b]$ containing the mismatches. Cox et al.\ showed that their approach compresses both DNA sequences and \LCP{} arrays better than Ferrada et al.'s version, albeit with slightly slower random access. We refer the reader to their paper for more details of their implementation.

max_stars_repo_name: jltsiren/relative-fm

max_issues_repo_name: jltsiren/relative-fm

max_forks_repo_name: jltsiren/relative-fm