4. Rječnici

Rječnici (Associative array), u drugim programskim jezicima ponekad zvani hash tablice (Hash table), drugi su složeni tip podataka koji upoznajemo. Za razliku od listi koje predstavljaju sekvencu vrijednosti, rječnici predstavljaju skup uređenih parova (ključ, vrijednost). Korisnost rječnika sastoji se u tome da se vrijednosti pohranjene pod nekim ključem dohvaćaju u konstantnom vremenu, tj. da veličina rječnika ne utječne na vrijeme dohvaćanja vrijednosti. S druge strane, da koristimo listu za vrijednosti koje moramo dohvaćati, vrijeme potrebno za dohvaćanje bilo bi vremenski linearne kompleksnosti, odnosno za dvostruko veću listu trebali bi u pravilu i dvostruko više vremena.

Ograničenje koje rječnici imaju jest da ključevi mogu biti samo nepromjenjivi tipovi podataka, dok vrijednosti mogu biti bilo koji tip podataka. Ključ je jedinstven, tako da se u rječniku ne može ponavljati.

Rječnik inicijaliziramo na sljedeći način:


In [24]:
rjecnik={}

Varijabla rjecnik je prazan rječnik, odnosno ne sadrži ni jedan uređeni par (ključ : vrijednost).

U sljedećem primjeru stvorili smo rječnik s dva uređena para:


In [25]:
rjecnik={'a':5, 'b':3.8}

Varijabla rjecnik sadrži u dva uređena para. Prvi uređeni par je 'a':5, gdje je ključ 'a', a vrijednost 5. Drugi uređeni par je 'b':3.8, gdje je ključ 'b', a vrijednost 3.8.

Nad rječnicima može se koristiti funkcija len() koja računa broj uređenih parova u rječniku:


In [26]:
rjecnik={'a':5, 'b':3.8}
len(rjecnik)


Out[26]:
2

Rječnici su promjenjivi tipovi podataka tako da se njihov sadržaj naknadno može i mijenjati. Ako želimo promijeniti vrijednost postojećeg ključa, to možemo napraviti na sljedeći način:


In [27]:
rjecnik={'a':5, 'b':3.8}
rjecnik['b']=9
print rjecnik


{'a': 5, 'b': 9}

Sintaksa rada s rječnicima slična je one s listama, jedino što se umjesto indeksa u listi u uglatoj zagradi definira ključ. Iz primjera je također vidljivo da u rječniku ne možemo imati dva ista ključa. Pridruživanjem druge vrijednosti pod postojeći ključ brišemo prethodnu vrijednost pod tim ključem.

Vrijednosti iz rječnika možemo dohvatiti na dva načina. Prvi je definiranjem ključa u uglatoj zagradi:


In [28]:
print rjecnik['a']


5

Ako na ovaj način dohvaćamo vrijednost ključa koji ne postoji u rječniku, javit će se pogreška KeyError, koja nas i upućuje da je pogreška u nazivu ključa:


In [29]:
rjecnik={'a':5, 'b':3.8}
print rjecnik['c']


---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-29-b8fd267317a0> in <module>()
      1 rjecnik={'a':5, 'b':3.8}
----> 2 print rjecnik['c']

KeyError: 'c'

Drugi način dohvaćanja vrijednosti iz ključa je metodom get():


In [30]:
rjecnik={'a':5, 'b':3.8}
print rjecnik.get('a')


5

Ako pak na ovaj način dohvaćamo vrijednost ključa koji ne postoji u rječniku, dobit ćemo vrijednost None:


In [31]:
rjecnik={'a':5, 'b':3.8}
print rjecnik.get('c')


None

Budući da nećemo uvijek znati postoji li neki ključ u rječniku, najsigurnije dohvaćanje vrijednosti je pomoću metode get().

Sintaksa ove metode je rjecnik.get(key[,default]). Metoda prima jedan obavezni argument i jedan opcionalni. Prvi argument key je obavezan argument koji sadrži ključ. Drugi argument default je opcionalni argument koji predstavlja vrijednost koja se vraća u slučaju ako ključ ne postoji u rječniku. Pretpostavljena vrijednost drugog argumenta je None.

U sljedećem primjeru možemo pretpostaviti da će vrijednost drugog argumenta metode get() biti 0, ako ključ ne postoji u rječniku:


In [32]:
rjecnik={'a':5, 'b':3.8}
print rjecnik.get('c',0)


0

Pri statističkoj analizi i modeliranju teksta, rječnike ćemo koristiti za prebrojavanje raznih događaja u tekstu. Zato nam je vrlo važan postupak koji za neki ključ vrijednost povećavamo za 1. Za to ćemo koristiti sljedeću naredbu:


In [33]:
rjecnik={'a':5, 'b':3.8}
rjecnik['c']=rjecnik.get('c',0)+1
print rjecnik.get('c')


1

