\section{Application overview}
-The backend consists of several processing steps before a crawler specification
-is ready. These steps are visualized in Figure~\ref{appinternals} where all the
-nodes are important milestones in the process of processing the user data.
-Arrows indicate informatio transfer between these steps. The Figure is a
-detailed explanation of the \textit{Backend} node in Figure~\ref{appoverview}.
+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 informatio transfer
+between these steps. The Figure is a detailed explanation of the
+\textit{Backend} node in Figure~\ref{appoverview}.
\begin{figure}[H]
\label{appinternals}
\end{figure}
\section{HTML data}
-The raw data from the \textit{Frontend} with the user markings will enter the
-backend as a HTTP \textit{POST} request and consists of several information
-fields extracted from the description boxes in the front and accompanied by the
-raw \textit{HTML} data from the table with the feed entries that contain the
-marking made by the user at the time just before the submit button is pressed.
-Within the \textit{HTML} data of the table markers are placed before sending to
-make the parsing of the tables more easy and remove the need for an advanced
-\textit{HTML} parser. The \textit{POST} request is not send asynchronously,
-this means the user has to wait until the server has processed the request. In
-this way the user will be immediately notified when the processing has finished
+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 precicely 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 Javascript and thus
-on the user side, all the processing afterwards is done in the backend and thus
-server side. All the descriptive fields will be transferred to the final
-aggregating dictionary.
+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 the rows within from the \textit{HTML}
-data. Because of the table markers this process can be done using very
-rudimentary matching techniques that require very little computational power.
-All the \texttt{SPAN} \textit{HTML} elements have to be found since the marking
-of the user are visualized through colored \texttt{SPAN} elements. To achieve
-this for every row all \texttt{SPAN} elements are extracted, again with simple
-matching techniques, to extract 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
+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, again with simple matching
+techniques, to extract 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 are going to be processing into so
-called node-lists. A node-list can be seen as a path graph of every character
-and marking. A path graph $G$ is defined as $G=(V,n_1,E,n_i)$ where $V=\{n_1,
-n_2, \cdots, n_{i-1}, n_i\}$ and $E=\{(n_1, n_2), (n_2, n_3), ... (n_{i-1},
-n_{i})\}$. A path graph is basically a graph that is a path of nodes where
-every node is connected to the next on and the last on being final. The
+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, \cdots, n_{i-1}, n_i\}$ and $E=\{(n_1,
+n_2), (n_2, n_3), ... (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 make it visible in Figure~\ref{nodelistexample}.
+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
\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
+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
+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 the DAWG to check if a
+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 while trying to find a path following the
-characters from the entry. The first algorithm to generate DAWGs from
+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
+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
-two steps. We start with the null graph that can be described by
+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. We just create a new node for every transition of
+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 stepwise approach.
+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)}
\begin{enumerate}
\item
- Say we add word $w$ to the grahp. 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''$.
+ Say we add word $w$ to the grahp. 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.
+ 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.
+ 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.
+ 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}
-Pseudocode for the algorithm can be found in Listing~\ref{pseudodawg}.
+\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}
\subsection{Example}
We visualize this 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}. In SG0 we begin with the null
-graph.
-
-Adding the first entry \texttt{abcd} is trivial because just creates a single
-path and does not require any hard work. Because the common prefix we find in
-Step 1 is empty the suffix will be the entire word. There is also no
-possibility of merging nodes because there were no nodes to begin with. The
-result of adding the first word is visible in subgraph SG1.
-
-For the second entry \texttt{aecd} 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.
-
-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.
+\texttt{abcd}, \texttt{aecd} and \texttt{aecf}.
+
+\begin{itemize}
+ \item Initial\\
+ 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 \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 \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 \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]
\label{dawg1}
\centering
- \includegraphics[scale=0.4]{inccons.eps}
+ \includegraphics[width=0.9\linewidth]{inccons.eps}
+ \strut\\\strut\\
\caption{Incrementally constructing a DAWG}
\end{figure}
repositories / bsc-thesis1415.git / commitdiff