Uppsala universitet
Institutionen för lingvistik
Introduktionskurs i språkteknologi för ITP och DVP/Språkteknologiska delområden VT 00
Leif-Jöran Olsson
Denna laboration ska ge insikter i några av de praktiska problem som kan uppstå när man designar ett stavningskontrollprogram.
Under laborationen ges chansen att studera och förbättra en enkel rättstavningsmjukvara i ett antal olika moduler.
I denna laboration ska vi gå igenom ett enkelt modulärt rättstavningsprogram, modul för modul, för att dels utvärdera hur delarna fungerar och dels diskutera hur de skulle kunna utvecklas.
Även om det inbjuds till en del programmering, är det inte obligatoriskt för någon del i laborationen; det går lika bra att bara informellt beskriva de algoritmer man skulle vilja använda.
De fyra modulerna programmet består av hanterar:
- förprocessning och tokenisering,
- orduppslagning,
- versaler och egennamn, respektive
- sammansatta ord.
All mjukvara i den här laborationen finns i katalogen /home/staff/ljo/undervisning/ist_std00/lrt-labb/.
Förprocessning och tokenisering
Innan man kan gå igenom en text ord för ord för att avgöra ifall varje enskilt ord (token) är rättstavat behöver man avgöra vilka delsträngar i texten som verkligen är ord.
Dessutom kan texten innehålla formatteringskoder (exempelvis i HTML) som man vill ignorera i stavningskontrollen.
Den första modulen i vårt rättstavningsprogram är en s.k. förprocessare, som utifrån en textfil skapar en lista över alla tokens (sorterade efter förekomst). Denna process brukar kallas tokenisering.
Dessutom fungerar vår förprocessare som ett filter, som tar bort alla HTML-taggar som är i vägen och konverterar alla SGML-entiteter (exv ä) till motsvarande svenska tecken (i det här fallet bokstaven ä).
Fotnot: En tokeniserare ingår egentligen inte i den gängse definitionen av en förprocessare, men det betyder inte att det inte finns något skäl att inkludera en. I själva verket utför filtreringen och tokeniseringen så likartade uppgifter, att en åtskillnad dem emellan möjligen är meningslös. Dessutom, vilket är viktigt, sparar man en genomgång (eng. pass) av texten genom att sammanföra dem båda i vad som motsvarar en finit transduktor.
html2tokens är ett enkelt bash-skript som försöker göra en sådan här förprocessning. Studera skriptet och försök förstå så mycket som möjligt av det.
Skriptet använder kommandot sed för att filtrera texten; sed 's/A/B/g' byter ut alla förekomster av ett reguljärt uttryck A mot strängen B.
Fotnot: I själva verket behöver inte B tolkas bokstavligt som en sträng. \1 i B betyder ungefär det som matchas mellan första uppsättningen "escapade" parenteser i A (\( och \)), och mer generellt blir \n det som matchas mellan n:te uppsättningen parenteser i A.
Ett exempel: sed 's/\([ab]\)/\1\1/g' dubblerar alla förekomster av a:n och b:n.
Flera förekomster av Sed blir tillsammans ett filter för HTML-taggar, som skickar vidare sin output till en transduktor för SGML-entiteter, som i sin tur skickar vidare till tokeniseraren, som avslutar förprocessningsmodulen.
Skriptet är inte perfekt. Pröva det på texten Uppsala universitets organisation för en snabb utvärdering. (Spara dokumentet på ditt konto och kör html2tokens.sh FILNAMN.html|more)
Det första man kan lägga märke till är att filtret inte kan hantera riktigt alla SGML-entiteter som förekommer i texten på ett riktigt tillfredställande sätt. Den första uppgiften är att utveckla html2tokens så att det klarar att hantera SGML-entiteter i texten.
En annan grej som är värd att titta på är definitionen av ett ord som programmet använder. Vad använder programmet för definition? Hur kan den utvecklas?
Kom ihåg: Om du inte vill programmera går det bra att i ord beskriva de tillägg som behöver göras. Om du vill programmera, men har svårt för att formulera dina tankar i programkod, så tala med mig.
Överkurs
För dig som vill lära dig lite extra nyttiga programmeringstips under kursen, är det här ett perfekt tillfälle att lära dig programmeringsverktyget Lex.
Fotnot: Den fria varianten av Lex heter Flex.
Lex är ett "skal" till programmeringsspråket C, som i mångt och mycket liknar det sätt Sed arbetar på, med två stora skillnader:
- C är ett kompilerat språk, vilket ger högre effektivitet
- I Lex kan det som motsvarar B i sed 's/A/B/g' vara ett godtyckligt komplicerat uttryck, eller tillochmed ett helt program.
Namnet Lex är en kortform för Lexical Analyzer (ung. Lexikonuppslagare), en beteckning för det första steget i en parsning.
Även om Lex är skapat för att designa framänden (eng. front end) av en parser för ett formellt språk, är det även mycket lämpligt att använda för första steget i många språkteknologiska produkter.
Börja med att läsa manualsidan för Lex (man lex på strindberg). Sedan skriver du helt enkelt om skriptet html2tokens i Lex, kompilerar och jämför prestanda med originalet.
Tips: Det finns ett påbörjat motsvarande Lex-program med information om kompilering, prestandamätning m.m. i filen html2tokens.l, som du kan använda för att komma igång --- oavsett om du någonsin har programmerat i C eller om du gör det jämt, finns det tillräckligt med information i dokumentationen och exemplet för att du skall kunna lyckas bra med uppgiften. Och stöter du på något problem är det bara att fråga labbhandledaren.
Fotnot: Det går bra att skippa de tekniska detaljerna i Lex-dokumentationen. I Lexmanualen kan jag tillochmed rekommendera att helt och hållet skippa de första delarna, för att börja läsa efter rubriken Creating an Input Language with the lex and yacc Commands, där det finns några bra exempel.Överkursuppgiften innebär alltså att du gör en uppgift motsvarande ovanstående, fast i Lex istället för shellskript.
Orduppslagning
Skriptet checkWords jämför orden i en text med orden i ett lexikon. Detta är ekvivalent med att göra stavningskontroll av isolerade ord.
Läs skriptet och förstå så mycket som möjligt av det. Sedan kör du programmet: html2tokens FILNAMN.html | checkWords
Du kommer att märka att programmet genererar många falsklarm. Försök lista ut vad som orsakar dessa, och skriv ner orsakerna för några olika typer av falsklarm.
Om du tror att du kan lösa några av problemen i checkWords genom att göra ändringar i det, så gör det.
Om du har problem med att formulera dina tankar som programkod, så be gärna labhandledaren om hjälp. Och, som vanligt: Det är inte obligatoriskt att göra dessa ändringar. Det går lika bra att formulera vad som skulle behöva ändras och hur i naturligt språk.
Fotnot: Man kunde iochförsig tänka sig att skriva ett Lex-program för att lösa orduppslagningen, vilket skulle kunna göra det hela mer effektivt. Det kan tillochmed anföras att detta är precis vad Lex skapades för; lexikonuppslagning.
Det finns dock en viktig skillnad mellan lexikonuppslagning i naturligt språk och den i ett formellt språk -- exempelvis Prolog: antalet ord som kan förekomma.
Detta gör att ett Lex-program för en sådan här uppslagning skulle bli bra mycket mer komplicerat än det i förprocessningen, vilket skulle falla långt utanför denna kurs.
På grund av detta finns det inte heller någon överkursuppgift till denna uppgift.
Versaler och egennamn
Ett annat av de problem du kommer att se i resultatet av checkWords är att de meningsinitiala ord som inleds med en versal och andra ord som innehåller versaler i regel inte kan hittas i lexikonet.
Det finns ett antal olika lösningar för detta, här några av dem:
Konvertera både lexikonet och alla tokens till gemener. Detta löser problemet, men kan ställa till problem om man vill undvika felstavningar av exempelvis sådana ord som måste innehålla en versal (t.ex. Sverige).
Konvertera första bokstaven i alla meningsinitiala ord till en gemen. Detta löser problemet, men å andra sidan uppstår problemet att ett meningsinitialt Sverige orsakar ett falsklarm.
Antag att varje gemen i lexikonet kan skrivas om som en versal i en token, men lägg till begränsningen att en versal i lexikonet aldrig kan skrivas om som en gemen i en token. Detta löser båda problemen, men ett problem kvarstår: Det finns vissa ord som aldrig får innehålla versaler, exempelvis ord som inte är meningsinitiala och inte egennamn. Dessutom finns det led i egennamn, exv af, som aldrig får skrivas med initial versal (enligt Svenska språknämnden 1991).
Vilken lösning föreslår du? I denna uppgift får du görna göra en liten implementation (använd då ett minimalt lexikon, för att spara tid) för att testa dina idéer, men det är som vanligt inte obligatoriskt.
I denna uppgift kan du exempelvis utgå från något av förslagen (1)-(3) ovan, komma med en helt egen lösning, eller argumentera för att en helt annan arkitektur på hela rättstavningsprogrammet vore bättre för dessa problem.
Överkurs
För dig som vill djupdyka lite grann i denna uppgift finns det rum att fundera över hur en lösning ser ut som dels klarar att hantera versaler och dels släpper genom godtyckliga egennamn, med reservationen att om ett namn, exv Fredrik, förekommit en gång i en text, ska inte en stavningsvariant Frerik eller liknande accepteras utan varning, särskilt inte om den bara förekommer en gång.
Några tips för den som vill skriva en implementation i denna uppgift:
- Använd ett programspråk med högre nivå, exv Prolog eller Bash, hellre än ett med lägre, exv Java eller Perl. Det gör att du slipper ta vissa svåra beslut i frågor som rör datastrukturer.
- Testa programmet med ett litet lexikon hellre än ett stort. Det sparar antagligen mycket tid i utvecklingsfasen.
- Använd en konstruerad text hellre än en autentisk för att testa att programmet löser just de problem du vill.
- Programmet behöver inte klara att hantera alla de problem som kan uppstå i hanteringen av versaler och egennamn.
Sammansatta ord
Sammansättningar i svenska är ett av de lingvistiskt mest komplicerade ämnen man stöter på i stavningskontroll, vilket beror på ett par saker; att man kan kombinera ord från nästan alla ordklasser på ett dynamiskt sätt (vilket gör att man omöjligt kan göra ett komplett sammansättningslexikon), och att man inte kan kombinera vilka ord som helst till sammansättningar.
I denna uppgift ska vi använda ett enkelt sammansättningsprogram för att se några av problemen. Programmet, som är skrivet i Prolog, analyserar ord genom att se ifall de kan ses som en konkatenering av två ord ur lexikonet. Ta en titt på programmet, och försök förstå hur det fungerar.
Försök utöka programmets lexikon och prova köra några sammansättningar: echo sammansättning | compound.sh. Om programmet inte skriver ut något har det accepterat ordet. Om det skriver ut samma ord kunde det inte analyseras.
Skriv en kort diskussion om vart och ett av följande:
- Ge några exempel på typer av sammansättningar som compound,sh alltid missar.
- I compound.sh är grammatiken otroligt enkel: n-sms -> n n, men om du försöker utöka den kommer du att se att svenska sammansättningar visar en enorm variation. Förklara vilka problem som uppstår när sammansättningsgrammatiken är för liten, dvs när den undergenererar.
- Ge minst tre olika kategorier av falska träffar grammatiken kan ge om den övergenererar. Förklara för var och en av dem vad som orsakar den.
Överkurs
Försök formulera (informellt eller med implementation, exv med utgång från compoundCheck) en sammansättningsgrammatik som klarar alla sammansättningar i texten, och inte övergenererar för något ord inom den domänen.
Hur kan man göra (främst avseende ställningstaganden i designen av rättstavningsprogrammet), för att minska den skada som övergenerering i sammansättningsmodulen kan orsaka? Ge några olika exempel på saker man kan tänka på och på de fenomen dessa gör att man undviker.
Redovisning lämnas i form av skriftlig rapport till Leif-Jöran Olsson (i postfacket på Institutionen för lingvistik eller via mail i postscriptformat) senast den 30 mars.
Rapporten ska innehålla/behandla det som tas upp i uppgiftsbeskrivningen ovan.
Rapporten kommer att ges betyget godkänd, väl godkänd eller underkänd enligt följande:
- För godkänt krävs en rapport på ca tre sidor, plus en sida extra för varje gruppmedlem utöver den första.
- För väl godkänt krävs därutöver att man löst minst två stycken överkursuppgifter, och i rapporten också har ungefär en sida per överkursuppgift i anslutning till motsvarande uppgift.
Lycka till! /Leif-Jöran
Troligtvis kan man klara alla uppgifter utan att titta i någon av referenserna, men se detta som tips för ifall du skulle köra fast.
Allmänt
Theo Vosse 1994: The Word Connection, Grammar-based Spelling Error Correction in Dutch. PhD Thesis, University of Leiden. ISBN 90-75296-01-0. ss 62-68, 70-81, 88-91, 99-116, 157-181, 183-189.
Förprocessning och tokenisering
Gregory Grefenstette & Pasi Tapanainen 1994: What is a Word, What is a Sentence? Problems of Tokenization. I The Proceedings of The 3rd International Conference on Computational Lexicography (COMPLEX '94). ss 79-87. Hungarian Academy of Sciences, Budapest. ( http://santana.uni-muenster.de/Linguistik/bibliothek/korling/grefen.ps )
Eric S. Raymond 1995: Sed (1). (UNIX-kommando på STP-datorerna: man sed)
Ed (1). (1994) (UNIX-kommando på STP-datorerna: man ed)
Regexp (5). (1996) (UNIX-kommando på strindberg: man 5 regexp)
Till överkursuppgiften (referenslitteratur)
Lex (0). (UNIX-kommando på strindberg: man lex)
Aho, Sethi & Ullman 1986: Compilers: Principles, techniques and Tools, Addison-Wesley. ss 105-111
Orduppslagning
Se Vosse (ovan), fr a ss 183-189
Versaler och egennamn
Svenska språknämnden 1991: Svenska skrivregler. Almqvist & Wiksell, Stockholm.
Sammansatta ord
Ingrid Almqvist & Anna Sågvall Hein 1996: Defining ScaniaSwedish - a Controlled Language for Truck Maintenance. In CLAW 96, Proceedings of the First International Workshop on Controlled Language Applications, KU Leuven, Belgium, ss 159-164. ( http://stp.ling.uu.se/~corpora/scania/ash961.html )
Till överkursuppgiften (referenslitteratur)
Olof Thorell 1981: Svensk ordbildningslära. Stockholm.