Labb 1

Konkordans

Om du redovisar labben senast den 11 september får du en labbleveranspoäng, som kan ge högre betyg på labbmomentet. Till labben hör teoriuppgifter som kan redovisas för en teoripoäng till tentan, och detta görs på övningen den 3 september (ingen annan redovisningsmöjlighet finns). Det är frivilligt att redovisa teoriuppgifterna, men för att klara av att göra labben bör du ha gjort dom.

En konkordans är en databas där man kan slå upp ord och då få se alla förekomster av ordet tillsammans med orden närmast före och närmast efter i texten. Detta är ett stort hjälpmedel för lingvister som vill undersöka hur olika ord används i språket.

I denna uppgift ska du skriva ett program som givet en text skapar en konkordansdatabas och ett program som frågar användaren efter ord, slår upp ordet och presenterar alla förekomster av ordet i sitt sammanhang. Det är viktigt att varje sökning går mycket snabbt så det gäller att det första programmet lagrar konkordansen på ett sådant sätt att det går snabbt att göra en sökning.

Exempel på körning av sökprogrammet:

$ java Konkordans komplexiteten
Det finns 7 förekomster av ordet.
ta på scen. Breddningsarbete. Komplexiteten har denna innebörd bland anna
räckvidden, hastigheterna och komplexiteten i omvärlden ökar. Domen inneb
 beter sig misstänkt? Ändå är komplexiteten så hög att jag stundtals blir
ttsplatsen. Vi är medvetna om komplexiteten i denna fråga och ser med oro
n. I det övriga materialet är komplexiteten sedan så stor att en fantasif
 av den från 1928 tilltagande komplexiteten i skattelagstiftningen. De då
ttelseorganisationen CIA. Men komplexiteten hos de föreningar som kemiste

Parprogrammering

För att få labbleveranspoäng på denna labb måste du (förutom att redovisa den senast ovanstående datum) genomföra den i tvåpersonsgrupper som arbetar enligt den agila programutvecklingstekniken parprogrammering. Läs här om parprogrammering.

Krav

Följande krav ställs på din lösning:

• Programmet ska vara skrivet i ett riktigt programspråk och inte något operativsystemnära skriptspråk eller liknande.

• Konkordansen ska inte skilja på stora och små bokstäver. Användaren ska alltså kunna skriva in alla sökfrågor med små bokstäver.

• Det givna programmet tokenizer.c på kurskatalogen (se nedan) definierar hur texten ska delas upp i enskilda ord.

• Konstruktionsprogrammet behöver inte vara jättesnabbt eftersom det bara ska köras en gång, men det måste vara någorlunda effektivt så att det kan skapa konkordansen på rimlig tid. Det får inte ta mer än tre minuter att skapa konkordansen på en Ubuntudator.

• Sökprogrammets utmatning ska inledas med en rad som anger antalet förekomster. Därefter ska varje förekomst av ordet presenteras på varje rad med till exempel 30 tecken före och 30 tecken efter. Ersätt radbyten med mellanslag. Om det finns fler än 25 förekomster ska programmet fråga användaren om hon vill ha förekomsterna utskrivna på skärmen.

• Man ska kunna söka efter ett ord, till exempel "bil", genom att i terminalfönstret ge kommandot konkordans bil (Om du använt C, C++ eller liknande) eller java Konkordans bil (om du använt Java). 

  Svaret (som alltså innehåller antalet förekomster men högst 25 rader med förekomster) måste komma inom en sekund på en av skolans Ubuntudatorer. Vid redovisningen ska programmet exekveras på en av skolans Ubuntudatorer (via fjärrinloggning, se nedan).

• Sökprogrammet ska inte läsa igenom hela texten och får inte använda speciellt mycket internminne. Internminnesbehovet ska inte växa med antalet distinkta ord i den ursprungliga texten (med andra ord ha konstant internminneskomplexitet). Du ska därför använda latmanshashning (se föreläsning 3) som datastruktur.

Tips

För att komma åt filerna på kurskatalogen på AFS behöver du antingen köra direkt på en Ubuntudator på KTH eller göra en fjärrinloggning på shell-servern student-shell.sys.kth.se (den som är anställd som amanuens använder istället staff-shell.sys.kth.se)

Texten, som ligger på /afs/nada.kth.se/info/adk20/labb1/korpus, är en stor fil och ska inte i sin helhet läsas in i internminnet under sökningen. Istället bör sökprogrammet öppna filen och hoppa till dom avsnitt som ska presenteras med seek (använd till exempel fseek i stdio.h i C, seek i Python Links to an external site. eller seek i java.io.RandomAccessFile Links to an external site. i Java). Texten har teckenkodningen ISO-8859-1, som också kallas ISO-Latin 1 Links to an external site.. Det betyder att varje tecken lagras i en byte, vilket är praktiskt när man ska adressera sig till en viss position i filen. Du konverterar en bytearray b till String i Java med new String(b, "ISO-8859-1"). I andra riktningen: en String s konverteras till en bytearray i ISO-8859-1 med s.getBytes("ISO-8859-1"). Mer information om teckenkonvertering i Java finns här Links to an external site.. I Python3 använder man encode och decode för teckenkonvertering, se tutorial Links to an external site.. I C är konvertering mellan ISO-8859-1 och Unicode-kodningar svårare. Om du använder C räcker det att sökprogrammet kan användas med teckenkodningen ISO-8859-1. Tänk då på att det går att ställa om terminalfönstrets teckenkodning.

