From b7450bae14a166e9f67c3368b2a62ed33e175960 Mon Sep 17 00:00:00 2001 From: Mart Lubbers Date: Mon, 2 Feb 2015 15:20:36 +0100 Subject: [PATCH] thing --- thesis2/3.methods.tex | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-) diff --git a/thesis2/3.methods.tex b/thesis2/3.methods.tex index 2f671be..0b16d52 100644 --- a/thesis2/3.methods.tex +++ b/thesis2/3.methods.tex @@ -61,13 +61,21 @@ which there is no graph $G'$ that has less paths and $\mathcal{L}(G)=\mathcal{L }(G')$ where $\mathcal{L}(G)$ is the set of all words present in the DAWG. \subsection{Algorithm} +The algorithm of building DAWGs is an iterative process that goes roughly in +three 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$ +\begin{itemize} + \item + -Pseudocode for the algorithm can be found in Listing~\ref{pseudodawg}. Incrementally node-lists are added to create a graph. For example in {Subgraphs in Figure}~\ref{dawg1} visualizes the construction of the DAWG from the entries: \texttt{aibc}, \texttt{aibc} and \texttt{ajbd}. +Pseudocode for the algorithm can be found in Listing~\ref{pseudodawg}. + In SG0 the graph is only the null graph, described by $G=(\{q_0\},\{q_0\},\{\}\{\})$ and does not contain any entries. -- 2.20.1