Merge commit 'origin'

[ailab3.git] / rapport.tex

\documentclass[a4paper, 12pt]{article}
\usepackage[swedish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{verbatim}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{parskip}
% Include pdf with multiple pages ex \includepdf[pages=-, nup=2x2]{filename.pdf}
\usepackage[final]{pdfpages}
% Place figures where they should be
\usepackage{float}

% vars
\def\title{Projekt}
\def\preTitle{Laboration 3: Information Retrieval \& Extraction}
\def\kurs{Artificiell Intelligens med inriktning mot kognition och
  design B, ht 2008}

\def\namn{Anton Johansson}
\def\mail{dit06ajn@cs.umu.se}
\def\namnett{Victor Zamanian}
\def\mailett{dit06vzy@cs.umu.se}

\def\handledareEtt{Dennis Olsson, denniso@cs.umu.se}
\def\inst{datavetenskap}
\def\dokumentTyp{Laborationsrapport}

\begin{document}
\begin{titlepage}
  \thispagestyle{empty}
  \begin{small}
    \begin{tabular}{@{}p{\textwidth}@{}}
      UMEÅ UNIVERSITET \hfill \today \\
      Institutionen för \inst \\
      \dokumentTyp \\
    \end{tabular}
  \end{small}
  \vspace{10mm}
  \begin{center}
    \LARGE{\preTitle} \\
    \huge{\textbf{\kurs}} \\
    \vspace{10mm}
    \LARGE{\title} \\
    \vspace{15mm}
    \begin{large}
      \namn, \mail \\
      \namnett, \mailett
    \end{large}
    \vfill
    \large{\textbf{Handledare}}\\
    \mbox{\large{\handledareEtt}}
  \end{center}
\end{titlepage}

\pagestyle{fancy}
\rhead{\footnotesize{\today}}
\lhead{\footnotesize{\namn, \mail \\ \namnett, \mailett}}
\chead{}
\lfoot{}
\cfoot{}
\rfoot{}

\section*{Sammanfattning}
Denna rapport går igenom olika verktyg för ''Data-mining''. Regexp,
XPath ...?

Labbspecifikation finns att läsa på:\\
\verb!http://www.cs.umu.se/kurser/5DV063/HT08/lab3.html!

\newpage
\tableofcontents
\newpage

\rfoot{\thepage}
\pagenumbering{arabic}

% TODO @anton - Problem-solving as search, basic to AI, Norvig.

\section{Introduktion}
% till ämnet.
Reguljära uttryck (Regular Expressions, regexp eller regex) är uttryck
som innehåller olika syntax för att identifiera specifika textsträngar
ur en större mängd text.

\section{Syfte}
% med uppgiften, beskrivet med egna ord.
Syftet med rapporten är att fördjupa sig inom ett smalt ämne inom
området Artificiell Intelligens och presentera teori för det valda
ämnet på ett vetenskapligt sätt.

\section{Metodbeskrivning}
%: beskrivning av metod, material, design och procedur

\section{Litteraturstudie}
%, teoretisk fördjupning
Enligt \cite{speech} härstammar Reguljära uttryck från Alan Turings (1936)
modell för aritmetisk beräkning, även kallad Turingmaskin. Denna
maskin var abstrakt, ett tanke experiment, för att utföra beräkningar.
% TODO Church-Turings hypotes säger att varje tänkbar process kan
% utföras av en Turingmaskin, och alltså finns det rent principiellt
% inte någon mer kraftfull beräkningsmekanism. Enligt wikipedia
% http://sv.wikipedia.org/wiki/Turingmaskin

Inspirerad av Turings arbete skapade sedan Warren McCulloch och Walter
Pitts (1943) en förenklad modell för neuronen, se \cite{norvig}
kapitel 18.

Stephen Cole Kleene definierade sedan (1951 och 1956) Ändlig
automation (Finite automation), Reguljära uttryck och påvisade dess
likhet.

Både Reguljära uttryck och Finite automation är en del av det en
språktyp som brukar kallas Reguljära språk, (''Regular Language'').

I boken \cite{speech} ger man ett exempel på hur Finite automation och
Reguljära uttryck förhåller sig till varandra. Säg att man ska
definiera ett naturligt språk, för enkelhets skull försöker vi
definiera vad som är ''ko-språk''. Vi kan säga att korrekt
''ko-språk'' definieras av kombinationerna:

\begin{verbatim}
Muu!
Muuu!
Muuuu!
...
\end{verbatim}

Detta skulle kunna beskrivas med en modell för Finite-state automation
enligt figur nedan.

\begin{figure}[H]
  \begin{center}
    \includegraphics[width=110mm]{images/state.pdf}
    \caption{Ändlig automation för ''ko-språk''}
    \label{state.pdf}
  \end{center}
\end{figure}

Tillstånden \verb!q0-q4! är de giltiga tillstånd som finns, \verb!q1! är
starttillståndet och \verb!q4! representerar sluttillstånd. Pilarna i figuren
markerar möjliga förflyttningar mellan tillstånden.

Denna information går även att representera som en ''State-transition''
tabell, se nedan:

\begin{center}
  \begin{tabular}{|c|l|l|l|}
    \hline
    & \multicolumn{3}{|c|}{Indata} \\
    \hline
    Tillstånd & M & u & ! \\
    \hline
    0  & 1 & 0 & 0 \\
    1  & 0 & 2 & 0 \\
    2  & 0 & 3 & 0 \\
    3  & 0 & 3 & 4 \\
    4  & 0 & 0 & 0 \\
    \hline
  \end{tabular}
\end{center}

Ovan tabell läses av uppifrån och ner. Starttillståndet \verb!0! har
en giltig förflyttning till tillstånd \verb!1!, detta gäller enbart
för indata \verb!M!, för alla andra indata finns inga giltiga
förflyttningar, detta markeras med \verb!0!.

Det korresponderande reguljära uttrycket för att beskriva ''ko-språk''
skulle vara \verb?/Muu+!/?. Det Reguljära uttrycket är allt som står
inom \verb!/!-tecknen. Man läser det som man läser det ungefär som man
läser vanlig text. \verb!M! är tillåtet starttillstånd, följt av ett
\verb!u!, sedan markerar operatorn \verb!u+! att en eller flera
\verb!u! är tillåtna. Meningen avslutas med \verb?!?, vilket markerar
sluttillståndet. % Se sektion TODO för mer info om regexp syntax.

% REGEXP-MANUAL:
% Står på sidan 848 i Norvig.
% TODO @anton/victor - beskrivning regexp manual med fina tabeller.

Ett reguljärt uttryck består enkelt nog av text som ska matchas. Om
man vill matcha texten ''hej'' i en textsträng ''hoppsanhejsan'' så
blir det reguljära uttrycket helt enkelt bara ''hej'' och ''hej'':et i
''hoppsanhejsan'' matchas. Däremot är det mer sällan man använder
reguljära uttryck för sådana enkla matchningar. Man vill i stället
använda dem till att matcha \textbf{generella mönster}. Ett exempel på
ett mönster skulle kunna vara en e-postadress på formen
\verb!<användarnamn>@<subdomän>.<domän>!, där \verb!<användarnamn>!
kan innehålla (i detta exempel) alla siffror, alla små och stora
bokstäver, understreck, punkt, bindestreck och plus.

I stället för att behöva skriva ett textmönster för varje e-postadress
som är möjlig att konstruera (i praktiken oräkneligt antal
variationer) kan man använda sig av speciella ''texthändelser'' för
att beskriva till exempel början\slash slutet av ett ord och
början\slash slutet av en hel sträng. Man kan också definiera
teckenklasser som man vill inkludera i sitt uttryck, till exempel alla
stora bokstäver, alla små bokstäver, siffror, eller till och med
vilken godtycklig kombination av tecken som helst. Här nedanför visas
en kort tabell med några texthändelser och deras motsvarande reguljära
uttryck.

\begin{center}
  \begin{tabular}{|c|l|l|l|l|}
    \hline
    regex-uttryck & Texthändelse & Exempel & Matchar
    \\ \hline
    \verb!\b! & Början eller slutet på ett ord & \verb!\b!text\verb!\b! & ''ord1 \textbf{text} ord3'' \\ \hline

    \

    \verb!^! & Början av en textsträng & \verb!^!text & ''\textbf{text} i början'' \\ \hline

    \verb!$! & Slutet av en textsträng & \verb!lutet$! & ''text i s\textbf{lutet}'' \\ \hline

    \verb![A-Za-z0-9]! & Definierar klass med tecknen & \verb![abc0-9]! & ''\textbf{b}r\textbf{a} text med \textbf{23} te\textbf{c}ken'' \\
    & A till Z, a till z och 0 till 9. & & \\ \hline

    \verb!.! & Står för vilket tecken som helst. & \verb!^.! & ''\textbf{t}ext'' \\ \hline
  \end{tabular}
\end{center}

Om man vill matcha en e-postadress i löpande text skulle man alltså
vilja använda sig av \verb!\b! runt uttrycket för att markera att det
som finns runt omkring adressen måste vara ordavgränsare av något
slag, så som ny rad eller någon typ av blanktecken. Vill man däremot
kontrollera indata från till exempel ett formulärfält där det är
meningen att en användare ska ange enbart en e-postadress är det
däremot önskvärt att omsluta uttrycket med \verb!^! i början och
\verb!$! i slutet för att markera att hela strängen måste
\textbf{börja och sluta med} adressen.

% Olika sätt att matcha e-mail adresser.
% \b[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,4}\b
% ^[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,4}$

\section{Resultat}
% innehållande sammanställning/analys av eventuell testdata,
% implementering av algoritmer osv.
% TODO - resultat, användningsområden kopplade till AI.
% TODO @anton - Kolla upp och skriv om ELIZA, regexp memory.
% TODO - resultat, ska innehålla typ ELIZA.


\section{Diskussion}
% av resultatet, koppling till tidigare studier.

\section{Slutsats}
%.

%. Använd minst två referenser utöver kursboken.
\bibliographystyle{alpha}
\bibliography{books}

\end{document}