Some change

[ailab3.git] / rapport.tex

\documentclass[titlepage, twoside, 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}

\thispagestyle{empty}
\cleardoublepage

\pagestyle{fancy}
\rhead{\footnotesize{\today}}
\lhead{\footnotesize{\namn, \mail \\ \namnett, \mailett}}
\chead{}
\lfoot{}
\cfoot{}
\rfoot{}
\fancyfoot[LE,RO]{\thepage}

\begin{abstract}
%TODO section
Reguljära uttryck (Regular Expressions) är uttryck som innehåller
olika syntax för att identifiera, eller ''matcha'', specifika
textsträngar ur en större mängd text. Det finns många olika
användningsområden för reguljära uttryck inom området Artificiell
Intelligens, till exempel att hämta data från dokument på Internet och
tolka det utifrån någon preferens; ''Sök (och ersätt)''-funktioner i
ordbehandlare och textredigerare; och tolkning och validering av data,
till exempel datum-, telefon-, och personnummerinmatning i
webbformulär.
\end{abstract}

\thispagestyle{empty}
\cleardoublepage

\thispagestyle{empty}
\tableofcontents
\newpage

\thispagestyle{empty}
\cleardoublepage

\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.
% TODO
Syftet med rapporten är att undersöka hur reguljära uttryck fungerar,
och hur kan de kan användas inom ämnet Artificiell Intelligens.

\section{Metodbeskrivning}
%: beskrivning av metod, material, design och procedur
Denna rapport är sammanställd främst genom en litteratur\-studie inom
om\-rå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 om\-rådet.

\section{Bakgrund}
%, teoretisk fördjupning, f d Litteraturstudie
Enligt Jurafski \emph{et al.} \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) och 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 \emph{reguljära språk}, (Regular Language).

I \cite{speech} av Jurafski \emph{et al.} 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 \emph{Finite-state
  automation} (ändlig automat) enligt Figur~\ref{fig:finauto}.

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

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

Denna information går även att representera som en
\emph{State-transition-tabell}, som i Tabell~\ref{tab:statetranstable}.

\begin{table}[h]
  \centering
  \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}
  \caption{State-transition-tabell för ''ko-språk''.}
  \label{tab:statetranstable}
\end{table}

State-transistion-tabeller läses uppifrån och ner. Starttillståndet 0
har en giltig förflyttning till tillstånd 1, detta gäller
enbart för indata M, för alla andra indata finns inga giltiga
förflyttningar, detta markeras med 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 leder till sluttillståndet i exemplet.
% 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. I
Tabell~\ref{tab:texthandelser} visas en kort tabell med några
texthändelser och deras motsvarande reguljära uttryck.

\begin{table}[h]
  \centering
  \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}
  \caption{Texthändelser och deras motsvarande reguljära uttryck.}
  \label{tab:texthandelser}
\end{table}

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''). Tabell \ref{tab:kvantifs} beskriver olika
kvantifierare.

\begin{table}[h]
  \centering
  \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}
  \caption{Reguljära kvantifierare, deras funktion och exempel på vad som matchas.}
  \label{tab:kvantifs}
\end{table}

Nu kan vi beskriva många olika variationer av mönster genom olika
text\-hä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 segmentet \linebreak\verb!<användarnamn>!. Användar\-namnet
kunde som sagt var innehålla små och stora bokstäver (från A till Z),
siffror, punkt, under\-streck, procent\-tecken, plus\-tecken och
binde\-streck. 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ändar\-namnet 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.
Följande avsnitt berör olika applikationer av reguljära uttryck inom
ämnet 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 säger i en presentation om användarvänlighet på webbsidor
\cite{raskin:website}.

%@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} \label{datah}
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\linebreak
\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.
Reguljära uttryck har visat sig vara ett mycket användbart verktyg vid
hämtning och tolkning av data ur text, dock kan det bli väldigt
beräknings\-tungt om man använder sig av de mer komplicerade former av
Reguljära uttryck där man sparar undan grupper av träffar i
minnet. Den simplaste formen av Reguljära uttryck har en komplexitet
på $O(n)$ där $n$ är antalet tecken i texten där ett mönster söks.
Dessa typer av Reguljära uttryck kan implementeras med en
''State-transition-tabell'', se sid \pageref{tab:statetranstable}. Vid
användande av mer avancerade Reguljära uttryck kan körningstiden öka
exponentiellt i förhållande till textmängden som ska sökas igenom.

För analys av data i XML-format som i sektionen om Datahämtning
\textbf{\ref{datah}} finns lämpade metoder såsom XQuery, Expat och
SAX.

\section{Slutsats}
Reguljära uttryck har visat sig vara mycket användbara inom vitt
spridda användningsområden. Användningsområdena som tagits upp i denna
rapport är enbart ett litet urval av de omfattande möjligheter som
Reguljära uttryck erbjuder. Vare sig man har använder sig av Reguljära
uttryck för att manipulera text direkt i en textredigerare eller om
man bygger in uttrycken i olika typer av applikationer och system så
erbjuder de Reguljära uttrycken nästintill oändliga möjligheter för
analys av text.

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

\end{document}