Till KTH:s startsida Till KTH:s startsida

Labb 1

Konkordans

Om du redovisar labben senast den 16 september får du en bonuspoäng på tentan. Labbteoriuppgifterna nedan kan redovisas för en bonuspoäng till tentan, och detta görs på övningen den 9 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å bonuspoä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 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 två minuter att skapa konkordansen på en Ubuntudator i datorsalarna.

  • 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 bör 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 måste komma inom en sekund på en av skolans Ubuntudatorer i datorsalarna.

  • 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. Du ska därför använda latmanshashning (se föreläsning 3) som datastruktur.

Tips

Texten, som ligger på /info/adk16/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 eller seek i java.io.RandomAccessFile i Java). Texten har teckenkodningen ISO-8859-1, som också kallas ISO-Latin 1. Det betyder att varje tecken lagras i en byte. 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. 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.

Ta ingen kopia av textfilen utan låt 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å /info/adk16/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: 

/info/adk16/labb1/tokenizer < /info/adk16/labb1/korpus | sort > /var/tmp/ut 

Eftersom Ubuntu normalt använder 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 Ä Å Ö ä å ö.

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).

Java är numera 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

Vid redovisningen

Er labblösning ska redovisas för en labbhandledare vid något av kursens schemalagda labbpass och vid en av skolans Ubuntudatorer. I kursen används kösystemet queue.csc.kth.se för att hålla reda på hjälp- och redovisningskön. Skriv i kommentarsfältet vilken labb det gäller och ange om du vill redovisa eller ha hjälp.

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

  • Reflektera över er erfarenhet från parprogrammeringen vid denna labb. (Krävs endast för bonus.)
  • 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).

Teoriuppgifter

  1. Vilka är rollerna vid parprogrammering och vilka uppgifter har varje roll?
  2. Indexinformationen för ett ord (det vill säga i vilka teckenpositioner ordet förekommer i den stora texten) kan bli mycket stor. Hur bör positionerna lagras för att det ska bli effektivast, som text eller binärt (data streams i Java)? Bör indexinformationen lagras tillsammans med själva ordet eller på ett separat ställe?
  3. I denna labb ska datastrukturen för konkordansen huvudsakligen ligga på fil, vilket betyder att sökningar görs i filen istället för som vanligt i internminnet. Det påverkar till exempel hur man representerar pekare. Diskutera för- och nackdelar med olika implementationer av konkordansen med avseende på följande egenskaper:
    • snabbhet (antal filläsningar och filpositioneringar per sökning),

    • minneskomplexitet för fillagringen (bara konstant mycket internminne ska användas)

    • enkelhet att konstruera och lagra på fil.

    Ta åtminstone upp följande datastrukturer:
    • binärt sökträd,

    • sorterad array,

    • hashtabell,

    • trie (träd där varje nivå motsvarar en bokstav i ordet),

    • latmanshashning

    Redovisa för- och nackdelarna i en tabell. 

Arbeta gärna ihop med labbteoriuppgifterna, men var och en ska av administrativa skäl ta med en egen skriftlig lösning med namn på som lämnas in vid redovisningen. Skriv gärna för hand!

Viggo Kann skapade sidan 19 augusti 2016

Lärare Viggo Kann ändrade rättigheterna 19 augusti 2016

Kan därmed läsas av lärare och ändras av lärare.

Lärare Viggo Kann ändrade rättigheterna 1 september 2016

Kan därmed läsas av alla och ändras av lärare.
En användare har tagit bort sin kommentar
kommenterade 5 september 2016

När jag kompilerar tokenizer.c får jag dessa varningar: Kompilering

När jag sedan använder mig av den kompilerade a.out och lagrar detta till en fil genom kommandot ./a.out < korpus > output så ser jag följande i output filen: Output fil

Hanteringen av ÅÄÖ är alltså inte korrekt.
Någon som känner igen problemet och kanske har en lösning?

Lärare kommenterade 5 september 2016

Alexander, kompilatorvarningen är nog ingen fara. Du kan prova att ge väljaren 
-Wno-invalid-source-encoding
för att slippa varningen om teckenkodningen.

