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}

\newpage
\thispagestyle{empty}
\mbox{}
\newpage

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

\section*{Sammanfattning}
Reguljära uttryck (Regular Expressions) är uttryck som innehåller
olika syntax för att identifiera specifika textsträngar ur en större
mängd text. Detta kan användas inom ämnet Artificiell Intelligens för
att till exempel validera och tolka indata och specificera olika typer
av språk.

\newpage
\tableofcontents
\newpage

\rfoot{\thepage}
\pagenumbering{arabic}

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

\section{Introduktion}
% till ämnet.
Denna rapport går igenom användandet av Reguljära uttryck (Regular
Expressions på engelska, även förkortat som ''regexp'' eller bara
''regex'') med avseende på informationshämtning inom området
Artificiell Intelligens.

Rapporten är formulerad och utförd enligt specifikation på sidan:\\
\begin{footnotesize}
  \verb!http://www.cs.umu.se/kurser/5DV063/HT08/assignments/lab3-spes-ht08.html!
\end{footnotesize}

\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
Denna rapport är sammanställd främst genom en litteraturstudie inom
området Artificiell Intelligens i förhållande till Reguljära uttryck.
Information och tankar är samlade från böcker och internetsidor, för
att försöka få en överblick över de Reguljära uttryckens betydelse och
användande inom området.

\section{Litteraturstudie}
%, teoretisk fördjupning
Enligt \cite{speech} härstammar Reguljära uttryck från Alan Turings
modell (1936) för aritmetisk beräkning, även kallad
Turingmaskin. Denna maskin var abstrakt, ett tankeexperiment, 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 deras
likhet.

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

