final

[bsc-thesis1415.git] / thesis2 / 3.methods.tex

\section{Application overview}
The backend consists of several processing steps that the input has go through
before it is converted to a crawler specification. These steps are visualized
in Figure~\ref{appinternals}. All the nodes are important milestones in the
process of processing the user data. Arrows indicate information transfer
between these steps. The Figure is a detailed explanation of the
\textit{Backend} node in Figure~\ref{appoverview}.

\begin{figure}[H]
        \centering
        \includegraphics[width=\linewidth]{backend.pdf}
        \caption{Main module internals\label{appinternals}}
\end{figure}

\section{HTML data}
The raw data from the frontend with the user markings enter the backend as a
HTTP \textit{POST} request. This \textit{POST} request consists of several
information data fields. These data fields are either fields from the static
description boxes in the frontend or raw \textit{HTML} data from the table
showing the processed RSS feed entries which contain the markings made by the
user. The table is sent in whole precisely at the time the user presses the
submit button. Within the \textit{HTML} data of the table markers are placed
before sending. These markers make the parsing of the tables more easy and
remove the need for an advanced \textit{HTML} parser to extract the markers.
The \textit{POST} request is not send asynchronously. Synchronous sending means
the user has to wait until the server has processed the request. In this way
the user will be notified immediately when the processing has finished
successfully and will be able to review and test the resulting crawler. All the
data preparation for the \textit{POST} request is done in \textit{Javascript}
and thus happens on the user side. All the processing afterwards is done in the
backend and thus happens on the server side. All descriptive fields will also
be put directly in the final aggregating dictionary. All the raw \textit{HTML}
data will be sent to the next step.

\section{Table rows}
The first conversion step is to extract individual table rows from the
\textit{HTML} data. In the previous step markers were placed to make the
identification easy of table rows. Because of this, extracting the table rows
only requires rudimentary matching techniques that require very little
computational power. User markings are highlights of certain text elements.
The highlighting is done using \texttt{SPAN} elements and therefore all the
\texttt{SPAN} elements have to be found and extracted. To achieve this for
every row all \texttt{SPAN} elements are extracted to  get the color and
afterwards to remove the element to retrieve the original plain text of the
\textit{RSS} feed entry. When this step is done a data structure containing all
the text of the entries together with the markings will go to the next step.
All original data, namely the \textit{HTML} data per row, will be transferred
to the final aggregating dictionary.

\section{Node lists}
Every entry gotten from the previous step is going to be processing into so
called node-lists. A node-list can be seen as a path graph where every
character and marking has a node. A path graph $G$ is defined as
$G=(V,n_1,E,n_i)$ where $V=\{n_1, n_2, \ldots, n_{i-1}, n_i\}$ and 
$E=\{(n_1, n_2), (n_2, n_3), \ldots\\ (n_{i-1}, n_{i})\}$. A path graph is
basically a graph that is a single linear path of nodes where every node is
connected to the next node except for the last one. The last node is the only
final node.  The transitions between two nodes is either a character or a
marking. As an example we take the entry \texttt{19:00, 2014--11--12 {-}
Foobar} and create the corresponding node-lists and it is shown in
Figure~\ref{nodelistexample}.  Characters are denoted with single quotes,
spaces with an underscore and markers with angle brackets. Node-lists are the
basic elements from which the DAWG will be generated. These node-lists will
also be available in the final aggregating dictionary to ensure consistency of
data and possibility of regenerating the data.
\begin{figure}[H]
        \centering
        \includegraphics[width=\linewidth]{nodelistexample.pdf}
        \caption{Node list example\label{nodelistexample}}
\end{figure}

\section{DAWGs}
\subsection{Terminology}
\textbf{Parent nodes} are nodes that have an arrow to the child.\\
\textbf{Confluence nodes} are nodes that have multiple parents.

\subsection{Datastructure}
We represent the user generated patterns as DAWGs by converting the node-lists
to DAWGs. Normally DAWGs have single letters from an alphabet as edgelabel but
in our implementation the DAWGs alphabet contains all letters, whitespace and
punctuation but also the specified user markers which can be multiple
characters of actual length but for the DAWGs sake they are one transition in
the graph.

