Labb 1

Konkordans

Om ni redovisar labben senast den 14 september får ni en labbleveranspoäng var, 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 8 september (ingen annan redovisningsmöjlighet finns). Det är frivilligt att redovisa teoriuppgifterna, men för att klara av att göra labben bör ni ha gjort dom.

En konkordans är en datastruktur 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 ni skriva ett program som givet en text skapar en konkordansdatastruktur på filsystemet samt 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 konkordansdatastrukturen 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 algoritmens
Det finns 12 förekomster av ordet.
let.  Historia  Cooley  Tukey-algoritmens historia börjar kring år 1805
 att jämföra målvariabeln med algoritmens estimering av målvariabeln. V
alsdivision skulle detta vara algoritmens totala komplexitet. Dock kvar
maximala använda minnet under algoritmens gång är det intressanta. Form
använda binär exponentiering. Algoritmens korrekthet förklaras som följ
 rötter kommer att klara båda algoritmens steg. Stage Junior 2006 Stage
r till nod 4 (se nästa bild). Algoritmens steg upprepas, och det är nu
att lära en robothund att gå. Algoritmens förmåga att lösa problemet be
ma problem. Ett annat ord för algoritmens resursberoende är komplexitet
rterad listan är från början. Algoritmens komplexitet blir O (N²).  Ins
2006) har visat att Masreliez-algoritmens prestanda är relativt bättre
 det behövs även en algoritm. Algoritmens uppgifter är att dela in talp 

Parprogrammering

För att få labbleveranspoäng på denna labb måste ni (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å er 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, stora bokstäver eller godtycklig blandning.

• 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 konkordansdatastrukturen på rimlig tid. Det får inte ta mer än tre minuter att skapa konkordansdatastrukturen på en Ubuntudator (utöver tiden att köra tokenizer och sort).

• 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 vederbörande 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 ni använt C, C++ eller liknande), python3 konkordans.py bil (om ni använt Python) eller java Konkordans bil (om ni 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å skolans Ubuntudatorer. Vid redovisningen ska programmet exekveras på en av skolans Ubuntudatorer (för 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). Ni ska därför använda latmanshashning (se föreläsning 3) som datastruktur. Vid redovisningen ska ni kunna motivera att internminneskomplexiteten är konstant för sökprogrammet.

• Prova att bara använda linjärsökning i indexfilen och jämför med att först använda binärsökning tills sökintervallet är litet och därefter linjärsökning (se pseudokoden i föreläsning 3) och se om det gör skillnad i körtid för något sökord. För vilken typ av sökord borde det teoretiskt sett gå snabbare med binärsökning? Ni kan till exempel mäta körtiden med Unixkommandot time (skriv time först i kommandot som startar ert sökprogram) och kolla på tiden för user. 

Tips

För att komma åt filerna på kurskatalogen på AFS behöver ni antingen köra direkt på en Ubuntudator på KTH eller göra en fjärrinloggning på eller filöverföring mot 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/kth.se/misc/info/kurser/DD2350/adk23/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 de 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.

Ange teckenkodningen hos filen då ni öppnar en fil/ström för läsning eller skrivning. I Java kan det t.ex. se ut som

new InputStreamReader(rawindexfile, StandardCharsets.ISO_8859_1)

och i Python

open(rawindexfilename, encoding = "latin-1")

Då kommer teckenkonverteringen nog att lösa sig av sig själv. Det går också att konvertera strängar/bytearrayer själv med new String(b, "ISO-8859-1") och s.getBytes("ISO-8859-1") i Java Links to an external site. och med metoderna encode och decode i Python Links to an external site..

Var noga med att tänka på vilken teckenkodning som används i vilket steg av programmet, t.ex. för korpus, indexfiler och terminalfönstret som används för sökning. Vi rekommenderar att använda ISO-8859-1 för korpus och indexfilerna. För andra filer kan Unicode eller binärdata användas. Kom ihåg att ange rätt teckenkodning när ni öppnar en fil för att läsa eller skriva.

I C är konvertering mellan ISO-8859-1 och Unicode-kodningar svårare, då är det förmodligen enklast att hålla er till ISO-8859-1 genom hela processen. Om ni använder C räcker det att sökprogrammet kan användas med teckenkodningen ISO-8859-1. Tänk då på att ni behöver ställa om terminalfönstrets teckenkodning.

Läs gärna på om teckenkodning ifall ni tycker det verkar svårt. Bra resurser är t.ex. Wikipediasidan om teckenkodning Links to an external site., samt "The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets" Links to an external site..

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

Konstruktionsprogrammet behöver 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å er skivminnesarea, så skapa dom istället på temporärarean /var/tmp och ta bort dom när ni är klara.

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/kth.se/misc/info/kurser/DD2350/adk23/labb1/tokenizer.c.
Ni kan använda en Makefile eller ett shell-skript för att starta flera program (till exempel tokenizer och sort) när ni konstruerar konkordansen. Kommandot som kör tokenizer och sort kan se ut ungefär så här: 

/afs/kth.se/misc/info/kurser/DD2350/adk23/labb1/tokenizer < /afs/kth.se/misc/info/kurser/DD2350/adk23/labb1/korpus | sort > /var/tmp/rawindex.txt

Eftersom Ubuntu normalt använder teckenkodningen UTF-8 behöver ni sätta shellvariabeln LC_COLLATE till C (med kommandot export LC_COLLATE=C i bash) innan ni 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!). För enkelhets skull finns filen rawindex.txt som skapats med kommandot ovan färdig på kurskatalogen som /afs/kth.se/misc/info/kurser/DD2350/adk23/labb1/rawindex.txt
Använd helst den färdiga rawindex.txt så att ni inte behöver skapa en egen kopia av denna jättefil.

