Nedan hittar ni det kodskelett som ni ska utgå ifrån. Innan ni går vidare, läs koden och försök klura ut vad som skulle hända om man körde den.

• Var sker det första anropet till en funktion? Till vilken funktion?
• Hur gör man för att avsluta programmet?

Kopiera och spara sedan ned kodskelettet nedan i en fil på lämplig plats i er hemkatalog.

def main():
    word = ""
    while word != "q":
        word = input("Type word: ").lower()
        suggestion = autocomplete(word)
        print("Autocompletion finished: ", suggestion)

def autocomplete(word):
    """Return autocomplete suggestions."""
    pass

main()

Förrutom ovanstående kod, kommer ni få tillgång till en liten samling ord- och frekvensfiler i olika konstellationer och filformat. Korpusfilerna finns i /courses/TDDE44/kursmaterial/laboration2/.

Jobbar du på egen dator kan du ladda ner dem: laboration2.zip

shuffled.csv och alphabetical.csv är kommaseparerade filer där varje rad innehåller ett ord och ordets frekvens (d.v.s. hur ofta det förekommer i en viss textmängd). Nedan är ett exempel ur shuffled.csv:

.
.
spårvagn,4
armkrok,2
december,46
nattkylan,1
barhuvad,1
.
.

Filerna shuffled_words och alphabetical_words innehåller samma ord som respektive .csv-fil, men utan frekvenserna. På samma sätt innehåller shuffled_freq och alphabetical_freq samma frekvenser som återfinns i respektive .csv-fil, fast utan orden.

Ni får själva bedöma vilken eller vilka av korpusfilerna som ni behöver för att lösa uppgiften.

Ordlistorna är extraherade från Stockholm-Umeå-korpus 2.0 (SUC 2.0). SUC 2.0 är en balanserad korpus som är sammanställd från texter från olika källor såsom böcker och nyhetstexter. Ord som innehåller siffror eller skiljetecken är bortplockade, men utöver det är ordlistan inte filtrerad eller censurerad på något sätt utan reflekterar källmaterialet för SUC.

För program som rymms i en fil används oftast följande disposition:

1. importer (där andra moduler importeras)
2. funktionsdefinitioner (en eller fler definitioner av den/de funktioner som används i programmet)
3. anrop till funktioner (ett eller fler anrop till de funktioner som gör att något händer)

Nedan följer ett lite mer konkret exempel:

# högst upp finns importer
import random
import med


# sedan följer definitioner av de funktioner som används i programmet
def main():
    # eventuella förberedelser följt av eventuell huvudloop
    data = load_data("datafile")
    while True:
        # sats1
        # sats2
        # ...
        process_something1(arg1, arg2)
        # ...
        process_something2(arg3)


def load_data(filename):
    # pass används för att kunna skriva icke-kompletta funktionsdefinitioner
    # utan att få syntax-fel när man kör programmet
    pass


def process_something1(arg1, arg2):
    pass


def process_something2(arg3):
    pass


# efter definitionerna av funktioner som programmet använder görs ofta ett anrop
# till programmets huvudfunktion, alternativt flera funktioner om det är flera
# funktioner som ska köras.
#
# många gånger lägger man dessa anrop innanför en vilkorssats som endast kör
# anropen när programmet körs som ett skript (återkommer till detta senare i
# kursen)
if __name__ == '__main__':
    main()

Det finns en hel del funktionalitet som hör ihop med specifika datatyper som man kan komma åt genom s.k. punktnotation. Exempel på detta är att använda .append() på en lista. Dessa kallas för metoder (man kan säga att metoder är funktioner som appliceras på värden via punktnotation; mer om detta senare i kursen).

För strängar finns .lower() som returnerar strängen i enbart gemener (se kodskelettet). Andra metoder för strängar är:

• str.endswith()
• str.find()
• str.join()
• str.rstrip()
• str.split()
• str.startswith()
• str.strip()

Med ovanstående notation refererar str till ett strängvärde. Vad dessa gör får du söka dig fram till.

För att lösa problem på ett datalogiskt sätt delar man oftast upp ett problem i mindre delproblem. Ett exempel på en problemuppdelning som kan göras är:

1. Hitta möjliga kandidater på ordförslag
2. Välj den bästa kandidaten