DAWGs are graphs but due to the constraints we can use a DAWG to check if a
match occurs by checking if a path exists that creates the word by
concatenating all the edge labels. The first algorithm to generate DAWGs from
words was proposed by Hopcroft et al\cite{Hopcroft1971}. It is an incremental
approach in generating the graph. Meaning that entry by entry the graph will be
expanded. Hopcrofts algorithm has the constraint of lexicographical ordering.
Later on Daciuk et al.\cite{Daciuk1998}\cite{Daciuk2000} improved on the
original algorithm and their algorithm is the algorithm we used to generate
minimal DAWGs from the node lists. 

\subsection{Algorithm}
The algorithm of building DAWGs is an iterative process that goes roughly in
four steps. We start with the null graph that can be described by
$G_0=(\{q_0\},\{q_0\},\{\}\{\})$ and does not contain any edges, one node and
$\mathcal{L}(G_0)=\emptyset$. The first word that is added to the graph will be
added in a naive way and is basically replacing the graph by the node-list
which is a path graph. We just create a new node for every transition of
character and we mark the last node as final. From then on all words are added
using a four step approach described below. Pseudocode for this algorithm can
be found in Listing~\ref{pseudodawg} named as the function
\texttt{generate\_dawg(words)}. A \textit{Python} implementation can be found
in Listing~\ref{dawg.py}.
\begin{enumerate}
        \item 
                Say we add word $w$ to the graph. Step one is finding the
                common prefix of the word already in the graph. The common
                prefix is defined as the longest subword $w'$ for which there
                is a $\delta^*(q_0, w')$. When the common prefix is found we
                change the starting state to the last state of the common
                prefix and remain with suffix $w''$ where $w=w'w''$.
        \item
                We add the suffix to the graph starting from the last node of
                the common prefix.
        \item 
                When there are confluence nodes present within the common
                prefix they are cloned starting from the last confluence node
                to avoid adding unwanted words.
        \item
                From the last node of the suffix up to the first node we
                replace the nodes by checking if there are equivalent nodes
                present in the graph that we can merge with.
\end{enumerate}

\begin{algorithm}[H]
        \SetKwProg{Def}{def}{:}{end}
        \Def{generate\_dawg(words)}{%
                register := $\emptyset$\;
                \While{there is another word}{%
                        word := next word\;
                        commonprefix := CommonPrefix(word)\;
                        laststate := %
delta\textsuperscript{*}(q0, commonprefix)\;
                        currentsuffix := %
word[length(commonprefix)\ldots length(word)]\;
                        \If{has\_children(laststate)}{%
                                replace\_or\_register(laststate)\;
                        }
                        add\_suffix(laststate, currentsuffix)\;
                }
                replace\_or\_register(q0)\;
        }
        \Def{replace\_or\_register\_dawg(state)}{%
                child := last\_child(state)\;
                \If{has\_children(child)}{%
                        replace\_or\_register(child)\;
                }
                \eIf{there is an equivalent state q}{%
                        last\_child(state)\;
                        delete(child)\;
                }{%
                        register.add(child)\;
                }
        }
        \caption{Generating DAWGs pseudocode\label{pseudodawg}}
\end{algorithm}

\newpage\subsection{Example}
The size of the graphs that are generated from real world data from the leisure
industry grows extremely fast. Therefore the example concists of short strings
instead of real life event information.
The algorith is visualized with an example shown in the {Subgraphs in
Figure}~\ref{dawg1} that builds a DAWG with the following entries:
\texttt{abcd}, \texttt{aecd} and \texttt{aecf}.

\begin{itemize}
        \item No words added yet\\
                Initially we begin with the null graph. This graph is show in
                the figure as SG0. This DAWG does not yet accept any words.
        \item Adding \texttt{abcd}\\
                Adding the first entry \texttt{abcd} is trivial because we can
                just create a single path which does not require any hard work.
                This is because the common prefix we find in Step 1 is empty
                and the suffix will thus be the entire word. Merging the suffix
                back into the graph is also not possible since there are no
                nodes except for the first node.  The result of adding the
                first word is visible in subgraph SG1.
        \item Adding \texttt{aecd}\\
                For the second entry we will have to do some
                extra work. The common prefix found in Step 1 is \texttt{a}
                which we add to the graph. This leaves us in Step 2 with the
                suffix \texttt{ecd} which we add too. In Step 3 we see that
                there are no confluence nodes in our common prefix and
                therefore we do not have to clone nodes. In Step 4 we traverse
                from the last node back to the beginning of the suffix and find
                a common suffix \texttt{cd} and we can merge these nodes. In
                this way we can reuse the transition from $q_3$ to $q_4$. This
                leaves us with subgraph SG2.
        \item Adding \texttt{aecf}\\
                We now add the last entry which is the word \texttt{aecf}. When
                we do this without the confluence node checking we encounter an
                unwanted extra word. In Step 1 we find the common prefix
                \texttt{aec} and that leaves us with the suffix \texttt{f}
                which we will add. This creates subgraph SG3 and we notice
                there is an extra word present in the graph, namely the word
                \texttt{abcf}.  This extra word appeared because of the
                confluence node $q_3$ which was present in the common prefix
                introducing an unwanted path. Therefore in Step 3 when we check
                for confluence node we would see that node $q_3$ is a
                confluence node and needs to be cloned off the original path,
                by cloning we take the added suffix with it to create an
                entirely new route. Tracking the route back again we do not
                encounter any other confluence nodes so we can start Step 4.
                For this word there is no common suffix and therefore no
                merging will be applied. This results in subgraph SG4 which is
                the final DAWG containing only the words added.
\end{itemize}

\begin{figure}[H]
        \centering
        \includegraphics[height=20em]{inccons.pdf}
        \caption{Incrementally constructing a DAWG\label{dawg1}}
\end{figure}

\subsection{Appliance on extraction of patterns}
The text data in combination with the user markings can not be converted
automatically to a DAWG using the algorithm we described. This is because the
user markings are not necessarily a single character or word. Currently user
markings are subgraphs that accept any word of any length. When we add a user
marking, we are inserting a kind of subgraph in the place of the node with the
marking.  By doing this we can introduce non determinism to the graph. Non
determinism is the fact that a single node has multiple edges with the same
transition, in practise this means it could happen that a word can be present
in the graph in multiple paths. An example of non determinism in one of our
DAWGs is shown in Figure~\ref{nddawg}. This figure represents a generated DAWG
with the following entries: \texttt{ab<1>c}, \texttt{a<1>bc}.

In this graph the word \texttt{abdc} will be accepted and the user pattern
\texttt{<1>} will be filled with the subword \texttt{d}. However if we try the
word \texttt{abdddbc} both paths can be chosen. In the first case the user
pattern \texttt{<1>} will be filled with \texttt{dddb} and in the second case
with \texttt{bddd}. In such a case we need to choose the hopefully smartest
choice. In the case of no paths matching the system will report a failed
extraction. The crawling system can be made more forgiving in such a way that
it will give partial information when no match is possible, however it still
needs to report the error and the data should be handled with extra care.

\begin{figure}[H]
        \centering
        \includegraphics[width=\linewidth]{nddawg.pdf}
        \caption{Example non determinism\label{nddawg}}
\end{figure}

\subsection{Minimality \& non-determinism}
The Myhill-Nerode theorem~\cite{Hopcroft1979} states that for every number of
graphs accepting the same language there is a single graph with the least
amount of states. Mihov\cite{Mihov1998} has proven that the algorithm for
generating DAWGs is minimal in its original form. Our program converts the
node-lists to DAWGs that can possibly contain non deterministic transitions
from nodes and therefore one can argue about Myhill-Nerodes theorem and Mihovs
proof holding. Due to the nature of the determinism this is not the case and
both hold. In reality the graph itself is only non-deterministic when expanding
the categories and thus only during matching. 

Choosing the smartest path during matching the program has to choose
deterministically between possibly multiple path with possibly multiple
results. There are several possibilities or heuristics to choose from.
\begin{itemize}
        \item Maximum fields heuristic\\

                This heuristic prefers the result that has the highest amount
                of categories filled with actual text. Using this method the
                highest amount of data fields will be getting filled at all
                times. The downside of this method is that because of this it
                might be that some data is not put in the right field because a
                suboptimal splitting occurred that has put the data in two
                separate fields whereas it should be in one field.
        \item Maximum path heuristic\\

                Maximum path heuristic tries to find a match with the highest
                amount of fixed path transitions. Fixed path transitions are
                transitions that occur not within a category. The philosophy
                behind is, is that because the path are hard coded in the graph
                they must be important. The downside of this method is when
                overlap occurs between hard coded paths and information within
                the categories. For example a band that is called
                \texttt{Location} could interfere greatly with a hard coded
                path that marks a location using the same words.
\end{itemize}

The more one knows about the contents of the categories the better the Maximum
field heuristic performs. When, as in our current implementation, categories do
not contain information both heuristics perform about the same.