När du använder skolans Ubuntudatorer (till exempel student-shell.sys.kth.se) ska du inte kopiera textfilen utan istället låta sökprogrammet använda ursprungstextfilen på kurskatalogen.

Konstruktionsprogrammet måste skapa något slags index som talar om för varje ord på vilka positioner i texten det förekommer. Detta index blir av samma storleksordning som texten och sökprogrammet ska därför inte heller läsa in hela indexet. Låt det ligga på en fil (eller flera filer) och positionera med hjälp av seek även i denna fil.

Indexfilerna blir stora och får nog inte plats på din skivminnesarea, så skapa dom istället på temporärarean /var/tmp och ta bort dom när du är klar.

Använd gärna färdiga Unixverktyg som sort vid konstruktionen. En enkel tokeniserare (ett program som läser en text och plockar ut dom enskilda orden samt deras position i texten) finns på /afs/nada.kth.se/info/adk20/labb1/tokenizer.c. 
Du kan använda en Makefile eller ett shell-skript för att starta flera program (till exempel tokenizer och sort) när du konstruerar konkordansen. Kommandot som kör tokenizer och sort kan se ut ungefär så här: 

/afs/nada.kth.se/info/adk20/labb1/tokenizer < /afs/nada.kth.se/info/adk20/labb1/korpus | sort > /var/tmp/ettfilnamnsominteredanfinns 

Eftersom Ubuntu normalt använder teckenkodningen UTF-8 behöver du sätta shellvariabeln LC_COLLATE till C (med kommandot
export LC_COLLATE=C 
i bash) innan du kör sort. Detta gör att sort tolkar texten som ISO-8859-1 och därmed sorterar tecknen i ordningen A B C ... Z a b c ... z Ä Å Ö ä å ö (notera ordningen mellan alfabetets tre sista bokstäver!).

Testa ditt program noga. Tänk ut svåra testfall (olika ytterligheter som enbokstavsord, första eller sista ordet i korpusen eller i indexet etc, se även sista teoriuppgiften).

Java är ganska snabbt, men just vid filhantering är det viktigt att man är noggrann när man använder Java. När du skapar konkordansen kommer du troligen att vilja skriva många gånger på en eller flera filer. Se till att de strömmar du konstruerar för skrivning (och läsning) är buffrade (läsning och skrivning på en RandomAccessFile kan inte buffras). Du kan läsa om Javas in- och utmatning i Java tutorial Links to an external site.

Vid labbpassen och redovisningen

Labbpassen genomförs i år på distans med hjälp av kösystem, redovisningstidsbokningssystem och Zoom. Varje labbgrupp skapar ett eget Zoomrum att arbeta i under labbpasset. I kursen används kösystemet Stay a while på queue.csc.kth.se för att hålla reda på hjälp- och redovisningskön vid hjälplabbpassen (tvåtimmarspassen, som huvudsakligen är till för hjälp men där redovisningar också tas emot). Skriv i rutan Location in länken till den Zoomsession som ni arbetar i och i kommentarsrutan vilken labb det gäller. Ange om du vill redovisa eller ha hjälp. Er labblösning ska redovisas för en labbhandledare vid något av kursens schemalagda labbpass och ansluten till en av skolans Ubuntudatorer (till exempel student-shell.sys.kth.se). Vid redovisningslabbpassen (fyratimmarspassen, som huvudsakligen är till för redovisningar men då hjälp också ges) bokas redovisningstider med systemet Remores enligt anvisningar som läggs upp på Canvas. Den som vill ha hjälp använder Stay a while på samma sätt som vid hjälppassen.

Förbered redovisningen genom att ha genererat konkordansen och ha program, testfall och skisser redo. Ni kommer då att få dela skärm och redovisa följande:

• Reflektera över er erfarenhet från parprogrammeringen vid denna labb. (Krävs endast för labbleveranspoäng.)
• Visa en uppsättning testfall som ni har tagit fram för att kolla att programmet gör rätt. Ni ska också kunna motivera varför ni valt just dessa testfall.
• Visa att programmet fungerar och är tillräckligt snabbt för era testfall och labbhandledarens testfall.
• Visa och förklara hur lösningens datastrukturer på fil och i minnet fungerar.
• Visa programkoden och vara beredd att svara på frågor om den.

Båda i labbgruppen ska kunna svara för hela programmet (vilket blir en naturlig följd av att ni parprogrammerat).