Labb 2

Rättstavning

Om du redovisar labben senast den 4 oktober får du en bonuspoäng på tentan. På övningen den 26 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.

I katalogen /info/adk13/labb2 finns ett Javaprogram som löser nedanstående problem. Din uppgift är att snabba upp programmet så att det går ungefär 10000 gånger snabbare. Korrekthet och effektivitet testas genom att din lösning skickas till Kattis. För att klara labben ska du bli godkänd av Kattis samt redovisa labben för en handledare. Börja med att logga in i Kattis och anmäla dig till adk13 i menyalternativet Kurser i översta menyn.

Problem
Editeringsavståndet mellan två ord är det minimala antalet bokstavsoperationer som krävs för att transformera det ena ordet till det andra. Det finns tre tillåtna bokstavsoperationer:

  1. ta bort en av bokstäverna i ordet

  2. lägg till en bokstav någonstans i ordet

  3. byt ut en bokstav i ordet mot en annan bokstav

Till exempel kan ordet alroitm transformeras till algoritm genom att bokstaven r byts ut mot g (regel 3) och bokstaven r skjuts in efter bokstaven o (regel 2). Kedjan

alroitm -> algoitm -> algoritm

visar att editeringsavståndet mellan alroitm och algoritm är högst 2. Eftersom det inte går att transformera alroitm till algoritm i en enda bokstavsoperation så är editeringsavståndet mellan orden precis 2.

Ett vanligt sätt att ta fram rättstavningsförslag till ett felstavat ord är att helt enkelt returnera dom ord i ordlistan som har minst editeringsavstånd till det felstavade ordet. Programmet ska givet en ordlista och ett antal felstavade ord beräkna rättstavningsförslag på detta sätt.

Specifikation
Indata består av två delar. Den första delen är ordlistan, som består av ett antal ord i utf-8-bokstavsordning, ett ord per rad. Denna del avslutas av en rad som bara innehåller ett '#'-tecken. Den andra delen är ett antal felstavade ord som ska rättstavas, ett ord per rad. Dom felstavade orden ingår inte i ordlistan. Varje ord i indata består bara av små bokstäver i svenska alfabetet (a-z, å, ä, ö), inga mellanslag, skiljetecken eller siffror.

Programmet ska för varje felstavat ord skriva ut en rad bestående av det felstavade ordet följt av det minimala editeringsavståndet inom parentes följt av en lista med alla ord i ordlistan som har minimalt editeringsavstånd till det felstavade ordet. Listan ska vara i bokstavsordning och varje ord i listan ska föregås av mellanslag. Ordlistan har högst en halv miljon ord och antalet felstavade ord i indata är högst 100.

Exempel på körning
En ordlistefil finns i /info/adk13/labb2/ordlista. Du kan provköra ditt program genom att skriva in några felstavade ord (till exempel labd och dabbbhud) på varsin rad i en fil (t.ex. testord.txt) och sedan köra

spel01$ cat /info/adk13/labb2/ordlista testord.txt | java Main
labd (1) labb lagd land
dabbbhud (4) anbud dabba nabbad

Uppgift
Det givna Javaprogrammet löser visserligen ovanstående problem, men det tar timmar att få fram svaret. Du ska effektivisera programmet så att det hittar svaret inom den tidsgräns som Kattis ger.

Bra testfall att testa ditt program med finns på /info/adk13/labb2/testfall/

Teoriuppgifterna ger uppslag om olika sätt att effektivisera programmet. Ditt optimerade program ska ha samma in- och utmatning som det givna programmet och det måste fortfarande vara Java.

Kattis känner till problemet som adkspelling

Teoriuppgifter

Sätt dig in i hur det givna programmet fungerar och svara sedan på följande frågor.

  1. Formulera rekursionen (partDist i programmet) så kompakt som möjligt med matematisk notation.

  2. Beräkna partDist("labd", "blad", x, y) för alla x och y mellan 0 och 4 och för in värdena i en matris M. Vad blir M?

  3. Vad är det alltså metoden partDist(w1, w2, x, y) beräknar?

  4. Visa att tidskomplexiteten för Distance(w1, w2) är Omega(2^max(n,m)) i värsta fallet, där n är antalet bokstäver i w1 och m är antalet bokstäver i w2.

  5. Visa hur man kan spåra vilka editeringsoperationer som görs i den kortaste editeringsföljden från "labd" till "blad" genom att titta på matrisen M.

  6. Visa med pseudokod hur rekursionen kan beräknas med dynamisk programmering, dvs hur en matris M kan skapas.

  7. Analysera tidskomplexiteten för att bestämma editeringsavståndet mellan ett n-bokstavsord och ett m-bokstavsord med dynamisk programmering.

  8. Beräkna dynprogmatrisen för editeringsavståndet mellan "labs" och "blad".

  9. Vilken del av matriserna för "labd"-"blad" och "labs"-"blad" skiljer?

  10. Allmänt sett, vilken del av matriserna för Y-X och Z-X skiljer när orden Y och Z har samma första p bokstäver?

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 16 September 2013

KATTIS verkar inte ha kursen adk13 ännu. När ändras detta?

Administrator commented 17 September 2013

Nu är kursen adk13 skapad i Kattis och labb 2-domaren finns med där. Övriga labbar läggs till efter hand.

Gå till adk13 i Kattis och klicka på Jag är student på den här kursen och vill registrera mig på Kattis.

commented 24 September 2013

I fråga 4, ska det stå O(2max(n,m)) (linjär tid) eller O(2^max(n,m)) (exponentiell tid)?

Administrator commented 24 September 2013

Detta uttryck blev fel i överföringen från gamla kurswebben. Det ska stå 2^max(n,m) alltså exponentiell tid. Tack för påpekandet! Jag har nu korrigerat sidan.

commented 29 September 2013

Finns det någon begränsning på hur långa orden i ordlistan eller indata är?

Teacher commented 29 September 2013

Försök konstruera programmet utan att sätta någon ordlängdsbegränsning i programkoden (men självklart sätter tillgången på minne en praktisk gräns). Alla ord i testordlistorna är äkta ord, så minnesutrymmet ska räcka till även om programmet använder kvadratiskt mycket minne.

commented 30 September 2013

Får man fler än ett förösk på KATTIS?

Teacher commented 30 September 2013

Det går bra att skicka in om och om igen till Kattis, även efter det att Kattis godkänt inskickningen. På det sättet kan man fortsätta att optimera och se hur snabbt programmet kan bli, om man har lust med det.

Feedback News