incomplete information. Because of the complexity of getting complete
information there are not many companies trying to bundle entertainment
information into a complete and consistent database and website.
-Hyperleap\footnote{\url{http://hyperleap.nl}} tries to achieve goal of serving
-complete and consistent information and offers it via various information
-bundling websites.
+Hyperleap\footnote{\url{http://hyperleap.nl}} tries to achieve the goal of
+serving complete and consistent information and offers it via various
+information bundling websites.
\newpage
\section{Hyperleap \& Infotainment}
Hyperleap is an internet company that was founded in the time that internet was
publishing and maintaining \textit{infotainment}. \textit{Infotainment} is a
combination of the words \textit{information} and \textit{entertainment}. It
represents a combination of factual information, the \textit{information} part,
-and subjectual information, the \textit{entertainment} part, within a certain
-category or field. In the case of Hyperleap the category is the leisure
-industry, leisure industry encompasses all facets of entertainment ranging from
-cinemas, theaters, concerts to swimming pools, bridge competitions and
-conferences. Within the entertainment industry factual information includes,
-but is not limited to, starting time, location, host or venue and duration.
-Subjectual information includes, but is not limited to, reviews, previews,
-photos, background information and trivia.
+and non factual information or subjectual information, the
+\textit{entertainment} part, within a certain category or field. In the case of
+Hyperleap the category is the leisure industry, leisure industry encompasses
+all facets of entertainment ranging from cinemas, theaters, concerts to
+swimming pools, bridge competitions and conferences. Within the entertainment
+industry factual information includes, but is not limited to, starting time,
+location, host or venue and duration. Subjectual information includes, but is
+not limited to, reviews, previews, photos, background information and trivia.
Hyperleap says to manage the largest database containing \textit{infotainment}
about the leisure industry focussed on the Netherlands and surrounding regions.
flow.
\begin{figure}[H]
-\label{informationflow}
\centering
\includegraphics[width=\linewidth]{informationflow.pdf}
- \caption{Information flow Hyperleap database}
+ \caption{Information flow Hyperleap database\label{informationflow}}
\end{figure}
\subsection{Sources}
stored or published. A source can have different source shapes such as HTML,
email, flyer, RSS and so on. All information gathered from a source has to be
quality checked before it is even considered for automated crawling. There are
-several criteria information from the source has to comply to before an
-automated crawler can be made. The prerequisites for a source are for example
-the fact that the source has to be reliable, consistent and free by licence.
-Event information from a source must have at least the \textit{What, Where} and
-\textit{When} information.
+several criteria to which the source has to comply before an automated crawler
+can be made. The prerequisites for a source are for example the fact that the
+source has to be reliable, consistent and free by licence. Event information
+from a source must have at least the \textit{What, Where} and \textit{When}
+information.
The \textit{What} information is the information that describes the content,
content is a very broad definition but in practice it can be describing the
more.
The \textit{Where} information is the location of the event. The location is
-often omitted because the organization behind source presenting the information
-thinks it is obvious. This information can also include different sub
-locations. For example when a pop concert venue has their own building but in
-the summer they organize a festival in some park. This data is often assumed to
-be trivial and inherent but in practice this is not the case. In this example
-for an outsider only the name of the park is often not enough.
+often omitted because the organization presenting the information thinks it is
+obvious. This information can also include different sub locations. For example
+when a pop concert venue has their own building but in the summer they organize
+a festival in some park. This data is often assumed to be trivial and inherent
+but in practice this is not the case. In this example for an outsider only the
+name of the park is often not enough.
The \textit{When} field is the time and date of the event. Hyperleap wants to
have at minimum the date, start time and end time. In the field end times for
\subsection{Temporum}
The \textit{Temporum} is a big bin that contains raw data extracted from
-different sources using automated crawlers. All the information in the
+different sources using automated crawlers. Some of the information in the
\textit{Temporum} might not be suitable for the final database and therefore
has to be post processed. The post-processing encompasses several different
steps.
The first step is to check the validity of the event entries from a certain
-source. Validity checking is useful to detect faulty automated crawlers
-before the data can leak into the database. Validity checking happens at random
-on certain event entries.
+source. Validity checking is useful to detect outdated automated crawlers
+before the data can leak into the database. Crawlers become outdated when a
+source changes and the crawler can not crawl the website using the original
+method. Validity checking happens at random on certain event entries.
An event entry usually contains one occurrence of an event. In a lot of cases
there is parent information that the event entry is part of. For example in the
data flow that require the most amount of resources. Both of these parts require
a programmer to execute and therefore are costly. In the case of the automated
crawlers it requires a programmer because the crawlers are scripts or programs
-created are website-specific. Changing such a script or program requires
-knowledge about the source, the programming framework and about the
-\textit{Temporum}. In practice both of the tasks mean changing code.
+are specifically designed for a particular website. Changing such a script or
+program requires knowledge about the source, the programming framework and
+about the \textit{Temporum}. In practice both of the tasks mean changing code.
-A large group of sources often changes in structure. Because of such changes
+A large group of sources often change in structure. Because of such changes
the task of reprogramming crawlers has to be repeated a lot. The detection of
malfunctioning crawlers happens in the \textit{Temporum} and not in an earlier
stage. Late detection elongates the feedback loop because there is not always a
for gaps and faulty information in the database. The figure shows information
flow with arrows. The solid and dotted lines form the current feedback loop.
\begin{figure}[H]
-\label{feedbackloop}
\centering
\includegraphics[width=0.8\linewidth]{feedbackloop.pdf}
- \caption{Feedback loop for malfunctioning crawlers}
+ \caption{Feedback loop for malfunctioning crawlers\label{feedbackloop}}
\end{figure}
The specific goal of this project is to relieve the programmer of spending a
information extraction be automated using the structural information which is a
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 useful
-because the crawlers then do not have to be retrained very often. To detect
-the underlying structures a technique is used that exploits subword matching
-with graphs.
+processing and possibly OCR. 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 useful because the crawlers then do not
+have to be retrained very often. To detect the underlying structures a
+technique is used that exploits subword matching with graphs.
\section{Directed Acyclic Graphs}
\paragraph{Directed graphs}
$$G=(\{n1, n2, n3, n4\}, \{(n1, n2), (n2, n1), (n2, n3), (n3, n4), (n1, n4)\}$$
\begin{figure}[H]
- \label{graphexample}
\centering
\includegraphics[scale=0.7]{graphexample.pdf}
- \caption{Example DG}
+ \caption{Example DG\label{graphexample}}
\end{figure}
\paragraph{Directed acyclic graphs}
the graph to $\mathcal{O}(L)$ where $L$ is the length of the path.
\begin{figure}[H]
- \label{dagexample}
\centering
\includegraphics[scale=0.7]{dagexample.pdf}
- \caption{Example DAG}
+ \caption{Example DAG\label{dagexample}}
\end{figure}
+\newpage
\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 tuple $G=(V,v_0,E,F)$.
because $n6$ is a final node anyways because there are no arrows leading out.
But this does not need to be the case, 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. Finally $v_0$ describes the initial node, this is
-visualized in figures as an incoming arrow. Because of the property of labeled
-edges, data can be stored in a DAWG. When traversing a DAWG and saving all the
-edge labels one can construct words. Using graph minimisation big sets of
-words can be stored using a small amount of storage because edges can be
-re-used to specify transitions. For example the graph in
-Figure~\ref{exampledawg} can describe the language $L$ where all words $w$ that
-are accepted $w\in\{abd, bad, bae\}$. Testing if a word is present in the DAWG
-is the same technique as testing if a node path is present in a normal DAG and
-therefore also falls in the computational complexity class of $\mathcal{O}(L)$.
-This means that it grows linearly with the length of the word.
+marking. The only final node is the example is $n_6$, marked with a
+double circle. $v_0$ describes the initial node, this is visualized in figures
+as an incoming arrow. Because of the property of labeled edges, data can be
+stored in a DAWG. When traversing a DAWG and saving all the edge labels one can
+construct words. Using graph minimisation big sets of words can be stored using
+a small amount of storage because edges can be re-used to specify transitions.
+For example the graph in Figure~\ref{exampledawg} can describe the language $L$
+where all words $w$ that are accepted $w\in\{abd, bad, bae\}$. Testing if a
+word is present in the DAWG is the same technique as testing if a node path is
+present in a normal DAG and therefore also falls in the computational
+complexity class of $\mathcal{O}(L)$. This means that it grows linearly with
+the length of the word.
\begin{figure}[H]
- \label{exampledawg}
\centering
\includegraphics[scale=0.7]{dawgexample.pdf}
- \caption{Example DAWG}
+ \caption{Example DAWG\label{exampledawg}}
\end{figure}
+
+\section{Structure}
+The following chapters will describe the system that has been created and the
+used methods. Chapter~2 shows the requirements design for the program followed
+in Chapter~3 by the underlying methods used for the actual matching. Finally
+Chapter~4 concludes with the results, discussion and future research.
repositories / bsc-thesis1415.git / blobdiff