För att se åäö korrekt i terminalfönstret måste du ställa in terminalfönstrets teckenkodning i någon meny till terminalprogrammet. Välj ISO-8859-1 eller ISO-Latin-1.

kommenterade 5 september 2016

Du har helt rätt Viggo, tack för hjälpen!

kommenterade 7 september 2016
  • snabbhet (antal filläsningar och filpositioneringar per sökning)

"filpositionering" och "filpositioneringar" ger 9 resp 7 träffar på google (länkar hit inkluderade). Vad åsyftas egentligen?

Lärare kommenterade 7 september 2016

Med filpositionering avses anrop av seek eller motsvarande funktion, se labbeskrivningen ovan.

kommenterade 10 september 2016

Hej!
Ska användare även kunna söka efter siffror eller tecken, såsom "40" eller "@"?

/ Alfrida

Assistent kommenterade 10 september 2016

Nej, det enda som programmen ska kunna hantera är bokstäver

kommenterade 11 september 2016

Är tanken att vi ska använda Bob Jenkins hashfunktion för latmanshashningen av prefix (aaa, aab, aac osv)?

Vill minnas att det talades om någon hashfunktion som producerar lägre tal, och alltså skulle passa för en mindre array med bara så många index som behövs för alla prefix. Men jag kan minnas fel, eller så var tanken att vi själva skulle skriva en sån hashfunktion?

Lärare kommenterade 11 september 2016

Ernst, det är inte bra att använda Bob Jenkins hashfunktion i detta fall. Använd en så enkel hashfunktion som möjligt som inte gör några krockar. På föreläsning 3 var det en färgfråga om detta. Tipset där var att använda en förberäknad funktion som omvandlar mellanslag till 0, a till 1, b till 2 etc och med hjälp av detta tolkar dom tre bokstäverna i prefixet som ett tal i bas 30.

kommenterade 11 september 2016

Aha ok, ja det bör ju inte vara så svårt. Tack!

En användare har tagit bort sin kommentar
kommenterade 14 september 2016

Är det ett formellt krav att vi ska använda oss av binärsökning för att hitta rätt ord inom en "prefix-grupp"? Det verkar som att linjär sökning går tillräckligt snabbt i det här fallet.

Lärare kommenterade 14 september 2016

Ernst, är du säker på att linjär sökning är tillräckligt snabbt för alla ord? Jag vill att den som gått ADK alltid ska använda binärsökning istället för linjärsökning i tidskritiska algoritmer. Det är så enkelt att programmera binärsökning så det ska mycket till för att inte använda det.

kommenterade 15 september 2016

Rad 48 i tokenizer.c borde ändras till
printf("%s %10ld\n", buf, startpos);
Då paddas siffrorna från tokenized med mellanslag, vilket gör att när den skickas till sort kommer den att sortera siffrorna i numerisk ordning istället för teckenordning. dvs:
a   20
a 100

istället för som det nu blir:
a 100

a 20

Det gör att sammanhangen skrivs ut i den ordningen som de faktiskt förekommer i korpus-filen. Några fel blir lättare att hitta och saker beteer sig allmänt mer som man väntar sig.

Lärare kommenterade 15 september 2016

Mikael, det är en bra idé, men vi kan inte ändra labbfilerna under pågående kurs, så ändringen görs till nästa år. Tack för idén!

kommenterade 16 september 2016

Hej, en fråga inför redovisningen: alla datorer är upptagna i spel- och sporthallen. Är det okej att redovisa på egen laptop? Vår sökning går snabbare på skolans datorer ändå.

Lärare kommenterade 16 september 2016

Vi räknar med att den som redovisat lämnar sin dator, så därför kommer det att bli lediga datorer efterhand. Det är 7-8 labbhandledare som tar emot redovisningar parallellt, så även om kön ser avskräckande lång ut så kommer den att betas av i rask takt.

kommenterade 8 december 2016

Jag har ännu inte fått Labb1 inrapporterad i Rapp (däremot Labb 2, 3 och 4). Normal fördröjning eller bör jag undersöka saken vidare?

Lärare kommenterade 8 december 2016

Johan, om en labb inte har kommit in i Rapp vid det här laget så är det något fel. Var snäll och visa upp ditt påskrivna labbkvitto så för jag in resultatet i Rapp.