Stiskanje besedil
Imamo niz "stavek ki to ni ker stavek ni kar to ni". Če si pripravimo slovar besed, recimo, {"ni": 3, "ker": 4, "kar": 5, "stavek": 0, "ki": 1, "to": 2}, lahko stisnemo niz v seznam [0, 1, 2, 3, 4, 0, 3, 5, 2, 3]. Vsaka beseda v nizu je nadomeščena s pripadajočo vrednostjo iz slovarja.
Testi
Za oceno 6
Napiši funkcijo slovar_besed(besedilo), ki sestavi slovar besed, ki se pojavijo v gornjem besedilu. Vsaki besedi je dodeljen indeks; beseda, ki se pojavi prej, ima nižji indeks. (Torej: prva beseda ima indeks 0 in vsaka naslednja beseda, ki se še ni pojavila, dobi prvi prosti indeks.)
>>> slovar_besed("stavek ki to ni ker stavek ni kar to ni")
{"stavek": 0, "ki": 1, "to": 2, "ni": 3, "ker": 4, "kar": 5}
Napiši funkcijo stisni_besedilo, ki prejme besedilo (v obliki niza) in slovar, ki pove, v katero številko se preslika katera beseda. Funkcija naj vrne seznam števil, v katere se preslikajo besede.
>>> stisni_besedilo(
"stavek ki to ni ker stavek ni kar to ni",
{"beseda": 0, "ki": 1, "to": 2, "ni": 3, "ker": 4, "kar": 5, "stavek": 6})
[6, 1, 2, 3, 4, 6, 3, 5, 2, 3]
Rešitev
Za prvo nalogo razbijemo besedilo na besede, gremo čeznje in jih vnašamo v slovar. Če naletimo na besedo, ki je že v slovarju, je ne dodajamo ponovno, tako da obdrži stari indeks.
def slovar_besed(besedilo):
slovar = {}
indeks = 0
for beseda in besedilo.split():
if beseda not in slovar:
slovar[beseda] = indeks
indeks += 1
return slovar
Nato odkrijemo, da pravzaprav ne potrebujemo spremenljivke indeks, saj je njena vrednost vedno enaka številu besed v slovarju. Kar je logično: prva beseda, ki jo dodamo, dobi indeks 0, druga 1 in tako naprej.
def slovar_besed(besedilo):
slovar = {}
for beseda in besedilo.split():
if beseda not in slovar:
slovar[beseda] = len(slovar)
return slovar
Potem pa se spomnimo še metode setdefault. Ta vpiše vrednost v slovar le, če ta ključ še ne obstaja. Če že obstaja, jo pusti pri miru. Točno to, kar potrebujemo tu.
def slovar_besed(besedilo):
slovar = {}
for beseda in besedilo.split():
slovar.setdefault(beseda, len(slovar))
return slovar
Stiskanje besedila je še preprostejše: sestavimo nov seznam in vanj zlagamo indekse besed, ki jih dobimo iz slovarja.
def stisni_besedilo(besedilo, slovar):
stisnjeno = []
for beseda in besedilo.split():
stisnjeno.append(slovar[beseda])
return stisnjeno
V takih trenutkih se spomnim Srečka Kosovela: "Vsi bodo dosegli svoj cilj, le jaz ga ne bom dosegel." Vseh študentov ne bom izgleda nikoli prepričal, da je spodnji program daljši in počasnejši (na dolge razdalje).
def stisni_besedilo(besedilo, slovar):
stisnjeno = []
for beseda in besedilo.split():
for beseda1, indeks in slovar.items(): # ne počni tega!!!
if beseda1 == beseda:
stisnjeno.append(indeks)
return stisnjeno
Takšnih rešitev domače naloge sem videl veliko, kljub vsemu prigovarjanju na predavanjih. Tisto, kar počneta notranji for in if, ki je v njem, je nepotrebno. Slovarji so namenjeni prav temu, da nam tega ne bi bilo potrebno početi. In za razliko od tega programa v Pythonu, ki preišče ves slovar in je tem počasnejši, čim daljši je slovar, znajo slovarji iskati ključe zelo zelo hitro in ne postanejo nič počasnejši, ko se povečajo. Pa še -- vsaka nepotrebna vrstica programa je priložnost več za napako.
Za oceno 7
Napiši funkcijo obrni_slovar(slovar), ki prejme slovar, kot ga imamo v prejšnjih nalogah. Vrne seznam, v katerem je vsaka beseda na tistem mestu, na katerem je vrednost, ki ji pripada v slovarju. Predpostaviti smeš, da med številkami, ki pripadajo besedam, ni "lukenj": če neki besedi pripada številka 4, obstajajo tudi besede, ki jim pripadajo številke 0, 1, 2, in 3.
>>> obrni_slovar({"dva": 1, "ena": 0, "tri": 2})
["ena", "dva", "tri"]
)
Napiši funkcijo raztegni_besedilo(besedilo, slovar), ki prejme besedilo v obliki seznama števil (kot ga vrne funkcija stisni_besedilo) in slovar, ki pove, kateri besedi pripada katera številka. Funkcija vrne besedilo v obliki niza.
>>> raztegni_besedilo(
[6, 1, 2, 3, 4, 6, 3, 5, 2, 3],
{"beseda": 0, "ki": 1, "to": 2, "ni": 3, "ker": 4, "kar": 5, "stavek": 6})
"stavek ki to ni ker stavek ni kar to ni",
Rešitev
Slovar najpreprosteje obrnemo tako, da pripravimo seznam praznih nizov, potem pa gremo čez slovar in na ustrezna mesta pišemo besede.
def obrni_slovar(slovar):
tabela = [""] * len(slovar)
for beseda, indeks in slovar.items():
tabela[indeks] = beseda
return tabela
Poleg tega trika je omembe vredno le še, kako sestavimo seznam praznih nizov: [""] * len(slovar). Sezname lahko, kot vemo, pomnožimo s pozitivnim celim številom, pa dobimo isto, kot če bi ta seznam tolikokrat prišteli k samemu sebi.
Manj elegantna rešitev je takšna:
def obrni_slovar(slovar):
obrnjen = {}
for beseda, indeks in slovar.items():
obrnjen[indeks] = beseda
tabela = []
for indeks in range(len(slovar)):
tabela.append(obrnjen[indeks])
return tabela
V prvem delu funkcije pripravimo obrnjen slovar - vrednosti iz podanega slovarja postanejo ključi in obratno, {"stavek": 0, "ki": 1, "to": 2, "ni": 3, spremenimo v {0: "stavek", 1: "ki", 2: "to", 3: "ni"}. Takšen slovar lahko potem uporabimo za pretvarjanje iz indeksov v besede.
V drugem delu funkcije gremo prek vseh indeksov od 0 do kolikor je treba in v tabelo dodajamo besede, ki pripadajo tem indeksom.
Za raztegovanje besedila obrnemo slovar, zložimo besede v seznam in jih združimo z join.
def raztegni_besedilo(stisnjeno_besedilo, slovar):
obrnjen = obrni_slovar(slovar)
besedilo = []
for indeks in stisnjeno_besedilo:
besedilo.append(obrnjen[indeks])
return " ".join(besedilo)
Metoda join je prikladna, ker se nam na ta način ni potrebno boriti s presledki. Tisti, ki so namesto tega sami sestavljali niz, tako da so imeli v začetku funkcije besedilo = "" in v zanki besedilo += obrnjen[indeks] + " ", so morali na koncu funkcije odbiti odvečni presledek.
Zakaj je naloga zahtevala, naj obrni_slovar vrne seznam in ne slovarja - takšnega, kot smo ga sestavili v prvem delu druge različice te funkcije? Prednost slovarja je v tem, da hitro išče vrednosti, ki pripadajo določenim ključem. Kadar so ključi cela števila od 0 do določenega števila, pa je seznam enako hiter (oziroma celo malenkost hitrejši), pa še manj pomnilnika porabi. No, predvsem pa je to naredilo nalogo zanimivejšo. :)
Ocena 8
Napiši funkcijo razbij_besedilo(besedilo), ki prejme niz in vrne seznam besed in znakov v tem besedilu. Vsaka beseda (zaporedje črk) v nizu, postane en element slovarja. Vsak drug znak (vključno s presledki), pa je v slovarju kot posamičen element. Glej spodnji zgled.
>>> razbij_besedilo("Stavek - čudna reč, ti stavki!")
["Stavek", " ", "-", " ", "čudna", " ", "reč", ",", " ", "ti", " ", "stavki", "!"],
Rešitev
Tole je bila najbrž najtežja naloga. No, kakor za koga: ostale zahtevajo, da znamo pravilno plesati s slovarji in seznami, ta pa je eno zoprno sestavljanje zank in pogojev.
Rešitev, ki sem jo pričakoval od študentov, je takšna.
def razbij_besedilo(besedilo):
besede = []
beseda = ""
for crka in besedilo:
if crka.isalpha():
beseda += crka
else:
if beseda:
besede.append(beseda)
beseda = ""
besede.append(crka)
if beseda:
besede.append(beseda)
return besede
V seznam besede očitno nabiramo beseda, beseda pa je beseda, ki jo trenutno sestavljamo in je v začetku prazna.
Z zanko gremo čez celotno besedilo. Ko vidimo črko, jo preprosto dodamo v beseda. Če nimamo črke, pa v seznam dodamo trenutno nabrano besedo (če ni prazna!) in jo z beseda = "" pobrišemo, tako da bomo prihodnjič nadaljevali od začetka. Nato v seznam dodamo še črko.
Po koncu zanke moramo preveriti še, ali trenutno sestavljane besede še nismo dodali v seznam. Če je tako, jo seveda dodamo.
Rešitev je preprostejša, če se izognemo spremenljivki beseda in spreminjamo kar zadnjo besedo seznama.
def razbij_besedilo(besedilo):
besede = []
for crka in besedilo:
if crka.isalpha() and besede and besede[-1][-1].isalpha():
besede[-1] += crka
else:
besede.append(crka)
return besede
Prvi pogoj določa, kdaj bomo dopolnjevali zadnjo besedo: če imamo opraviti s črko in seznam besed ni prazen in je tudi zadnji znak zadnje besede črka (ker ne dodajamo besede k znakom, ki niso črke). Namesto besede[-1][-1] bi lahko pisali tudi besede[-1][0] - elementi seznama besede, ki so besede, imajo črko tako na začetku kot na koncu, tisti ki niso besede, pa so dolgi le en znak.
Če torej smemo dodati črko k zadnji besedi, jo dodamo. Sicer v seznam dodamo trenutni znak.
Nekateri študenti so vprašali, če smejo pri reševanju uporabljati regularne izraze. Nisem jim prepovedal, priporočil pa sem, naj jih ne. Z njimi je namreč manj poučno. Rešitev naloge z njimi je namreč takšna:
import re
def razbij_besedilo(besedilo):
return re.findall("\w+|.", besedilo)
Večini študentov tale "\w*|." ne pove ničesar. Za tiste, ki regularne izraze poznajo, pa je izraz trivialen, tako da se ob takšnem reševanju naloge ne bi ničesar naučili.
Ocena 9
Napiši funkcijo stisni_pravo_besedilo(besedilo), ki prejme besedilo v obliki niza, vrne pa besedilo (v obliki seznama števil) in slovar. Besedilo razbij na "besede" s funkcijo razbij_besedilo, ki si jo napisal v prejšnji nalogi, tako da bodo tudi presledki in ločila obravnavani kot "besede".
>>> stisnjen, slovar = stisni_pravo_besedilo("To je stavek, ker - očitno - je.")
>>> stisnjen
[0, 1, 2, 1, 3, 4, 1, 5, 1, 6, 1, 7, 1, 6, 1, 2, 8]
>>> slovar
{'To': 0, ' ': 1, 'je': 2, 'stavek': 3, ',': 4, 'ker': 5, '-': 6, 'očitno': 7, '.': 8}
Napiši funkcijo raztegni_pravo_besedilo(stisnjeno_besedilo, slovar), ki rezultate, ki jih vrača prejšnja funkcija, spreminja nazaj v nize.
>>> raztegni_pravo_besedilo(
[0, 1, 2, 1, 3, 4, 1, 5, 1, 6, 1, 7, 1, 6, 1, 2, 8],
{'To': 0, ' ': 1, 'je': 2, 'stavek': 3, ',': 4, 'ker': 5, '-': 6, 'očitno': 7, '.': 8})
V funkcijah za oceno 9 si žal ne bo možno kaj dosti pomagati s funkcijami za oceni 6 in 7. Pač pa vam utegne priti prav, če veste, da ima niz metodo isalpha(), ki vrne True, če so vsi znaki niza črke (ne pa ločila, presledki ali podobno). Metoda je uporabna predvsem za nize, ki so dolgi en znak.
Rešitev
V funkciji stisni_pravo_besedilo ne moremo uporabiti funkcije slovar_besed, ker le-ta pričakuje niz s celotnim besedilom, ki ga sama razkosa z metodo split, kar tu ni dobro.
To, da ne moremo uporabiti funkcije iz prejšnje naloge, nekoliko ruši eleganco domače naloge, vendar tega nisem popravljal (čeprav bi očitno lahko, pač tako, da bi spremenil navodila za slovar_besed), ker se mi je zdelo čisto zanimivo, da študent sam naleti na to težavo in uvidi, da je nerešljiva. :)
Sploh pa je sestavljanje slovarja tako preprosto, da to uredimo mimogrede.
def stisni_pravo_besedilo(besedilo):
po_besedah = razbij_besedilo(besedilo)
slovar = {}
stisnjeno = []
for beseda in po_besedah:
slovar.setdefault(beseda, len(slovar))
stisnjeno.append(slovar[beseda])
return stisnjeno, slovar
Besedilo torej razrežemo, pripravimo prazen slovar in seznam indeksov. Gremo čez besede. Vsako vpišemo v slovar, če je treba (hvala, setdefault) in v seznam dodamo ustrezni indeks. Na koncu vrnemo oboje.
Eden od študentov je poslal čuden izdelek z napako, ki je najprej nisem razumel, kasneje pa mi je potegnilo. Napisal je tole:
return (stisnjeno, "\n", slovar)
Najprej: oklepaji so tu nepotrebni in jih običajno ne pišemo, saj si tako lažje delamo utvaro, da funkcija vrača dve stvari (in ne terke z dvema stvarema). Torej:
return stisnjeno, "\n", slovar
Na moje vprašanje, čemu vrača tri stvari - stisnjeno besedilo, niz "\n" in slovar -, je odgovoril, da je mislil, da mora funkcija vrniti rezultat v dveh vrsticah. Seveda: test je takšen:
self.assertEqual(
([0, 1, 2, 1, 3, 4, 1, 5, 1, 6, 1, 7, 1, 6, 1, 2, 8],
{'To': 0, ' ': 1, 'je': 2, 'stavek': 3, ',': 4, 'ker': 5, '-': 6, 'očitno': 7, '.': 8}),
stisni_pravo_besedilo("To je stavek, ker - očitno - je.")
)
Rezultat je tu očitno v dveh vrsticah.
([0, 1, 2, 1, 3, 4, 1, 5, 1, 6, 1, 7, 1, 6, 1, 2, 8],
{'To': 0, ' ': 1, 'je': 2, 'stavek': 3, ',': 4, 'ker': 5, '-': 6, 'očitno': 7, '.': 8})
Vendar ne: to je le terka, ko smo jo v program razpisali v več vrstic, da je preglednejši. V resnici je
(1,
2)
isto kot
(1, 2)
Funkcija raztegni_pravo_besedilo je praktično enaka funkciji raztegni_besedilo, le join je drugačen.
def raztegni_pravo_besedilo(stisnjeno_besedilo, slovar):
obrnjen = obrni_slovar(slovar)
besedilo = []
for indeks in stisnjeno_besedilo:
besedilo.append(obrnjen[indeks])
return "".join(besedilo)
Ker je bila edina prednost uporabe metode join v tem, da nas je rešil sitnosti s presledki, le-teh pa tu nimamo, je vseeno, če niz sestavljamo kar sproti.
def raztegni_pravo_besedilo(stisnjeno_besedilo, slovar):
obrnjen = obrni_slovar(slovar)
besedilo = ""
for indeks in stisnjeno_besedilo:
besedilo += obrnjen[indeks]
return besedilo
Ocena 10
Recimo, da imamo slovar {"stavek": 0, "ki": 1, "to": 2, "ni": 3, "ker": 4, "kar": 5}, vendar se v besedilu pojavijo samo besede {"stavek", "to", "ni", "kar"}. Slovar bi lahko skrčili v {"stavek": 0, "to": 2, "ni": 3, "kar": 5}. Vendar to zaradi manjkajočih števil ni več veljaven slovar: potrebno je spremeniti 2 v 1, 3 v 2 in 5 v 3, medtem ko 0 ostane 0.
Napiši funkcijo poenostavi_slovar(slovar, besede), ki prejme slovar in množico besed, ki jih v resnici potrebujemo, vrne pa preslikovalno tabelo besed v obliki Pythonovega slovarja. V gornjem primeru vrne {0: 0, 2: 1, 3: 2, 5: 3}.
>>> poenostavi_slovar(
{"stavek": 0, "ki": 1, "to": 2, "ni": 3, "ker": 4, "kar": 5},
{"stavek", "to", "ni", "kar"})
{3: 2, 5: 3, 0: 0, 2: 1}
Napiši funkcijo stisni_bolj, ki prejme stisnjeno besedilo (v obliki seznama števil) in slovar. Vrne novo stisnjeno besedilo in slovar: iz slovarja so odstranjene besede, ki se v besedilu ne pojavijo, stisnjeno besedilo pa je ustrezno preštevilčeno na način, ki si ga sprogramiral v prejšnji funkciji.
V preprostem primeru spodaj je v slovarju odvečna beseda "beseda". Ta ima ravno indeks 0, tako da se vse številke le zmanjšajo za 1.
>>> stisnjeno, slovar = stisni_bolj(
[6, 1, 2, 3, 4, 6, 3, 5, 2, 3],
{"beseda": 0, "ki": 1, "to": 2, "ni": 3, "ker": 4, "kar": 5, "stavek": 6})
>>> stisnjeno
[5, 0, 1, 2, 3, 5, 2, 4, 1, 2]
>>> slovar
{"ki": 0, "to": 1, "ni": 2, "ker": 3, "kar": 4, "stavek": 5}
Rešitev
Prvi del je siten. Za vsako besedo moramo vedeti, koliko besed, ki so pred njo, smo pobrisali, da ji bomo lahko za toliko zmanjšali indeks. Nekateri študenti so napisali kar lepe rešitve, ki to znajo.
Tule bomo šli po drugačni bližnjici. Obrnili bomo slovar! Nato gremo preprosto čez vse besede v seznamu, ki predstavlja obrnjen slovar. Če je beseda med temi, ki jih moramo obdržati, dodamo mapiranje. Izvirni indeks te besede je enak indeksu v seznamu obrnjen (dobili pa bi ga lahko tudi iz slovarja slovar), novi indeks pa je - s trikom, ki smo se ga domislili v prvi funkciji za oceno 6 - kar enak dolžini mapiranja.
def poenostavi_slovar(slovar, besede):
obrnjen = obrni_slovar(slovar)
mapiranje = {}
for i, beseda in enumerate(obrnjen):
if beseda in besede:
mapiranje[i] = len(mapiranje)
return mapiranje
Tako narejena funkcija je preprosta, vendar zahteva, da se spomnimo trika.
Druga funkcija je po svoje trivialna, le daljša.
def stisni_bolj(besedilo, slovar):
besede = set()
obrnjen = obrni_slovar(slovar)
for beseda in besedilo:
besede.add(obrnjen[beseda])
mapiranje = poenostavi_slovar(slovar, besede)
novo_besedilo = []
for indeks in besedilo:
novo_besedilo.append(mapiranje[indeks])
nov_slovar = {}
for beseda, indeks in slovar.items():
if indeks in mapiranje:
nov_slovar[beseda] = mapiranje[indeks]
return novo_besedilo, nov_slovar
Najprej si pripravimo mapiranje, namreč tisto, kar vrne poenostavi_slovar. Po tem bo ostanek zelo preprost. Za poenostavi_slovar potrebujemo seznam besed, ki se pojavljajo. Do njih pridemo tako, da obrnemo slovar in naberemo v množico vse besede, ki se pojavljajo v besedilu.
Ko imamo mapiranje pa ni več kaj početi: sestavimo nov seznam indeksov in vanj zložimo mapirane indekse podanega seznama. Prav tako sestavimo nov slovar in vanj prepišemo podani slovar, pri čemer mapiramo vse vrednosti.