U rječniku pod određenim ključem pohranjujemo dosadašnju vrijednost pod tim ključem, ili 0 uvećanu za 1. U našem slučaju, po izvršavanju ove naredbe pod ključem će biti pohranjena vrijednost 1. Kada bi ponovno pokrenuli naredbu, pod ključem bi pohranjena bila vrijednost 2. Što ćemo redovito raditi jest prolaženje kroz sekvencu događaja u tekstu (znakova, nizova znakova – tzv. n-grafa, riječi, nizova riječi – tzv. n-grama) te u rječniku bilježiti koliko smo puta susreli određeni događaj.

Pogledajmo primjer u kojem prebrojavamo koliko smo puta vidjeli određeni znak u nizu znakova:


In [34]:
rjecnik={}
niz='otorinolaringologija'
for znak in niz:
    rjecnik[znak]=rjecnik.get(znak,0)+1
print rjecnik


{'a': 2, 'g': 2, 'i': 3, 'j': 1, 'l': 2, 'o': 5, 'n': 2, 'r': 2, 't': 1}

Pogledajmo kako možemo iterirati kroz rječnik. Do sada smo iterirali kroz niz znakova (znamo da time prolazimo kroz svaki znak tog niza), listu (prolazimo kroz svaki element liste) te datoteku (prolazimo kroz svaki red datoteke). Kada iteriramo kroz rječnik, prolazimo kroz sve ključeve tog rječnika. Ponavljamo: rječnik predstavlja SKUP uređenih parova, odnosno ne možemo očekivati nikakav eksplicitan poredak tih ključeva.

U sljedećem primjeru iteriramo kroz rječnik:


In [35]:
rjecnik={'a':5, 'b':3.8, 'c':1}
for kljuc in rjecnik:
    print 'ključ '+kljuc+' ima vrijednost '+str(rjecnik[kljuc])


ključ a ima vrijednost 5
ključ c ima vrijednost 1
ključ b ima vrijednost 3.8

Iz ovog primjera je vidljivo da poredak uređenih parova nije definiran, jer se radi o skupu.

Prisjetimo se i operatora in koji je na nizu znakova provjeravao je li podniz znakova sadržan u nizu znakova, odnosno na listi je li neka vrijednost element te liste. Nad rječnicima operator in provjerava je li neka vrijednost ključa u tom rječniku:


In [38]:
rjecnik={'a':5, 'b':3.8, 'c':1}
'a' in rjecnik


Out[38]:
True

In [39]:
rjecnik={'a':5, 'b':3.8, 'c':1}
'd' in rjecnik


Out[39]:
False

Upoznajmo još tri metode nad rječnicima - keys() za dohvaćanje svih ključeva rječnika, values() za dohvaćanje svih vrijednosti te items() za dohvaćanje svih parova (ključ, vrijednost):


In [40]:
rjecnik={'a':5, 'b':3.8, 'c':1}
print rjecnik.keys()
print rjecnik.values()
print rjecnik.items()


['a', 'c', 'b']
[5, 1, 3.8]
[('a', 5), ('c', 1), ('b', 3.8)]

Iz primjera je vidljivo da metode keys() i values() vraćaju listu čiji elementi liste su ključevi ili vrijednosti. Metoda items() vraća listu parova ne u uglatim, već u oblim zagradama. Ta metoda, naime, vraća listu n-torki. N-torke su tip podataka koji tek sada po prvi put susrećemo. N-torke su nepromjenjivi pandan promjenjivim listama te ćemo ih koristiti nešto kasnije, kada ćemo u rječnike pod ključevima htjeti bilježiti sekvencu riječi. Prisjetimo se, rječnici kao ključeve primaju samo nepromjenjive tipove podataka.

Za kraj, pogledajmo kako možemo sortirati rječnik, i to prema vrijednostima silazno. Kako ćemo rječnik koristiti za prebrojavanje događaja, sortiranje rječnika prema vrijednosti bit će nam potrebno za uvid u najčešće događaje.


In [41]:
rjecnik={'a':5, 'b':3.8, 'c':1, 'd':10, 'e':2}
sorted(rjecnik.items(),key=lambda x:-x[1])


Out[41]:
[('d', 10), ('a', 5), ('b', 3.8), ('e', 2), ('c', 1)]

Ovdje koristimo funkciju sorted() nad rezultatom metode items() koja vraća listu parova (ključ, vrijednost) iz rječnika. Sam rječnik, naravno, kako se kod njega radi o skupu uređenih parova, nije moguće sortirati. Najzbunjujućiji dio ove naredbe vjerojatno je argument key kojime se definira ključ sortiranja. Za početak, ovdje vidite primjer kako u Pythonu možete definirati neki od opcionalnih argumenata na ranijem mjestu nego što to nalaže sintaksa funkcije ili metode: navođenjem imena argumenta. Nadalje, vrijednost argumenta key je zapravo funkcija u skraćenoj, tzv. lambda notaciji koja kaže da svaki element sortiranja x treba doživjeti kao njegov drugi element s promijenjenim predznakom. Pogađate da time kriterij sortiranja postaje vrijednost rječnika, tj. frekvencija kojoj je promijenjen predznak. Time rječnik, tj. listu nastalu iz rječnika sortiramo prema vrijednosti unazadno.

Zadatke možete naći ovdje: Zadaci