DD1320 Tillämpad Datalogi

Föreläsning 9 - Automater, textsökning, KMP

Automater

En portkodsautomat med nio knappar kan se ut så här:
A B C
D E F
G H
I
Anta att den rätta knappföljden är DEG. Då har automaten fyra olika tillstånd:
  1. Starttillstånd.
  2. Knapptryckning D har just gjorts.
  3. Knapptryckningarna DE har just gjorts.
  4. Knapptryckningarna DEG har just gjorts. Låset öppnas.
När automaten är i ett visst tillstånd och en viss knapp trycks ner övergår den i ett nytt tillstånd, och det kan beskrivas med en övergångsmatris:

  A B C D E F G H
1 1 1 1 2 1 1 1 1    Exempel: Om automaten är i tillstånd 3
2 1 1 1 2 3 1 1 1    och knapp D trycks ner övergår den till
3 1 1 1 2 1 1 4 1    tillstånd 2

Man kan också rita en graf med fyra noder (som representerar tillstånden) och en massa bokstavsmärkta pilar (som visar vilka övergångar som finns).
Bilden kan inte visas



Här är några fler exempel på vad automater kan användas till:

Textsökning

Samma automat kan användas för textsökning, till exempel för att söka efter GUD i bibeln. Bokstav efter bokstav läses och automaten övergår i olika tillstånd. När fjärde tillståndet uppnås har man funnit GUD. Datalogins fader, Donald Knuth, uppfann tillsammans med Vaughan Pratt en enkel metod att konstruera och beskriva automaten. James H. Morris kom på samma sak oberoende av dom två! Därför kallar vi automaten KMP-automat. En KMP-automat har bara en framåtpil och en bakåtpil från varje tillstånd. Så här blir den:
Bilden kan inte visas
Ett nolltillstånd har skjutits in längst till vänster. Automaten startar emellertid i tillstånd 1, som har ett G i noden. Den tjuvtittar på första bokstaven i bibeln, och om det är ett G läser den G-et och går till höger. Annars följer den bakåtpilen utan att glufsa bokstaven. I nolltillståndet glufsar den alltid en bokstav och går till höger. Koden blir i princip så här, om vi först antar att bokstäverna lästs in i en kö, som har en extra metod peek(), med vilken man kan tjuvtitta på första noden. 
i = 1 # starttillståndet
while i < 4:
  if i == 0 or q.peek() == sokord[i]: 
     i = i+1
     q.get()
  else: 
     i = next[i];
Här är sokord[i] i-te bokstaven i det sökta ordet och next[i] det tillstånd man backar till från tillstånd i. Nextvektorn (bakåtpilarna) i vårt exempel blir
i next[i]
1
0
2
1
3
1
Om vi i stället söker efter ADAM i bibeln blir KMP-automaten så här:
Bilden kan inte visas
Nextvektorn för ADAM blir alltså den här:
i next[i]
1
0
2
1
3
0
4
2
För GUD gick bakåtpilen från tillstånd 3 till tillstånd 1, men här vore meningslöst att två gånger i rad kolla om bokstaven är A. Bakåtpilen från tillstånd 4 till tillstånd 2 kräver också en förklaring. Om vi har sett ADA och nästa bokstav inte är ett M kan vi i alla fall hoppas att det A vi just sett ska vara början på ADAM. Därför backar vi till tillstånd 2 och undersöker om det möjligen kommer ett D. Reglerna för hur nextvektorn bildas kan sammanfattas så här: Kom ihåg att nextvektorn bara behövs när det kommer ett dåligt tecken.




Om den sträng vi söker efter är m tecken lång och texten vi söker i är n tecken lång kräver KMP-sökning aldrig mer än n+m teckenjämförelser och är alltså O(n+m). Metoden går igenom texten tecken för tecken - man kan alltså läsa ett tecken i taget t ex från en fil vilket är praktiskt om texten är stor.

Boyer-Moore