Testa ert program noga. Eftersom denna labb inte testas automatiskt av Kattis är det många som har buggar och får komplettering vid redovisningen. 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). Ni kan kontrollera vad rätt svar på era testfall är genom att använda verktyget grep Links to an external site. på rawindex.txt. Se särskilt till att testa programmet under samma omständigheter som vid redovisning (d.v.s. på en labbdator eller genom SSH i KTH:s datormiljö).

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

Vid labbpassen och redovisningen

Labbpassen genomförs både i sal (se schemat) och på distans med hjälp av Zoom. Varje labbgrupp som vill delta i labbpasset i Zoom skapar ett eget Zoomrum att arbeta i under labbpasset. I kursen används (för både sal och Zoom) 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 (för Zoomlabb) och i kommentarsrutan vilken labb det gäller. Ange om ni vill redovisa eller få 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 om ni inte sitter vid en Ubuntudator i sal). Använd den färdiga filen rawindex.txt på kurskatalogen vid redovisningen, så att det inte behöver ligga flera kopior av den och ta upp plats på /var/tmp. Och ta bort alla era filer på /var/tmp direkt efter redovisningen.

Vid redovisningslabbpassen (fyratimmarspassen, som huvudsakligen är till för redovisningar men då hjälp också ges) bokas redovisningstider med systemet Remores.

Länk till bokningslistor för labbredovisning 14 september 2023 publiceras här en dag före labbredovisningen. Det kommer att ordnas tillräckligt med tider för alla som vill redovisa. Läs instruktionerna noga innan ni bokar er redovisningstid. Avboka den bokade tiden om ni inte är redo för redovisning.

Länk till bokningslistorna. Boka inte in er för redovisning för en assistent som ni känner väl, då blir det jäv.

Den som vill ha hjälp använder Stay A While på samma sätt som vid hjälppassen. Den 14 september ges hjälp huvudsakligen i labbsalarna, eftersom alla Zoomassar tar redovisningar.

Innan ni redovisar, gå igenom punktlistan med kraven på lösningen ovan och kontrollera att ert program uppfyller alla krav. Förbered själva redovisningen genom att generera konkordansdatastrukturen och ha program, testfall och skisser redo. Ni kommer då att få redovisa följande (med delad skärm om det är en Zoomredovisning):

• 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 studenterna i labbgruppen ska kunna redogöra för hela programmet (vilket blir en naturlig följd av att ni parprogrammerat).