update

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

diff --git a/thesis2/3.methods.tex b/thesis2/3.methods.tex
index 2bc95bb..5729b79 100644 (file)
--- a/thesis2/3.methods.tex
+++ b/thesis2/3.methods.tex
@@ -217,19 +217,29 @@ added.
 \end{figure}
 
 \subsection{Appliance on extraction of patterns}
-The text data in combination with the user markings are not just plain text and
-thus we can not create a DAWG out of them without a few adaptations to the
-structure.
+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. User markings are
+basically one or more characters. When we add a user marking we insert a
+character that is not in the alphabet and later on we change the marking to a
+kind of subgraph. When this is applied it can be possible that non determinism
+is added to the graph. Non determinism is the fact that a single node has
+multiple edges with the same transition, in practise this means that a word can
+be present in the graph in multiple paths. This is shown in
+Figure~\ref{nddawg} with the following words: \texttt{ab<1>c}, \texttt{a<1>bbc}.
+In this graph the word \texttt{abdc} will be accepted and the user pattern
+\texttt{<1>} will be filled with the word \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.
 
-Adaption for our data
-
-Non determinism
+\begin{figure}[H]
+       \label{nddawg}
+       \centering
+       \includegraphics[width=\linewidth]{nddawg.eps}
+       \caption{Example non determinism}
+\end{figure}
 
-How to get best match
+\subsection{How to choose path}
 
-The algorithm for minimizing DAWGs can not be applied directly on the user
-generated pattern. This is mainly because there is no conclusive information
-about the contents of the pattern and therefore non deterministic choices have
-to be made. Because of this there can be multiple matches and the best match
-has to be determined. There are several possible criteria for determining the
-best match. The method we use is ... TODO