Då hela texten vi söker i finns i en lista kan man istället använda Boyer-Moores metod. Den börjar med att försöka matcha sista tecknet i söksträngen, som är m tecken lång. Om motsvarande tecken i texten inte alls förekommer i söksträngen hoppar den fram m steg, annars flyttar den fram så att tecknet i texten passar ihop med sista förekomsten i söksträngen.
Exempel: Vi söker efter TILDA i texten MEN MILDA MATILDA. 
MEN MILDA MATILDA  
TILDA
     TILDA
          TILDA
            TILDA
MEN MILDA MATILDA
Boyer-Moore är O(n+m) i värsta fallet, men ca n/m steg om texten vi söker i består av många fler tecken än dom som ingår i söksträngen, så att vi oftast kan hoppa fram m steg.

När du skriver Ctrl-S för att söka efter en sträng i Emacs är det Boyer-Moore som används.

J Strother Moores egen animation av Boyer-Moore.

Rabin-Karp

Beräknar en hashfunktion för söksträngen och jämför med hashfunktionen beräknad för alla avsnitt av längden m i texten. Låt oss söka efter "TILDA" i texten "MEN MILDA MATILDA". Med Pythons hashfunktion hash() % 17 får vi hash(TILDA)=16 
hash(MEN M) = 6
 hash(EN MI) = 15
  hash(N MIL) = 9
   hash( MILD) = 1
    hash(MILDA) = 7
     hash(ILDA ) = 13
      hash(LDA M) = 15
       hash(DA MA) = 12
        hash(A MAT) = 0
         hash( MATI) = 5
          hash(MATIL) = 12
           hash(ATILD) = 3
            hash(TILDA) = 16
För att snabba upp beräkningarna använder man hela tiden förra hashvärdet. Komplexiteten blir
O(nm) i värsta fallet, men i praktiken bara O(n+m).

Sökning på webben

När man använder en sökmotor, t ex Google, för att hitta webbsidor som innehåller ett visst ord skulle alla ovanstående metoder bli för tidsödande. Där slår man istället upp ordet i ett index som skapats i förväg. Hur det fungerar kan man läsa mer om i kursen DD2418, Språkteknologi.

Reguljära uttryck

Om man t ex skulle vilja söka efter lab1, Lab2, eller labb3 så kan man använda ett reguljärt uttryck för att beskriva söksträngen. Ett reguljärt uttryck består av tecken och metatecken som tillsammans utgör ett sökmönster. Metatecken (t ex * och +) har särskild innebörd. Här följer några regler: Det reguljära uttrycket [Ll]abb?[1-7] kan användas för att hitta alla labbvarianter vi eftersökte ovan.

Det finns UNIX-kommandon som använder reguljära uttryck:

egrep som letar efter ett reguljärt uttryck i en textfil
sed som kan byta ut valda delar av en fil (där delarna väljs ut med hjälp att ett reguljärt uttryck)
awk som är ett programmeringsspråk som bygger på att vissa instruktioner ska utföras vid varje matchning av ett uttryck.

Pythonmodulen re har funktionalitet för reguljära uttryck. Exempel: 

   import re
   pattern="[Ll]abb?[1-7]"
   sometext="Lab5, labb 6, labb7 och lab8"
   print(re.findall(pattern,sometext))
   # Utskriften blir ['Lab5', 'labb7']
Bakom kulisserna i re-modulen skapas automater som kan kontrollera om indata matchar det givna uttrycket.

Modellering av grafiska gränssnitt

Många problem kan modelleras med automater. Objektorienterad programmering lämpar sig väl för att implementera tillstånden.

Exempel:
I många grafiska gränssnitt kan man markera text genom att trycka ner musknappen och hålla den nedtryckt medan man drar musen över texten. Det här kan vi se som en automat med ett normaltillstånd och ett markeringstillstånd, där musknappstryck/släpp ger övergång mellan tillstånden.

Objektmodellering och tillståndsprogrammering kan man läsa mer om i kursen DD2385, Programutvecklingsteknik.

Är man särskilt intresserad av grafiska gränssnitt finns kursen DH2323, Datorgrafik med interaktion

Den som vill veta hur automater egentligen fungerar kan läsa Dilians kurs DD1372, Automata and languages (men den kräver en del andra förkunskaper).