Sist endret: 23.09.2016  
 

Praksisoppgave - Kobra lærer å stave

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 02.10.2017 15:00

Velg språk:
- Python
- Java

Løsningsforslag

Følgende filer er tilgjengelige etter at fristen har gått ut:
ordbok.py, ordbok_tweak.py

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
ordbok.py Funksjonene bygg(ordliste) og posisjoner(ord, strukt)
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt output_eksempel_01.txt

Oppgave

Du skal lage et program for å finne ord i en tekst. For å gjøre dette, kan du lage en funksjon som bygger et tre og en funksjon som bruker treet til å søke. Første linje av input til programmet er en streng som består av tegnene [a-z] og mellomrom. Dette representerer dokumentet det skal søkes i. De neste linjene i input er spørringer etter ord. Programmet skal søke etter disse ordene i teksten, og returnere hvilke posisjoner ordet finnes på. Tegnet ? brukes til å angi at her kan det stå en hvilket som helst bokstav fra alfabetet [a-z].

En måte å løse denne oppgaven på er å putte ordene inn i et tre, hvor hver bokstav i ordet tilsvarer en peker til neste node. Nedenfor ser du treet for setningen ha ha mons har en hund med moms hun er en hunn. Legg merke til at noen av nodene inne i treet tilsvarer slutten på ord, mens andre ikke gjør det. Legg også merke til at noen ord finnes på flere steder i dokumentet.

Funksjonen posisjoner(ord, indeks, node) som skal returnerer posisjonene til alle treff på ord i trestrukturen med rot node. indeks sier hvor langt i ordet vi har kommet. For å finne disse posisjonene kan den bruke rekursjon. Å bruke rekursjon vil si å utføre rekursive kall. Et kall til funksjonen selv er et rekursivt kall. Rekursjon brukes som regel til å dele opp et problem i mindre deler, for deretter å sette sammen løsningene. I dette problemet er det ordene som inneholder ? som kan gi flere delproblemer. Når du ser ? skal du kalle posisjoner én gang for alle mulige erstatninger for ? med de tilhørende delene av treet.

ordtre.png

Output fra programmet ditt skal være søkeuttrykk: pos1 pos2 ... posN, som vist i eksempel-output. Posisjonene skal være sortert stigende. Dette gjøres allerede i den utdelte koden.

I rammeverket er det brukt dictionaries. En dict i Python er omtrent det samme som en HashMap Java, man kan lagre verdier assosiert med nøkler, og hente dem ut igjen, i konstant tid Θ(1) (i gjennomsnitt). Forskjellen fra vanlige arrays, hvor nøklene er indekser, kan nøklene i en dict være hva som helst, og du er ikke avhengig av at de er i et lite verdiområde.

Eksempel på bruk av dict:

>>> d = {} 
>>> d['a'] = 1
>>> d['b'] = 2
>>> if 'b' in d:
...     print d['b']
... 
2
>>> d[42] = 'mjau'
>>> print d.keys()
['a', 42, 'b']
>>> print d.values()
[1, 'mjau', 2]
>>> print d.items()
[('a', 1), (42, 'mjau'), ('b', 2)]

Rammeverk

#!/usr/bin/python3

from sys import stdin, stderr
import traceback


class Node:
    def __init__(self):
        self.barn = {}
        self.posi = []


def bygg(ordliste):
    # SKRIV DIN KODE HER


def posisjoner(ord, indeks, node):
    # SKRIV DIN KODE HER


def main():
    try:
        ord = stdin.readline().split()
        ordliste = []
        pos = 0
        for o in ord:
            ordliste.append((o, pos))
            pos += len(o) + 1
        toppnode = bygg(ordliste)
        for sokeord in stdin:
            sokeord = sokeord.strip()
            print("%s:" % sokeord, end='')
            posi = posisjoner(sokeord, 0, toppnode)
            posi.sort()
            for p in posi:
                print(" %s" % p, end='')
            print()
    except:
        traceback.print_exc(file=stderr)


if __name__ == "__main__":
    main()

Variabelbeskrivelse

Rammeverket oppretter en nodeklasse for deg med folgende egenskaper:
barn - en liste med alle nodebarna til noden (noder direkte underlagt noden du staar i)
posi - en liste over indeksene hvor ordet begynner i tekststrengen (inputet)

Andre variable:
'ordliste' - en liste med tupler. Tuplene er paa folgende form: (ord, posisj), og det er et tuppel for hvert ord i input. Merk at for ord som forekommer flere ganger vil det vaere flere tupler, et tuppel for hver forekomst. For eksempel baade ("ha", 0) og ("ha", 3) for eksempel-input.
'ord' - et enkelt ord, for eksempel "ha".
'indeks' - sier hvor langt i ordet vi har kommet i soket, og er altsaa et tall.
'node' - er rotnoden til treet du skal soke gjennom.

Dersom du fortsatt er usikker paa de ulike variablene, kan det vaere greit aa printe de og se hva de faktisk inneholder.

Input-eksempel

ha ha mons har en hund med moms hun er en hunn
ha
mjau
m?d
e?

Tilhørende output

ha: 0 3
mjau:
m?d: 23
e?: 15 36 39

Hvordan teste Python-program

Unix

Du kan teste programmet ditt med kommandoen:

    python program.py < input.txt

Windows

  • Lagre programmet ditt på feks m:\tdt4120\
  • Åpne kommandolinje (Start -> Kjør -> cmd)
    • m:
    • cd \tdt4120
    • python.exe program.py < input.txt
  • Merk at hvis du bare skriver "python", ikke "python.exe", ser det ut til ofte å oppstå en feil fordi python prøver å kjøre inputfilen også.

Godbit

Bit 1: Ofte er du interessert i å søke etter uttrykk med ukjente delstrenger, hvor du ikke vet lengden på delstrengen. La * representere fra 0 til uendelig mange bokstaver. En spørring som *e* i eksemplet skal da gi treff på ordene en, er og med. Modifiser søkefunksjonen din til å kunne søke etter slike uttrykk.