I \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 \textbf{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
\textbf{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}

Ovanstående tabell läses 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 \textbf{Reguljära uttrycket} för att beskriva
''ko-språk'' skulle vara:

\begin{verbatim}
Muu+!
\end{verbatim}

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.

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 (från A till Z), understreck, punkt, procenttecken,
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{footnotesize}
    \begin{tabular}{|c|p{4cm}|l|l|l|}
      \hline
      \textbf{regex-uttryck} & \textbf{Texthändelse} & \textbf{Exempel} & \textbf{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 A till Z, a
      till z och 0 till 9. & \verb![abc0-9]! & ''\textbf{b}r\textbf{a} text med \textbf{23} te\textbf{c}ken'' \\
      
      \hline
      
      \verb!.! (punkt) & Står för vilket tecken som helst. & \verb!^.! & ''\textbf{t}ext'' \\ \hline
    \end{tabular}
  \end{footnotesize}
\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, dvs. 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.

Låt oss definiera en teckenklass med alla siffror, dvs
''\verb![0-9]!'' och använda det i ett reguljärt uttryck, till exempel
''\verb!\b$[0-9]!''. Om vi sedan försöker matcha strängen ''\$10000''
med det mönstret kommer vi endast matcha följande (fet stil)
''\textbf{\$1}0000''. Detta beror på att teckenklassen vi definierat
matchar bara \textit{det första} tecknet som platsar i
klassen. Självklart skulle vi vilja kunna matcha flera tecken i en och
samma teckenklass utan att behöva definiera en likadan klass för hela
det antalet tecken vi vill matcha. Därför har man definierat något som
kallas kvantifierare som gör att man kan bestämma hur många gånger man
vill matcha en specifik klass, ett mönster eller bara ett tecken (så
kallade ''tokens''). Nedanstående tabell beskriver olika
kvantifierare.

\begin{center}
  \begin{footnotesize}
    \begin{tabular}{|c|p{4cm}|l|p{4cm}|}
      \hline
      \textbf{kvantifierare} & \textbf{Beskrivning} & \textbf{Exempel} & \textbf{Matchar} \\ \hline

      \verb!?! & Matchar föregående uttryck noll eller en gång. &
        colou\verb!?!r & ''\textbf{colour}'' och ''\textbf{color}'' \\ \hline

      \verb!+! & Matchar föregående uttryck en eller fler gånger. &
        Mu\verb:+:! & ''\textbf{Mu!}'', ''\textbf{Muu!}'',
        ''\textbf{Muuu!}'', \ldots \\ \hline 

      \verb!*! & Matchar föregående uttryck noll eller flera gånger &
        10\verb!*! & ''\textbf{1}'', ''\textbf{10}'', ''\textbf{100}'',
        \ldots \\ \hline

      \verb!{!$n$\verb!,!$m$\verb!}! & Matchar föregående uttryck
        minst $n$ gånger och som mest $m$ gånger. &
        \verb!^!1\verb![!0\verb!]{!1,5\verb!}! & ''\textbf{10}'',
        ''\textbf{100}'', ''\textbf{1000}'', ''\textbf{10000}'' och
        ''\textbf{100000}'' men inte ''1'' och inte ''1000000'' (6
        nollor eller mer).\\ \hline
    \end{tabular}
  \end{footnotesize}
\end{center}

Nu kan vi beskriva många olika variationer av mönster genom olika
texthändelser och kvantifierare, men vad händer om man vill inkludera
till exempel ett frågetecken i sitt mönster? Då måste man ''komma
runt'' (escape) frågetecknets regexp-betydelse för att komma åt dess
textuella värde. Detta görs vanligtvis med bakåtvänt snedstreck
(\textbackslash). Till exempel måste vi i vårt e-post\-adress\-mönster
matcha en punkt (i domännamnet), som vi måste uttrycka som
''\verb!\.!''.

Nu har vi tillräckligt stor kunskap för att uttrycka ett reguljärt
uttryck som matchar en generell e-post\-adress. Vi börjar med att
beskriva \verb!<användarnamn>!. Användarnamnet kunde som sagt var
innehålla små och stora bokstäver (från A till Z), siffror, punkt,
understreck, procenttecken, plustecken och bindestreck. Vi uttrycker
detta som

\begin{verbatim}
\b[A-Za-z0-9._%+-]+
\end{verbatim}

där det sista plustecknet som sagt innebär att alla de tecken som den
definierade tecken\-klassen innefattar måste matchas minst en
gång. Plustecknet inom tecken\-klass\-definitionen tolkas som ett
''textplus'' och inte som ett ''regex-plus''. Vi lägger också till
ordavgränsare som gör att uttrycket bara matchar användarnamnet i
början av ett nytt ord (dvs. själva e-post\-adressen) och inte matchar
ett användarnamn när det kommer direkt efter ett icke tillåtet
användarnamnstecken. Hade vi glömt ordavgränsaren hade följade
användarnamn matchats:
\\ ''\copyright\&\texttrademark\textexclamdown\textbf{sven.svensson}@host.doman''
vilket vi inte vill eftersom de icke tillåtna tecknen inte bör finnas
före användarnamnet.

Vi uttrycker sedan domännamnet som

\begin{verbatim}
[A-Za-z0-9.-]+\.[A-Za-z]{2,4}\b
\end{verbatim}

där plustecknet betyder precis samma sak som i uttrycket för
användarnamnet och ''\verb!\.!'' står för punktens textuella
värde. Sedan finns det ett krav på det som står efter punkten i
domännamnet, nämligen att denna ''token'' måste bestå av minst 2 och
som mest 4 tecken, därav kvantifieraren \verb!{!2\verb!,!4\verb!}!.
\verb!\b! i slutet av uttrycket innebär att det måste finnas en
ordavgränsare efter domännamnet.

Sätter vi nu samman dessa uttryck med ett snabel-a i mitten får vi ett
uttryck för en generell e-post\-adress \textbf{i löptext}. Vill vi
definiera ett uttryck för att undersöka om totala textmängden består
av endast en e-post\-adress kan vi ersätta \verb!\b! i början med
\verb!^! och i slutet med \verb!$! (till exempel om vi vill
kontrollera ett formulärfält på en webbsida)
\cite{regexinfo:website}. De två olika uttrycken ser ut som följer:

\begin{verbatim}
\b[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,4}\b
\end{verbatim}

och

\begin{verbatim}
^[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,4}$
\end{verbatim}

% 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}$
% http://www.regular-expressions.info/email.html

\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.
\subsection{Applikationer av Reguljära uttryck}
Följande sektioner berör olika användningsområden för Reguljära
uttryck inom Artificiell intelligens.

\subsubsection{ELIZA}
Mer avancerade former av Reguljära uttryck kan använda sig av
minnesfunktioner för att spara tidigare matchningar. I
programmeringssråket Perl kan man göra ersättningar på formen:
\begin{verbatim}
s/hej/hejsan/
\end{verbatim}

Här ersätts alla \verb!hej! med \verb!hejsan!. För att spara träffar i
sökningen och ersätta med samma ord i ersättningssträngen använder man
grupper inom parenteser \verb!()!. Den sträng som en grupp matchar kan
sedan refereras till. \verb!\1!, till exempel, representerar
innehållet i första gruppen.

\begin{verbatim}
s/jag heter (\w+)/på dig \1, trevligt att höras/
\end{verbatim}

Ovanstående Reguljärt uttryck skulle ersätta ''Hej jag heter Anton''
med ''Hej på dig Anton, trevligt att höras''. Denna typ av Reguljära
ersättningar utgör grunden för implementationen av Chatroboten ELIZA,
som utvecklades av Joseph Weizenbaum, se \cite{speech}. Här följer en
kort konversation med Emacs implementering av ELIZA:

\begin{itemize}
\item[-] Hello my name is Anton
\item[-] \textbf{ELIZA:} How do you do?  What brings you to see me?
\item[-] I need help with some Artificial Intelligence questions
\item[-] \textbf{ELIZA:} Why do you say you need help with some
  artificial intelligence questions?
\item[-] I'm writing an essay about Regular Expressions
\item[-] \textbf{ELIZA:} Is it because of your plans that you say you
  are writing an essay about regular expressions?
\item[-] yes
\item[-] \textbf{ELIZA:} I see...  Well, what makes you believe this is so?
\end{itemize}

Ovanstående exempel vittar om att denna typ av chatrobot har en
relativt fast ram med frågor och svar att följa. Det tar inte lång tid
för en mänsklig användare att förstå att det inte är en mänsklig
motpart man kommunicerar med. ELIZA är implementerad för att svara på
frågor som rör psykoterapi--så fort man lämnar det bekanta ämnet blir
följdfrågorna ologiska ur ett mänskligt perspektiv.

Emacs implementation av ELIZA har en mängd hårdkodade svar. Följande
kodsnutt visar svaren som kan fås av indata som innehåller vissa
nyckelord gällade död:

\begin{footnotesize}
\begin{verbatim}
(setq deathlst
        '((this is not a healthy way of thinking \.)
          ((doc$ bother) you\, too\, may die someday \?)
          (i am worried by your obsession with this topic!)
          (did you watch a lot of crime and violence on television as a child \?))
        )
