Föreläsning 10: Automater, textsökning
Mål | Läs i kursboken |
Automater Textsökning |
Aziz, Cackler, Young: Basics of Automata Theory (Links to an external site.) Georgy Gimel’farb: String Matching Algorithms |
Idag
- Automater
- Textsökning
- KMP-automat
- Boyer-Moore
- Rabin-Karp
- Sökning på webben
- Reguljära uttryck
- Om det finns tid över tjuvstartar vi med Föreläsning 11 om Hashning!
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:
- Starttillstånd.
- Knapptryckning D har just gjorts.
- Knapptryckningarna DE har just gjorts.
- 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 I
1 1 1 1 2 1 1 1 1 1 Exempel: Om automaten är i tillstånd 3
2 1 1 1 2 3 1 1 1 1 och knapp D trycks ner övergår den till
3 1 1 1 2 1 1 4 1 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).
Här är några fler exempel på vad automater kan användas till:
- Söka efter ett ord i en text (se KMP-automat nedan).
- Tolka reguljära uttryck.
- Beskriva grafiska gränssnitt.
- Kompilatorns/interpretatorns analys av ditt program (se föreläsning om syntax).
- Komprimering.
- Morfologisk Links to an external site. analys av ord (t ex o-ut-trött-lig-a).
Modellering av grafiska gränssnitt
Grafiska gränssnitt kan modelleras med automater. Vad som ska synas på skärmen, och hur programmet ska reagera på t ex knapptryckningar avgörs då av vilket tillstånd automaten befinner sig i.
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.
I programmet skriver vi då if-satser som kontrollerar vilket tillstånd automaten är i, t ex
if state == HIGHLIGHT:
invertText()
Textavsnitt ur THE COSMIC COMPUTER Links to an external site. av H. BEAM PIPER
Textsökning
Med textsökning menar vi att söka efter en sträng s i en text. Anta att strängen har längd m.
En naiv metod skulle vara att gå igenom texten en bokstav framåt i taget och jämföra varje delsträng av längd m med strängen s.
Om vi söker efter s = "was" i texten till höger skulle vi då få
"Thi" == "was"
"hir" == "was"
"irt" == was"
"rty" == "was"
osv. vilket ger oss tre tecken-jämförelser i varje steg. I det allmänna fallet får vi O(m*n) där
- m är längden av söksträngen
- n är längden av texten
Finns det effektivare sätt att söka efter en sträng i en text?
KMP
Samma automat som vi tittade på ovan kan användas för textsökning, till exempel för att söka efter ordet DEG. Bokstav efter bokstav läses och automaten övergår i olika tillstånd. När fjärde tillståndet uppnås har man funnit ordet DEG. 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 Links to an external site.. En KMP-automat har bara en framåtpil och en bakåtpil från varje tillstånd. Så här blir den:
Ett nolltillstånd har skjutits in längst till vänster. Automaten startar emellertid i tillstånd 1, som har ett D i noden. Den tjuvtittar på första bokstaven i texten, och om det är ett D läser den D-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 bokstaven. Det är variabeln i som håller reda på vilket tillstånd vi befinner oss i.
i = 1 # starttillståndet while i < 4: if i == 0 or q.peek() == sokord[i]: i = i+1 q.dequeue() else: i = next[i];
Här är sokord[i] den 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 blir KMP-automaten så här:
Nextvektorn för ADAM blir alltså den här:
i | next[i] |
1 | 0 |
2 | 1 |
3 | 0 |
4 | 2 |
Varför det? För DEG 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 next-vektorn bildas kan sammanfattas så här:
- next[1]=0.
- Annars är next[i]=1 om sökordet inte innehåller upprepningar.
- ...men om de j senaste bokstäverna vi sett bildar början på sökordet sätts next[i]=j+1.
- ...men om bokstav j+1 är samma som bokstav i sätts i stället next[i]=next[j+1].
Kom ihåg att next-vektorn 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-F för att söka efter en sträng i webbläsaren är det troligen Boyer-Moore som används (se t ex Chromium Links to an external site.)
J Strother Moores egen html-visualisering av Boyer-Moore Links to an external site..
Rabin-Karp
Hashfunktioner
En hashfunktion tar en sträng som indata och ger ett stort heltal som utdata. Exempel:
hash("TILDA") = 1018473546
Hur kan det fungera att lagra lösenord hashat? Eftersom samma sträng alltid ger samma hashvärde räckte det med att spara hashvärdet och jämföra med det.
s1 = input("Ge ditt lösenord: ")
if hash(s1) == 1018473546:
print ("OK")
Men hashfunktionen i Python kan inte ge hur stora värden som helst; sys.maxsize (oftast 2147483647) är en övre gräns. Eftersom det finns fler möjliga strängar än hashvärden så betyder det att olika strängar kan ge samma hashvärde.
hash(s1) == hash(s2) betydet inte säkert att s1 == s2
Mer om hashning kommer på nästa föreläsning!
Textsökning med Rabin-Karp
Denna textsökningsmetod går ut på att man 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"! För tydlighets skull krymper vi hahvärdena genom att ta hash() % 17 i exemplet nedan.
Vi beräknar hash("TILDA") % 17 = 10
hash("MEN M") = 8
hash("EN MI") = 7
hash("N MIL") = 6
hash(" MILD") = 3
hash("MILDA") = 15
hash("ILDA ") = 4
hash("LDA M") = 11
hash("DA MA") = 12
hash("A MAT") = 5
hash(" MATI") = 0
hash("MATIL") = 0
hash("ATILD") = 10
hash("TILDA") = 10
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 du läsa mer om i kursen DD1418 Språkteknologi med introduktion till maskininlärning.
Reguljära uttryck
De sökmetoder vi beskrivit ovan kräver att vi vet exakt vilken sträng vi söker efter. Men om man är osäker på stavningen eller t ex skulle vilja söka efter lab1, Lab2, eller labb3 så kan man istället 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:
- a* matchar noll eller flera a:n
- a+ matchar ett eller flera a:n
- a? matchar ett eller inget a
- . matchar alla tecken utom radslut
- [a-zA-Z] matchar alla engelska bokstäver
- [abc] matchar a, b eller c
- [^abc] matchar vilket tecken som helst utom a, b eller c
- X|Y matchar uttrycket X eller uttrycket Y
- \. matchar en punkt. Tecknet "\" används för att rädda det efterföljande tecknet från att tolkas som ett metatecken.
- (ab) skapar en grupp. T ex matchar (ab)+ ett eller flera ab:n
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.
Testa dina reguljära uttryck på regex101.com Links to an external site.
Du som vill veta hur automater egentligen fungerar kan läsa Dilians kurs DD1373 Automater och språk.
För dig som är särskilt intresserad av grafiska gränssnitt finns kursen DH2323, Datorgrafik med interaktion
https://xkcd.com/208/ Links to an external site.