thesis2/3.methods.tex

   1 \section{Internals of the crawler generation module}
   2 Data marked by the user is in principle just raw html data that contains a
   3 table with for every RSS feed entry a table row. Within the html the code
   4 severel markers are placed to make the parsing more easy and removing the need
   5 of an advanced HTML parser. When the user presses submit a http POST request is
   6 prepared to send all the gathered data to the backend to get processed. The
   7 sending does not happen asynchronously, so the user has to wait for the data to
   8 be processed. Because of the sychronous data transmission the user is notified
   9 immediatly when the crawler is succesfully added. The data preparation that
  10 makes the backend able to process it is all done on the user side using
  11 Javascript.
  12
  13 When the backend receives the http POST data it saves all the raw data and the
  14 data from the information fields. The raw data is processed line by line to
  15 extract the entries that contain user markings. The entries containing user
  16 markings are stripped from all html while creating an data structure that
  17 contains the locations of the markings and the original text. All data is
  18 stored, for example also the entries without user data, but not all data is
  19 processed. The storage of, at first sight, useless data is done because later
  20 when the crawlers needs editing the old data can be used to update the crawler.
  21
  22 When the entries are isolated and processed they are converted to node-lists. A
  23 node-list is a literal list of words where a word is interpreted in the
  24 broadest sense, meaning that a word can be a character, a single byte, a string
  25 or basically anything. These node-lists are in this case the original entry
  26 string where all the user markers are replaced by single nodes. As an example
  27 lets take the following entry and its corresponding node-list assuming that the
  28 user marked the time, title and date correctly. Markers are visualized by
  29 enclosing the name of the marker in angle brackets.
  30 \begin{flushleft}
  31         Entry: \texttt{19:00, 2014-11-12 - Foobar}\\
  32         Node-list: \texttt{['<time>', ',', ' ', '<date>', ' ', '-', ' ', '<title>']}
  33 \end{flushleft}
  34
  35 The last step is when the entries with markers are then processed to build
  36 node-lists. Node-lists are basically lists of words that, when concatenated,
  37 form the original entry. A word isn't a word in the linguistic sense. A word
  38 can be one letter or a category. The node-list is generated by putting all the
  39 separate characters one by one in the list and when a user marking is
  40 encountered, this marking is translated to the category code and that code is
  41 then added as a word. The nodelists are then sent to the actual algorithm to be
  42 converted to a graph representation.
  43
  44 \section{Minimizing DAWGs}
  45 \subsection{Datastructure}
  46 We represent the user generated patterns as DAWGs by converting the node-lists
  47 to DAWGS. Normally DAWGs have as edgelabels letters from an alphabet, in our
  48 case the DAWGs alphabet contains all letters, whitespace and punctuation but
  49 also the specified user markers which can be multiple characters in length.
  50
  51 DAWGs are graphs but due to the constraints we can check if a match occurs by
  52 checking if a path exists that creates the word by concatenating all the edge
  53 labels. The first algorithm to
  54 generate DAWGs from words was proposed by Hopcroft et
  55 al\cite{Hopcroft1971}. It is an incremental approach in generating the graph.
  56 Meaning that entry by entry the graph will be expanded. Hopcrofts algorithm has
  57 the constraint of lexicographical ordering. Later on Daciuk et
  58 al.\cite{Daciuk2000} improved on the original algorithm and their algorithm is
  59 the algorithm we used to minimize our DAWGs. A minimal graph is a graph $G$ for
  60 which there is no graph $G'$ that has less paths and $\mathcal{L}(G)=\mathcal{L
  61 }(G')$ where $\mathcal{L}(G)$ is the set of all words present in the DAWG.
  62
  63 \subsection{Algorithm}
  64 The algorithm of building DAWGs is an iterative process that goes roughly in
  65 three steps. We start with the null graph that can be described by
  66 $G_0=(\{q_0\},\{q_0\},\{\}\{\})$ and does not contain any edges, one node and
  67 $\mathcal{L}(G_0)=\emptyset$
  68 \begin{itemize}
  69         \item
  70
  71
  72
  73 Incrementally node-lists are added to create a graph. For example in
  74 {Subgraphs in Figure}~\ref{dawg1} visualizes the construction of the
  75 DAWG from the entries: \texttt{aibc}, \texttt{aibc} and \texttt{ajbd}.
  76
  77 Pseudocode for the algorithm can be found in Listing~\ref{pseudodawg}.
  78
  79 In SG0 the graph is only the null graph, described by
  80 $G=(\{q_0\},\{q_0\},\{\}\{\})$ and does not contain any entries.
  81
  82 Adding the first entry \texttt{a,bc} is not a
  83 hard task because there is no common prefix nor suffix so the entry becomes a
  84 strain of nodes starting from $q_0$ and is visualized in subgraph SG1.
  85
  86 For the second entry \texttt{a.bc} some smart optimization has to be applied.
  87 The common prefix is \texttt{a} and the common suffix is \texttt{bc}. Therefore
  88 the first node in which the common prefix starts needs to be copied and split
  89 off to make room for an alternative route. This is exactly what happens in SG2.
  90 Node $q_2$ is copied and gets a connection to node $q_3$. From the last node of
  91 the common prefix a route is built towards the first node, that is the copied
  92 node, of the common suffix resulting in an extra path $q_1\rightarrow
  93 q_5\rightarrow q_3$. This results in subgraph SG2.
  94
  95 Adding the thing node \texttt{a.bd} in the same naive way as the second node
  96 results in subgraph SG3 and introduces a bad side effect. Namely that a new
  97 word, that was not specifically added was introduced, is added to the DAWG.
  98 This is because within the common prefix there is a node that has some other
  99 arrow leading to it. When a new path is added the algorithm checks the common
 100 prefix and suffix for confluence nodes. Confluence nodes are nodes that have
 101 multiple arrows leading in and because of the multiple arrows they can lead to
 102 unwanted additional words. The first confluence node found must be copied and
 103 detached and the specific suffix from the entry must be copied with it to
 104 separate the path from the existing paths. Applying this technique in the
 105 example leads to subgraph SG4. With common prefix \texttt{a.b} and an empty
 106 common suffix node $q_3$ is found as a confluence node in the common prefix and
 107 therefore node $q_3$ is copied to the new node $q_6$ taking the paths leading
 108 to the final state with it. In this way no new words are added to the DAWG and
 109 the DAWG is still optimal.
 110
 111 \begin{figure}[H]
 112         \caption{Step 1}
 113         \label{dawg1}
 114         \centering
 115         \digraph[width=\linewidth]{inccons}{
 116                 rankdir=LR;
 117                 n4 [style=invis];
 118                 q40 [label="q0"];
 119                 q41 [label="q1"];
 120                 q42 [label="q2"];
 121                 q43 [label="q3"];
 122                 q44 [label="q4" shape=doublecircle];
 123                 q45 [label="q5"];
 124                 q46 [label="q6"];
 125                 n4 -> q40[label="SG4"];
 126                 q40 -> q41[label="a"];
 127                 q41 -> q42[label="i"];
 128                 q42 -> q43[label="b"];
 129                 q43 -> q44[label="c"];
 130                 q41 -> q45[label="j"];
 131                 q45 -> q46[label="b"];
 132                 q46 -> q44[label="d"];
 133                 q46 -> q44[label="c"];
 134
 135                 n3 [style=invis];
 136                 q30 [label="q0"];
 137                 q31 [label="q1"];
 138                 q32 [label="q2"];
 139                 q33 [label="q3"];
 140                 q34 [label="q4"ishape=doublecircle];
 141                 q35 [label="q5"];
 142                 n3 -> q30[label="SG3"];
 143                 q30 -> q31[label="a"];
 144                 q31 -> q32[label="i"];
 145                 q32 -> q33[label="b"];
 146                 q33 -> q34[label="c"];
 147                 q33 -> q34[label="d"iconstraint=false];
 148                 q31 -> q35[label="j"];
 149                 q35 -> q33[label="b"];
 150
 151                 n2 [style=invis];
 152                 q20 [label="q0"];
 153                 q21 [label="q1"];
 154                 q22 [label="q2"];
 155                 q23 [label="q3"];
 156                 q24 [label="q4"ishape=doublecircle];
 157                 q25 [label="q5"];
 158                 n2 -> q20[label="SG2"];
 159                 q20 -> q21[label="a"];
 160                 q21 -> q22[label="i"];
 161                 q22 -> q23[label="b"];
 162                 q23 -> q24[label="c"];
 163                 q21 -> q25[label="j"];
 164                 q25 -> q23[label="b"];
 165
 166                 n1 [style=invis];
 167                 q10 [label="q0"];
 168                 q11 [label="q1"];
 169                 q12 [label="q2"];
 170                 q13 [label="q3"];
 171                 q14 [label="q4"ishape=doublecircle];
 172                 n1 -> q10[label="SG1"];
 173                 q10 -> q11[label="a"];
 174                 q11 -> q12[label="i"];
 175                 q12 -> q13[label="b"];
 176                 q13 -> q14[label="c"];
 177
 178                 n [style=invis];
 179                 q0 [label="q0"];
 180                 n -> q0[label="SG0"];
 181         }
 182 \end{figure}