Labb 1

Konkordans

Om du redovisar labben senast den 20 september får du en bonuspoäng på tentan. På övningen den 12 september har du dessutom möjlighet att redogöra för lösningen på teoriuppgifterna nedan. Korrekt lösning av dessa ger en bonuspoäng på tentan. Sen redovisning ger ingen bonus. 
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

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.

  • 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 (som kan ses som en variant på en trie implementerad som array för dom första bokstäverna i ordet och sorterad array för resten av bokstäverna, se föreläsning 3) som datastruktur.

Tips
Texten, som ligger på /info/adk13/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/adk13/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/adk13/labb1/tokenizer < /info/adk13/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

Teoriuppgifter

  1. Indexinformationen för ett ord (det vill säga i vilka teckenpositioner ordet förekommer i den stora texten) kan bli mycket stor. Bör positionerna lagras som text eller binärt (data streams i Java)? Bör indexinformationen lagras tillsammans med själva ordet eller på ett separat ställe?

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

    • utrymme på skivminnet,

    • utrymme i primärminnet,

    • 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. Tänk på att datastrukturen ska ligga på fil och att sökningar alltså görs i filen istället för som vanligt i internminnet.

Viggo Kann created page 21 August 2013

Administrator Viggo Kann changed the permissions 4 September 2013

Kan därmed läsas av alla och ändras av lärare.
commented 10 September 2013

angånde labteorin ska hur ska den redovisas?

Administrator commented 10 September 2013

Labbteoriuppgifterna får lösas i grupp men till övningen ska var och en ta med sig en egen skriftlig lösning. Det är dock okej om två personer har med var sitt exemplar av samma lösning som man har skrivit tillsammans.

Någon gång under övningens första timme kommer labbteorin att redovisas muntligt för en kamrat. Ni kommer då att grupperas två och två och ställa ett urval av teorifrågorna till varandra. Efter detta ska ni lämna in frågeprotokollet och era skriftliga lösningar till övningsassistenten.

Resultatet av labbteorin kommer några dagar senare att synas i Rapp.

commented 11 September 2013

Hur många tecken bör man ta hänsyn till utöver å, ä, ö?

Administrator commented 12 September 2013

Det givna programmet tokenizer.c definierar vilka tecken som ska vara med och vad som utgör ett ord.

commented 13 September 2013

Förstår att en viktig del av labben är att inte använda mycket minne. För att träna på att lösa problem där man inte kan lagra allt i primärminnet. Hur mycket minne får man använda?

Administrator commented 13 September 2013

Konstant minne (dvs oberoende av antalet ord i indexet) är okej att använda.

commented 18 September 2013

Vi får felmeddelandet "export: command not found" när vi försöker export LC_COLLATE=C. Vi har även testat bash -c "export LC_COLLATE=C" utan framgång. Vad gör vi för fel?

Administrator commented 18 September 2013

Kommandot export hör till bash shell, så om ni kör något annat shell får ni sätta variabler med något annat kommando (till exempel setenv LC_COLLATE C om ni kör tcshell). Eller också startar ni bash med kommandot bash och därefter ger export-kommandot. Se Unixlathunden för mer information.

commented 19 September 2013

Annars brukar det gå bra med att skriva allt på samma rad (åtminstone i bash):

anvnamn@dator:~$ LC_COLLATE=C sort ...

Då sätter man temporärt LC_COLLATE=C bara för det programmet som körs.

commented 16 December 2013

Om man kör /info/adk13/labb1/tokenizer < /info/adk13/labb1/korpus | sort > /var/tmp/ut hamnar orden å, ä, ö längst upp - vad gör man för att åtgärda detta?

Teacher commented 16 December 2013

Ge kommandot    export LC_COLLATE=C       innan du kör sort så blir sorteringsordningen som den ska.

Feedback News