\end{verbatim}
\end{footnotesize}

Även mängder med vanliga ord sparas för att på ett bättre sätt kunna
tolka indata, exempelvis vanliga synonymer, pronomen, verb och förkortningar:

\begin{footnotesize}
\begin{verbatim}
(setq replist
  (wanna . (want to))
  (gimme . (give me))
  (gotta . (have to))
  (gonna . (going to))
  (never . (not ever))
  ...)
\end{verbatim}
\end{footnotesize}

\subsubsection{Tolkning av indata}
Det finns en mängd användbara Reguljära uttryck för att tolka och på
ett vettigt sätt behandla indata som ett datorsystem får från
användare. Det kan gälla exempelvis verifiering av e-postadresser,
datum, person- och telefonnummer och så vidare. Detta är användbart
vid all typ av indata från användare, och i hög grad aktuellt när det
gäller forumlär på Internet.

Till exempel kan man istället för att kräva att användare ska skriva
för- och efternamn i separata rutor använda Reguljära uttryck för att
försöka tolka vad som är vad. Samma sak gäller adresser och
telefonnummer. Det kan vara intressant att ha information och ett
telefonnummers riktnummer och landskod, utan att för den sakens skull
kräva att en användare ska behöva specificera allt sådant manuellt.
Följer man bara vanliga konventioner för hur telefonnummer skrivs kan
man skapa ett Reguljärt uttryck för att fånga upp all denna
information ur en enda textsträng. All sådan här tolkning av indata är
väldigt bra ur användarsynpunkt, ''Don't make me click'', som Aza
Raskin \cite{raskin:website} säger i en presentation om
användarvänlighet på webbsidor.

