\textit{Backend} node in Figure~\ref{appoverview}.
\begin{figure}[H]
- \label{appinternals}
\centering
\includegraphics[width=\linewidth]{backend.pdf}
- \caption{Main module internals}
+ \caption{Main module internals\label{appinternals}}
\end{figure}
\section{HTML data}
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.
+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, \cdots, 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.
+$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]
- \label{nodelistexample}
\centering
\includegraphics[width=\linewidth]{nodelistexample.pdf}
- \caption{Node list example}
+ \caption{Node list example\label{nodelistexample}}
\end{figure}
\section{DAWGs}
\begin{algorithm}[H]
\SetKwProg{Def}{def}{:}{end}
- \Def{generate\_dawg(words)}{
+ \Def{generate\_dawg(words)}{%
register := $\emptyset$\;
\While{there is another word}{%
word := next word\;
register.add(child)\;
}
}
- \caption{Generating DAWGs pseudocode}
- \label{pseudodawg}
+ \caption{Generating DAWGs pseudocode\label{pseudodawg}}
\end{algorithm}
\newpage\subsection{Example}
-We visualize this with an example shown in the {Subgraphs in
+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}.
\end{itemize}
\begin{figure}[H]
- \label{dawg1}
\centering
\includegraphics[height=20em]{inccons.pdf}
- \caption{Incrementally constructing a DAWG}
+ \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 basically multiple random characters. 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>bbc}.
+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
needs to report the error and the data should be handled with extra care.
\begin{figure}[H]
- \label{nddawg}
\centering
\includegraphics[width=\linewidth]{nddawg.pdf}
- \caption{Example non determinism}
+ \caption{Example non determinism\label{nddawg}}
\end{figure}
\subsection{Minimality \& non-determinism}
path that marks a location using the same words.
\end{itemize}
-If we would know more about the categories the best heuristic automatically
-becomes the maximum path heuristic. When, as in our implementation, there is
-very little information both heuristics perform about the same.
+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.
repositories / bsc-thesis1415.git / blobdiff