\paragraph{Temporum}
The \textit{Temporum} is a big bin that contains raw data extracted from
different sources and has to be post processed to be suitable enough for the
-actual database. This post processing encompasses several possible tasks.
+actual database. This processing encompasses several possible tasks.
The first task is to check the validity of the entry. This is a very shallow
test to check if the crawler is not malfunctioning and there is no nonsense in
-the data.
-
-The second step is matching the entry to several objects. For example the entry
-has to be matched to a certain venue when its source is a ticket vendor who
-sells tickets for multiple venues. Another example is that the event is a pop
-concert and is part of a big tour. Many of these tasks are done alone by or
-with aid of a computer program. Almost no data is going straight through the
+the data. Most of the data is not directly checked for validity, the data is
+skimmed for strange things but not every datapoint is checked. The second step
+is matching the entry to several objects. For example the entry has to be
+matched to a certain venue when its source is a ticket vendor who sells tickets
+for multiple venues. Another example is that the event is a pop concert and is
+part of a big tour. Many of these tasks are done alone by or with aid of a
+computer program. Almost no data is going straight through the
\textit{Temporum} and this property makes the \textit{Temporum} a safety net
for all the incoming data.
preprocessed in the old way, send to the \textit{Temporum} and checked by a
human and matched. The human then notices the error in the data and contacts
the programmer. The programmer then has to reprogram the specific crawler to
-the new structure. This feedback loop, shown in Figure~\ref{fig:1.2.1} can take
-days and can be the reason for gaps or faulty information in the database.
+the new structure. This feedback loop, shown in Figure~\ref{feedbackloop} can
+take days and can be the reason for gaps or faulty information in the database.
\begin{figure}[H]
\caption{Feedback loop for malfunctioning crawlers}
- \label{fig:1.1.2}
+ \label{feedbackloop}
\centering
\scalebox{0.8}{
\digraph[]{graph112}{
The goal of the project is to relieve the programmer of repairing crawlers all
the time and make the task of adapting, editing and removing crawlers doable
for someone without programming experience. In practice this means in
-Figure~\ref{fig:1.1.2} removing the dotted arrows by dashed arrow.
+Figure~\ref{feedbackloop} removing the dotted arrows by dashed arrow.
For this project an application has been developed that can provide an
-interface to a crawler system that is able to crawl
-RSS\footnote{\url{http://rssboard.org/rss-specification}} and
-Atom\footnote{\url{http://tools.ietf.org/html/rfc5023}} publishing feeds.
-The interface also provides the user with point and click interfaces to create,
-modify, test and remove crawlers. The Hyperleap back end can, via this
-interface, generate XML feeds that contain the crawled data. For editing the
-structure and contents of the program a programmer is in theory also not
-necessary because all the things someone wants to change are located in a
-single file that is human readable. In practice it means that one person, not
-by definition a programmer, can be instructed to change the structure and this
-can also greatly reduce programmer intervention time.
+interface to a crawler system that is able to crawl RSS\cite{Rss} and
+Atom\cite{Atom} publishing feeds. The interface also provides the user with
+point and click interfaces to create, modify, test and remove crawlers. The
+Hyperleap back end can, via this interface, generate XML feeds that contain the
+crawled data. For editing the structure and contents of the program a
+programmer is in theory also not necessary because all the things someone wants
+to change are located in a single file that is human readable. In practice it
+means that one person, not by definition a programmer, can be instructed to
+change the structure and this can also greatly reduce programmer intervention
+time.
\section{RSS/Atom}
-RSS/Atom feeds, from now on called RSS feeds, are publishing
-feeds in the XML format\footnote{\url{http://www.w3.org/TR/REC-xml/}} that are
-used to publish events. Every event or entry consists of several standardized
-fields. The main data fields are the \textit{title} and the
-\textit{description} field. In these fields the raw data is stored that
+RSS/Atom feeds, from now on called RSS feeds, are publishing feeds in the XML
+format\cite{Xml} that are used to publish events. Every event or entry consists
+of several standardized fields. The main data fields are the \textit{title} and
+the \textit{description} field. In these fields the raw data is stored that
describes the event. Further there are several auxiliary fields that store the
link to the full article, store the publishing data, store some media in the
form of an image or video URL and store a \textit{Globally Unique
-Identifier}(GUID).
+Identifier}(GUID)\footnote{A GUID is a unique identifier that in most cases is
+the permalink of the article. A permalink is a link that will point to the
+article}. An example of a RSS feed can be found in Listing~\ref{examplerss},
+this listing shows a partly truncated RSS feed of a well known venue in the
+Netherlands.
+
+\begin{listing}
+ \caption{An example of a, partly truncated RSS feed of a well known dutch
+ venue}
+ \label{examplerss}
+ \xmlcode{exrss.xml}
+\end{listing}
The RSS feeds are mostly used by news sites to publish their articles, the feed
then only contains the headlines and if the user that is reading the feed is
\section{Why RSS?}
\label{sec:whyrss}
-Information from venues comes in various different format with for each format
-several positive and negative points. For this project we chose to focus on
-RSS feeds. RSS feeds are, as explained earlier, very structured and consistent
-in their structure. The structure basically only changes if the CMS changes or
-upgrades. Because of this patterns don't have to be retrained a lot.
-
-In comparison to websites RSS feeds don't have a structural dimension in
-the data, all the information in an entry is basically two fields of plain
-text. Therefore an entirely new strategy has to be applied to train the
-patterns.
-
-\section{Scientific relevance and similar research}
-Currently the techniques for conversion from non structured data to structured
-data are static and mainly only usable by computer science experts. There is a
-great need of data mining in non structured data because the data within
-companies and on the internet is piling up and are usually left to catch dust.
-
-The project is a followup project of the past project done by Roelofs et
-al.\cite{Roelofs2008} and \cite{Roelofs2009}. Roelofs et al. described
-techniques on recognizing patterns in website data and published about an
-adapted levenstein distance algorithm to recognize data in isolated text. These
-techniques of recognizing data in text can still be used to interpret the
-isolated extracted parts from this project.
+The first proposal described formats like HTML, fax/email, RSS, XML and some
+more. Because of the scope of the project and the time planned for it we had to
+remove some of the input formats because they all require different techniques.
+For example when the input source is in HTML format, most probably a website,
+then there can be a great deal of information extraction be automated using the
+structural information which is characteristic for HTML. For fax/email however
+there is almost no structural information and most of the automation techniques
+require natural language processing. We chose RSS feeds because RSS feeds lack
+inherent structural information but are still very structured. This structure
+is because, as said above, the RSS feeds are generated and therefore almost
+always look the same. Also, in RSS feeds most venues use particular structural
+identifiers that are characters. They separate fields with vertical bars,
+commas, whitespace and more non text characters. These field separators and
+keywords can be hard for a computer to detect but people are very good in
+detecting these. With one look they can identify the characters and keywords
+and build a pattern in their head.
+Another reason we chose RSS is their temporal consistency, RSS feeds are almost
+always generated and because of that the structure of the entries is very
+unlikely to change. Basically the RSS feeds only change structure when the CMS
+that generates it changes the generation algorithm. This property is usefull
+because the crawlers then do not have to be retrained very often. Because the
+non inherent structure entirely new strategies had to be applied.
\section{Directed Acyclic Graphs}
\paragraph{Normal graphs}
with edges. A standard graph is defined as the ordered pair: $G=(V,E)$. In
this ordered pair $V$ is the set of nodes and $E$ is set of undirected edges
where every undirected edge is a tuple of two nodes.
-Figure~\ref{fig:graphexample} is specified as:
+Figure~\ref{graphexample} is specified as:
$$G=(\{n1, n2, n3\}, \{(n1, n2), (n2, n3), (n2, n3)\})$$
\begin{figure}[H]
\caption{Example Graph}
- \label{fig:graphexample}
+ \label{graphexample}
\centering
\digraph[]{graphexample}{
rankdir=LR
tuples in stead of not ordered. Adding this property gives the edges a
direction. Every edge has a specific start and end and are therefore called
directed edges. A directed graph would look the same as the graph in
-Figure~\ref{fig:graphexample} but then the normal edges would be replaced by
+Figure~\ref{graphexample} but then the normal edges would be replaced by
directional arrows that specifically go from one node to the other.
\paragraph{Directed acyclic graphs}
Directed Acyclic Graphs(DAGs) are a special kind of directed graphs. DAGs
are also defined as $G=(V,E)$ but with a restriction on $E$. Namely that cycles
-are not allowed. Figure~\ref{fig:dagexample} shows two graphs. The left graph
+are not allowed. Figure~\ref{dagexample} shows two graphs. The left graph
contains a cycle and the right graph does not. Only the right graph is a valid
DAG. A cycle is defined by a sequence of edges where nodes are visited more
then once. Adding the property of non-cyclicity to graphs lowers the
\begin{figure}[H]
\caption{Example DAG}
- \label{fig:dagexample}
+ \label{dagexample}
\centering
\digraph[]{dagexample}{
rankdir=LR
\paragraph{Directed Acyclic Word Graphs}
The type of graph used in the project is a special kind of DAG called
-Directed Acyclic Word Graphs(DAWGs). A DAWG can be defined by the ordered pair
-$G=(V,E)$ and is the same as a directed graph except for the edges. An edge in
-a DAWG is instead of a tuple a triple and consist of a starting point, an end
-point and a label. Because of the property of labeled edges data can be stored
+Directed Acyclic Word Graphs(DAWGs). A DAWG can be defined by the ordered
+triple $G=(V,E,F)$.
+$V$ is the same as in directed graphs. $E$ is also the same besides the fact
+that the ordered pair of nodes that describes the edge it now is a triple
+consisting of a start node, an end node and a label. In a standard DAWG the
+label is always one character. $F$ describes the set of final nodes, final
+nodes are nodes that can be the end of a sequence even if another arrow leads
+out. In the example graph in Figure~\ref{exampledawg} the final nodes are
+visualized with a double circle as node shape. In this example it is purely
+cosmetic because $n6$ is a final node anyways because there are no arrows
+leading out. But for example in $G=(\{n1, n2, n3\}, \{(n1, n2), (n2, n3)\},
+\{n2, n3\})$ there is a distinct use for the final node marking. Graph $G$
+accepts the words \textit{a,ab} and to simplify the graph node $n2$ and $n3$
+are final. Because of the property of labeled edges data can be stored
in a DAWG. When traversing a DAWG and saving all the edgelabels one can
construct words. Because of properties of graphs a DAWG can store big sets of
words in a small amount of storage because it can re-use edges to specify
-transitions. For example the graph in Figure~\ref{fig:2.1.1} can describe a
+transitions. For example the graph in Figure~\ref{exampledawg} can describe a
dictionary that holds the words: \textit{abd, bad, bae}. Testing if a word is
present in the DAWG is, just as for a DAG, falls in the computational
complexity class of $\mathcal{O}(L)$ meaning that it grows linearly with the
\begin{figure}[H]
\caption{Example DAWG}
- \label{fig:2.1.1}
+ \label{exampledawg}
\centering
\digraph[]{graph21}{
rankdir=LR;
- 1,2,3,4,5 [shape="circle"];
- 6 [shape="doublecircle"];
- 1 -> 2 [label="a"];
- 2 -> 3 [label="b"];
- 3 -> 6 [label="d"];
- 1 -> 4 [label="b"];
- 4 -> 5 [label="a"];
- 5 -> 6 [label="d"];
- 5 -> 6 [label="e"];
+ n1,n2,n3,n4,n5 [shape="circle"];
+ n6 [shape="doublecircle"];
+ n1 -> n2 [label="a"];
+ n2 -> n3 [label="b"];
+ n3 -> n6 [label="d"];
+ n1 -> n4 [label="b"];
+ n4 -> n5 [label="a"];
+ n5 -> n6 [label="d"];
+ n5 -> n6 [label="e"];
}
\end{figure}
repositories / bsc-thesis1415.git / blobdiff