%@TODO fixa url löpande
Ett annat bra exempel på hur Reguljära uttryck kan underlätta
inmatning av data finns implementerat i den webbaserade
kalendertjänsten från Google Inc. (\begin{footnotesize}
http://google.com/calendar/\end{footnotesize}). För att skapa en ny
händelse i kalendern kan användaren klicka på aktuell dag och skriva
till exempel ''Äta mat hos mamma kl 10-12''. Detta genererar en
händelse med rubrik ''Äta mat hos mamma'' och placeras med start kl 10
och slut kl 12 i kalendern. Ett Reguljärt uttryck för detta skulle
kunna vara att matcha de första siffrorna efter \verb!(kl|klockan)!,
dessa borde vara starttimme för händelsen. Följs dessa siffror av
\verb!.! eller \verb!:! utan mellanslag efter skulle nästa två siffror
kunna representera minuter, nästa siffror, eventuellt efter ett
bindestreck, kan representera sluttid. På detta sätt kan man med hjälp
av Reguljära uttryck representera naturligt språk för datorn. Vidare
skulle extra nyckelord kunna läggas in, till exempel \verb!hos!,
\verb!på! eller \verb!i! för att markera att det som följer är en
plats, eller \verb!med! för att markera att följande text innehåller
information om deltagare i händelsen.

\subsubsection{Datahämtning}
Reguljära uttryck kan användas för att hämta och tolka information ur
en större mängd data. Ett trivialt exempel är till exempel att försöka
svara på frågan, ''Vad är det för väder i Umeå idag?'' baserat på
innehållet från sidan:

\begin{verbatim}
http://www.tfe.umu.se/weather/1440/900/10/sv-SE/now.htm
\end{verbatim}

Html-taggen som visar den aktuella temperaturen i Umeå har följande
utseende:
\begin{verbatim}
<td class="tempfont" ... >0,7 &deg;C</td>
\end{verbatim}

Det som skiljer denna tagg från de andra på sidan är attributet
\verb!class="tempfont"!. Den aktuella temperaturen visas mellan
\verb!<td ...>! och \verb!</td>!, det innebär att det i detta exempel
skulle vara $0,7\,^{\circ}\mathrm{C}$ dagen sidan hämtades. Följande
Reguljära uttryck matchar den strängen som innehåller temperatur i sin
första grupp, dvs uttrycket inom \verb!()!, som senare kan refereras
till med \verb!\1!:

\begin{verbatim}
<td class="tempfont.+?>([0-9]+,[0-9]+)
\end{verbatim}

Med denna information kan man sedan förenkla och säga att bra väder
gäller för alla $temperaturer \geq 15$ och dåligt väder gäller för
$temperaturer < 15$. Detta Reguljära uttryck är mycket specifikt och
enbart användbart på denna specifika sida så länge temperaturen
inkapslas exakt av den HTML-taggen och eventuella attribut.

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

\section{Slutsats}
%.

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

\end{document}