1 \documentclass[a4paper,
12pt
]{article
}
2 \usepackage[swedish
]{babel
}
3 \usepackage[utf8
]{inputenc}
8 % Include pdf with multiple pages ex \includepdf[pages=-, nup=2x2]{filename.pdf}
9 \usepackage[final
]{pdfpages
}
10 % Place figures where they should be
15 \def\preTitle{Laboration
3: Information Retrieval \& Extraction
}
16 \def\kurs{Artificiell Intelligens med inriktning mot kognition och
19 \def\namn{Anton Johansson
}
20 \def\mail{dit06ajn@cs.umu.se
}
21 \def\namnett{Victor Zamanian
}
22 \def\mailett{dit06vzy@cs.umu.se
}
24 \def\handledareEtt{Dennis Olsson, denniso@cs.umu.se
}
25 \def\inst{datavetenskap
}
26 \def\dokumentTyp{Laborationsrapport
}
32 \begin{tabular
}{@
{}p
{\textwidth}@
{}}
33 UMEÅ UNIVERSITET
\hfill \today \\
34 Institutionen för
\inst \\
41 \huge{\textbf{\kurs}} \\
50 \large{\textbf{Handledare
}}\\
51 \mbox{\large{\handledareEtt}}
61 \rhead{\footnotesize{\today}}
62 \lhead{\footnotesize{\namn,
\mail \\
\namnett,
\mailett}}
68 \section*
{Sammanfattning
}
69 Denna rapport går igenom olika verktyg för ''Data-mining''. Regexp,
72 Labbspecifikation finns att läsa på:\\
73 \verb!http://www.cs.umu.se/kurser/
5DV063/HT08/lab3.html!
80 \pagenumbering{arabic
}
82 % TODO @anton - Problem-solving as search, basic to AI, Norvig.
84 \section{Introduktion
}
86 Reguljära uttryck (Regular Expressions, regexp eller regex) är uttryck
87 som innehåller olika syntax för att identifiera specifika textsträngar
88 ur en större mängd text.
91 % med uppgiften, beskrivet med egna ord.
92 Syftet med rapporten är att fördjupa sig inom ett smalt ämne inom
93 området Artificiell Intelligens och presentera teori för det valda
94 ämnet på ett vetenskapligt sätt.
96 \section{Metodbeskrivning
}
97 %: beskrivning av metod, material, design och procedur
99 \section{Litteraturstudie
}
100 %, teoretisk fördjupning
101 Enligt
\cite{speech
} härstammar Reguljära uttryck från Alan Turings
102 (
1936) modell för aritmetisk beräkning, även kallad
103 Turingmaskin. Denna maskin var abstrakt, ett tanke experiment, för att
105 % TODO Church-Turings hypotes säger att varje tänkbar process kan
106 % utföras av en Turingmaskin, och alltså finns det rent principiellt
107 % inte någon mer kraftfull beräkningsmekanism. Enligt wikipedia
108 % http://sv.wikipedia.org/wiki/Turingmaskin
110 Inspirerad av Turings arbete skapade sedan Warren McCulloch och Walter
111 Pitts (
1943) en förenklad modell för neuronen, se
\cite{norvig
}
114 Stephen Cole Kleene definierade sedan (
1951 och
1956) Ändlig
115 automation (Finite automation), Reguljära uttryck och påvisade dess
118 Både Reguljära uttryck och Finite automation är en del av det en
119 språktyp som brukar kallas Reguljära språk, (''Regular Language'').
121 I boken
\cite{speech
} ger man ett exempel på hur Finite automation och
122 Reguljära uttryck förhåller sig till varandra. Säg att man ska
123 definiera ett naturligt språk, för enkelhets skull försöker vi
124 definiera vad som är ''ko-språk''. Vi kan säga att korrekt
125 ''ko-språk'' definieras av kombinationerna:
134 Detta skulle kunna beskrivas med en modell för
\textbf{Finite-state
135 automation
} enligt figur nedan.
139 \includegraphics[width=
110mm
]{images/state.pdf
}
140 \caption{Ändlig automation för ''ko-språk''
}
145 Tillstånden
\verb!q0-q4! är de giltiga tillstånd som finns,
\verb!q1!
146 är starttillståndet och
\verb!q4! representerar sluttillstånd. Pilarna
147 i figuren markerar möjliga förflyttningar mellan tillstånden.
149 Denna information går även att representera som en
150 \textbf{State-transition tabell
}, se nedan:
153 \begin{tabular
}{|c|l|l|l|
}
155 &
\multicolumn{3}{|c|
}{Indata
} \\
157 Tillstånd & M & u & ! \\
168 Ovan tabell läses av uppifrån och ner. Starttillståndet
\verb!
0! har
169 en giltig förflyttning till tillstånd
\verb!
1!, detta gäller enbart
170 för indata
\verb!M!, för alla andra indata finns inga giltiga
171 förflyttningar, detta markeras med
\verb!
0!.
173 Det korresponderande
\textbf{Reguljära uttrycket
} för att beskriva
174 ''ko-språk'' skulle vara:
180 Det Reguljära uttrycket är allt som står inom
\verb!/!-tecknen. Man
181 läser det som man läser det ungefär som man läser vanlig
182 text.
\verb!M! är tillåtet starttillstånd, följt av ett
\verb!u!,
183 sedan markerar operatorn
\verb!u+! att en eller flera
\verb!u! är
184 tillåtna. Meningen avslutas med
\verb?!?, vilket markerar
185 sluttillståndet.
% Se sektion TODO för mer info om regexp syntax.
188 % Står på sidan 848 i Norvig.
189 % TODO @anton/victor - beskrivning regexp manual med fina tabeller.
191 Ett reguljärt uttryck består enkelt nog av text som ska matchas. Om
192 man vill matcha texten ''hej'' i en textsträng ''hoppsanhejsan'' så
193 blir det reguljära uttrycket helt enkelt bara ''hej'' och ''hej'':et i
194 ''hoppsanhejsan'' matchas. Däremot är det mer sällan man använder
195 reguljära uttryck för sådana enkla matchningar. Man vill i stället
196 använda dem till att matcha
\textbf{generella mönster
}. Ett exempel på
197 ett mönster skulle kunna vara en e-postadress på formen
198 \verb!<användarnamn>@<subdomän>.<domän>!, där
\verb!<användarnamn>!
199 kan innehålla (i detta exempel) alla siffror, alla små och stora
200 bokstäver, understreck, punkt, bindestreck och plus.
202 I stället för att behöva skriva ett textmönster för varje e-postadress
203 som är möjlig att konstruera (i praktiken oräkneligt antal
204 variationer) kan man använda sig av speciella ''texthändelser'' för
205 att beskriva till exempel början
\slash slutet av ett ord och
206 början
\slash slutet av en hel sträng. Man kan också definiera
207 teckenklasser som man vill inkludera i sitt uttryck, till exempel alla
208 stora bokstäver, alla små bokstäver, siffror, eller till och med
209 vilken godtycklig kombination av tecken som helst. Här nedanför visas
210 en kort tabell med några texthändelser och deras motsvarande reguljära
215 \begin{tabular
}{|c|p
{4cm
}|l|l|l|
}
217 regex-uttryck & Texthändelse & Exempel & Matchar
219 \verb!
\b! & Början eller slutet på ett ord &
\verb!
\b!text
\verb!
\b! & ''ord1
\textbf{text
} ord3'' \\
\hline
223 \verb!^! & Början av en textsträng &
\verb!^!text & ''
\textbf{text
} i början'' \\
\hline
225 \verb!$! & Slutet av en textsträng &
\verb!lutet$! & ''text i s
\textbf{lutet
}'' \\
\hline
227 \verb!
[A-Za-z0-
9]! & Definierar klass med tecknen A till Z, a
228 till z och
0 till
9. &
\verb!
[abc0-
9]! & ''
\textbf{b
}r
\textbf{a
} text med
\textbf{23} te
\textbf{c
}ken'' \\
232 \verb!.! & Står för vilket tecken som helst. &
\verb!^.! & ''
\textbf{t
}ext'' \\
\hline
237 Om man vill matcha en e-postadress i löpande text skulle man alltså
238 vilja använda sig av
\verb!
\b! runt uttrycket för att markera att det
239 som finns runt omkring adressen måste vara ordavgränsare av något
240 slag, så som ny rad eller någon typ av blanktecken. Vill man däremot
241 kontrollera indata från till exempel ett formulärfält där det är
242 meningen att en användare ska ange enbart en e-postadress är det
243 däremot önskvärt att omsluta uttrycket med
\verb!^! i början och
244 \verb!$! i slutet för att markera att hela strängen måste
245 \textbf{börja och sluta med
} adressen.
247 % Olika sätt att matcha e-mail adresser.
248 % \b[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,4}\b
249 % ^[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Za-z]{2,4}$
252 % innehållande sammanställning/analys av eventuell testdata,
253 % implementering av algoritmer osv.
255 % TODO - resultat, användningsområden kopplade till AI.
256 % TODO @anton - Kolla upp och skriv om ELIZA, regexp memory.
257 \subsection{Applikation av Reguljära uttryck
}
258 \subsubsection{ELIZA
}
259 Mer avancerade former av Reguljära uttryck kan använda sig av
260 minnesfunktioner för att spara tidigare matchningar. I
261 programmeringssråket Perl kan man göra ersättningar på formen:
266 Här ersätts alla
\verb!hej! med
\verb!hejsan!. För att spara träffar i
267 sökningen och ersätta med samma ord i ersättningssträngen använder man
268 grupper inom parenteser
\verb!()!. Den sträng som en grupp matchar kan
269 sedan refereras till,
\verb!
\1!, representerar innehållet i första
273 s/heter (
\w+)/Hej på dig
\1, trevligt att höras/
276 Ovan Reguljära uttryck skulle ersätta ''Hej jag heter Anton'' med
277 ''Hej på dig Anton, trevligt att höras''. Denna typ av Reguljära
278 ersättningar utgör grunden för implementationen av Chatroboten ELIZA,
279 som utvecklades Joseph Weizenbaum, se
\cite{speech
}. Nedan följer en
280 kort konversation med Emacs implementering av ELIZA:
283 \item[-
] Hello my name is Anton
284 \item[-
] \textbf{ELIZA:
} How do you do? What brings you to see me?
285 \item[-
] I need help with some Artificial Intelligence questions
286 \item[-
] \textbf{ELIZA:
}Why do you say you need help with some artificial intelligence questions?
287 \item[-
] I'm writing a rapport on Regular Expressions
288 \item[-
] \textbf{ELIZA:
}Is it because of your plans that you say you are writing a rapport on
292 Ovan exempel vittar om att denna typ av chatrobot har en relativt fast
293 ram med frågor–svar att följa, det tar inte lång tid för en mänsklig
294 användare att fatta att det inte är en mänsklig motpart man
295 kommunicerar med. ELIZA är implementerad för att svara på frågor som
296 rök Psykoterapi, så fort man lämnar det bekanta ämnet blir
297 följdfrågorna ologiska ur ett mänskligt perspektiv.
299 Implementationerna av ELIZA har en mängd svar hårdkodade i sig. Nedan
300 kodsnutt visar svaren som kan fås av indata som innehåller vissa
301 nyckelord gälladen död:
305 '((this is not a healthy way of thinking \.)
306 ((doc$ bother) you\, too\, may die someday \?)
307 (i am worried by your obsession with this topic!)
308 (did you watch a lot of crime and violence on television as a child \?))
312 Även en mängd språkord sparas för att på ett bättre sätt kunna tolka
313 indata, exempelvis synonymer och förkortningar:
325 \subsubsection{Tolkning av indata
}
326 När ett datorsystem får indata från användare, finns en mängd
327 användbara Reguljära uttryck för att tolka och behandla denna indata
328 på ett vettigt sätt. Det kan gälla alla typer av indata. Exempelvis
329 som verifiering e-postadresser, datum, telefonnummer och så
330 vidare. Detta är användbart vid allt typ av indata från användare, och
331 i hög grad aktuellt när det gäller forumlär på Internet.
333 Till exempel kan man istället för att kräva att användare ska skriva
334 för och efternamn i separata rutor använda Reguljära uttryck för att
335 försöka tolka vad som är vad. Samma sak gäller adresser och
336 telefonnummer. Det kan vara intressant att ha information och ett
337 telefonnummers riktnummer och landskod, utan att för den sakens skull
338 kräva att en användare ska behöva specificera upp allt sådant
339 manuellt. Följer man bara vanliga konventioner för hur telefonnummer
340 skrivs kan man skapa ett Reguljärt uttryck för att fånga upp all denna
341 information ur en enda textsträng. All sådan här tolkning av indata är
342 väldigt bra ur användarsynpunkt, ''Don't make me click'', som Aza
343 Raskin
\cite{raskin:website
} säger i en presentation.
345 Ett annat bra exempel på hur Reguljära uttryck kan hjälpa till vid
346 inmatning av data finns implementerat i den webbaserade kalendern,
347 http://google.com/calendar/. För att skapa en ny händelse i kalendern
348 kan användaren klicka på aktuell dag och skriva till exempel ''Äta mat
349 hos mamma kl
10-
12'', detta genererar en händelse med rubrik ''Äta mat
350 hos mamma'' och placeras med start kl
10 och slut kl
12. Ett Reguljärt
351 uttryck för detta skulle kunna vara att matcha de första siffrorna
352 efter
\verb!(kl|klockan)!, dessa borde vara starttimme för händelse,
353 separeras dessa siffror av
\verb!.! eller
\verb!:! skulle nästa
354 siffror kunna representera minuter och så vidare. På detta sätt kan
355 man representera det naturliga språket för datorn. Vidare skulle extra
356 nyckelord kunna läggas in, till exempel
\verb!hos! för att markera att
357 det som följer är en position, eller
\verb!med! för att markera att
358 följande text innehåller information om deltagare i händelsen.
363 % av resultatet, koppling till tidigare studier.
368 %. Använd minst två referenser utöver kursboken.
369 \bibliographystyle{alpha
}