Göm meny

Temauppgift 2

Nyckelbegrepp

while-loop, variabel, villkor, filläsning, lista, sträng

Inlärningsmål

Syftet med temauppgiften är att ge ett exempel på en praktisk implementation i programmeringsspråket Python. Temauppgiften kopplar följande kursmål:

Efter avslutad kurs ska den studerande kunna:

  • förklara vad ett program är och hur ett program fungerar
  • förklara programkod de själva och andra på kursen skrivit
  • använda grundläggande datatyper/datastrukturer och styrstrukturer för att skriva enklare program

Muntlig redovisning

Temauppgiften redovisas vid särskilt redovisningstillfälle, se deadlines.

Komplettering

Missad redovisning kompletteras genom att skicka in en screencast där du demonstrerar ditt program och svarar på de frågor som finns i slutet av denna sida.

Du behöver inte redigera screencasten på något speciellt sätt. Se bara till att det du vill visa syns, samt att din röst hörs. Screencasten får vara max 5 minuter lång.

Temauppgift 2 - Autocomplete

I den här temauppgiften ska ni få skriva en autocomplete-funktion i programmeringsspråket Python. En autocomplete-funktion utgår från vad användaren börjat att skriva och förutspår resten av ordet. Funktionen kan förstås göras i princip hur enkel eller sofistikerad som helst. Den absolut enklaste formen kanske jämför indata mot en ordlista och returnerar det “första bästa”, medan en mer avancerad metod tar hänsyn till hur vanligt förekommande ordet är, eller vilka ord användaren har skrivit tidigare.

I den här temauppgiften kommer ni att skriva koden i en texteditor och köra den i terminalen.

Spara ned labbskelettet nedan på lämplig plats i er hemkatalog.

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

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

main()

Till er hjälp har ni en liten samling ord- och frekvensfiler i olika konstellationer och filformat. Korpusfilerna finns i ~729G74/kursmaterial/temauppgift2/.

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.

Instruktioner

Fundera först på vilken strategi ni vill implementera. Ni kan exempelvis låta er funktion returnera det första bästa ordet som börjar på rätt bokstäver, eller låta den returnera en uppsättning förslag som användaren får välja mellan.

Skriv sedan klart funktionen autocomplete() ovan så att den förutsäger slutet på ett inmatat ord enligt er valda strategi.

En körning kan exempelvis se ut så här:

Type word: bast
Autocompletion finished:  bastu
Type word: enhö
Autocompletion finished:  enhörning
Type word: fik
Autocompletion finished:  fiktiv
Type word: programmer
Autocompletion finished:  programmering

För VG

För VG ska er funktion även använda sig av ytterligare resurser, det vill säga frekvensinformationen alternativt en funktion som beräknar Levenshtein-avståndet mellan två ord.

Dokumentera i funktionskommentaren hur ni tänkt. Funktionskommentarer skriver man genom att med början på raden direkt efter funktionshuvudet lägga till en kommentar 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 word_list.
    
    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
    ...

VG-alternativ 1

Kombinera korpusfilen och dess motsvarande frekvensfil för att returnera förslag med högst frekvens.

VG-alternativ 2

Kombinera korpusfilen och algoritmen för att beräkna minsta editeringsavstådet.

Till er hjälp har ni en funktion som beräknar Levenshtein-avståndet mellan två strängar (ord), d.v.s. hur många redigerande steg (raderingar, infogningar och substitueringar av tecken) som krävs för att transformera ett ord till ett annat.

För att kunna använda funktionen för beräkning av Levenshtein-avståndet kan ni använda en färdig funktion som finns implementerad i filen ~729G74/kursmaterial/temauppgift2/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 anropa med.minimumEditDistance() med de två strängar ni vill räkna på som inargument:

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

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

Frågor

Följande frågor ska kunna besvaras efter genomförd uppgift:

  • Vilken strategi valde ni? Beskriv den.
  • Förklara hur inläsningen av ordlistan går till.
  • Förklara hur er strategi är implementerad. Var i koden görs vad?
  • Vilka alternativa strategier skulle ni kunnat välja?

Sidansvarig: Jody Foo
Senast uppdaterad: 2017-10-27