Genom att dela upp ett problem i delproblem kan man underlätta felsökning av kod genom att det blir lättare att avgöra i vilken del av koden som problemet kan finnas. Man kan t.ex. dela upp sin kod så att varje delproblem löses i en separat funktion. Resultatet från funktionen som löser ett delproblem skickas vidare till nästa funktion:

def large_problem(data1, data2):
    result1 = subproblem1(data1, data2)
    result2 = subproblem2(result1)

• För att undvika att läsa in data från fil varje gång ni kör autocomplete, kan ni istället lägga till och skicka med ett extra argument till funktionen autocomplete() som innehåller den information som behövs. Vissa ändringar jämfört med kodskeletet kan behövas.
• Inläsning av data görs då någonstans innan ni går in i loopen som frågar användaren efter ett ord och sedan kör autocomplete()-funktionen.

Dokumentera i funktionskommentaren hur ni tänkt. Funktionskommentarer, också kallade dokumentationssträngar (eng. docstring), skriver man genom att med början på raden direkt efter funktionshuvudet lägga till en speciell typ av sträng som börjar med tre citattecken och avslutas med tre citattecken. Se exempel nedan.

def get_most_frequent_word(document):
    """Returnera det mest frekventa ordet i document.
    
    Funktionen räknar ut ordfrekvenserna i strängen document och returnerar
    sedan det mest frekvent förekommande ordet. Ingen lexikal analys
    genomförs vilket alltså betyder förekomster av "grön" och "gröna" inte slås
    ihop till förekomst av samma ord."""

    # här följer sedan koden som tillhör till funktionen
    ...

En bra funktionskommentar börjar med en kort beskrivning av vad funktionen kommer göra och returnera. Enligt pythonstandard (PEP257), ska första raden i en funktionskommentar vara en mening i aktiv form. Behövs ytterligare förklaring lägger man till en tom rad och kan sedan skriva ett stycke med flera meningar.

I exemplet ovan och i en hel del kod ni stöter på i den här kursen står kommentarer på svenska. Detta har pedagogiska orsaker och ute i verkligheten använder vi engelska.

I del 2 handlade problemet om att hitta ord som börjar på det användaren har skrivit för att kunna fylla på med återstående bokstäver.

Här i del 3 handlar problemet istället om att hitta ord som användaren försökte skriva. Det finns olika sätt att göra detta. En variant är att anta att användanden skrivit rätt antal bokstäver, men att någon eller några bokstäver är fel.

Skriv en funktion som utgår från denna premiss, dvs skriv funktionen autocorrect() som tar in minst ett argument (användarens ord) och försök returnera en rättstavad variant av ordet.

Inläst data (t.ex. alphabetical_words) ska fortfarande användas (för att hitta rätt ord).

Exempel på autocorrect-körning:

Type word: bast
Autocorrection finished: bäst
Type word: furt
Autocorrection finished: fort
Type word: progrannet
Autocorrection finished: programmet

Antag att endast kända ord med samma längd som input-ordet är möjliga kandidater.

Vad är redigeringsavstånd?

Redigeringsavståndet mellan två strängar är hur många redigerande steg (raderingar, infogningar och substitueringar av tecken) som krävs för att transformera ett ord till ett annat. Ett vanligt mått på redigeringsavstånd är Levenshtein-avståndet.

För att beräkna av Levenshtein-avståndet mellan två ord kan ni använda en färdig funktion som finns implementerad i filen /courses/TDDE44/kursmaterial/laboration2/med.py. Kopiera filen från kurskatalogen till samma katalog som er autocomplete-pythonfil ligger i. Sedan lägger ni till raden

import med

högst upp i er python-kod. Nu kan ni beräkna Levenshtein-avståndet mellan två strängar i er kod genom att anropa med.minimum_edit_distance() med de två strängar ni vill räkna på som argument:

# skriv ut redigeringsavståndet mellan kisse och katt
print(med.minimum_edit_distance('kisse', 'katt'))

# ovanstående kommer skriva ut följande strängen "4", dvs att fyra redigeringar
# behövs för att ändra strängen "kisse" till strängen "katt"

Om ni har tid och är intresserade kan ni uttöka er lösning till något av följande:

• Kombinera redigeringsavståndsdata med frekvensdata för att välja förslag.
• Hitta möjliga kandidater till rättstavning även bland ord som är längre eller kortare än det användaren skrev.
• Kombinera autocorrect med autocomplete.

OBS! Ingen av de ovanstående förfinade varianterna krävs för att få godkänt, utan är endast exempel på möjlig fortsatt utveckling.