Exemples

Aquesta lliçó presenta dos exemples d’ús de diccionaris: En el primer exemple, es vol comptar quantes vegades apareix cada paraula d’un text. Al segon exemple es mostra com construir i consultar un índex per cercar eficientment els documents que conten una certa paraula.

Exemple: Comptar totes les paraules d’un text

Considerem que, donat un text, volem obtenir la llista de totes les seves paraules (en minúscules), juntament amb el seu nombre d’aparicions.

Una bona forma de fer-ho és utilitzant un diccionari. El diccionari tindrà com a claus les paraules del text (en minúscules). I cada paraula tindrà associada com a valor un enter que és el nombre de vegades que aquella paraula ha aparegut en el text. Un diccionari ocurrencies com aquest es declara doncs així:

ocurrencies: dict[str, int]

Començant per un diccionari buit, anirem llegint seqüencialment cada paraula del text. Per a cada paraula paraula, si paraula no era encara al diccionari, l’afegirem associant-li el comptador 1 (perquè, al ser nova, només ha aparegut un cop). En canvi, si paraula ja era al diccionari, li incrementarem d’una unitat el seu comptador d’ocurrències associat. Un cop llegit tot el text, recorrerem tots els elements del diccionari, escrivint cada clau i comptador. El programa corresponent queda doncs així:

from yogi import tokens

# crear el diccionari comptador d'ocurrències de paraules buit
ocurrencies: dict[str, int] = {}

# llegir cada paraula i afegir-la al diccionari
for paraula in tokens(str):
    paraula = paraula.lower()
    if paraula not in ocurrencies:
        ocurrencies[paraula] = 1
    else:
        ocurrencies[paraula] += 1

# recórrer els elements del diccionari per escriure'ls
for paraula, comptador in ocurrencies.items():
    print(paraula, comptador)

Per exemple, si executem aquest programa sobre aquesta entrada

I'm saying nothing
But I'm saying nothing with feel

el resultat és

i'm 2
saying 2
nothing 2
but 1
with 1
feel 1

Recordeu que (des de Python 3.6) l’ordre en què es recorren els elements d’un diccionari és el seu ordre d’inserció. Per tal que les paraules quedin ordenades alfabèticament, es pot utilitzar la funció predefinida sorted que les ordena per clau:

for paraula in sorted(ocurrencies.items()):
    print(paraula, ocurrencies[paraula])

Així, el resultat és ara:

but 1
feel 1
i'm 2
nothing 2
saying 2
with 1

Per tal que les paraules quedin ordenades per ocurrències primer, alfabèticament segon, es poden passar més paràmetres a sorted indicant la tupla que determina el criteri per ordenar (ignoreu el lambda per ara):

for paraula, comptador in sorted(ocurrencies.items(), key=lambda x: (x[1], x[0])):
    print(comptador, paraula)

Així, el resultat és ara:

1 but
1 feel
1 with
2 i'm
2 nothing
2 saying

Exemple: Indexació de documents

Suposem que volem indexar diferents documents de text de manera que, donada una paraula, puguem trobar eficientment tots els documents que continguin aquella paraula. Aquesta tasca és semblant a la que realitzen els cercadors d’Internet, o al Finder del vostre ordinador.

Per simplificar, suposem que l’entrada és una seqüència de descripcions de documents. Cada document comença amb el seu identificador, seguit del seu nombre de paraules i seguit de les seves paraules.

Per exemple, si aquests són els nostres documents

mati      8   cada dia al mati canta el gall kiririki
gegant   16   el gegant del pi ara balla ara balla el gegant del pi ara balla pel cami
nina     11   dalt del cotxe hi ha un nina que repica els picarols
balco     8   el gall i la gallina estaven al balco

preguntar per gall hauria de retornar mati i balco, no necessàriament en aquest ordre. Preguntar per cotxe hauria de retornar nina i preguntar patata no hauria de retornar res.

Per tal de no haver de llegir tots els documents cada cop que es demana una paraula, construirem un índex dels documents: Un índex és una estructura de dades que indica a quin document apareix cada paraula. La idea és semblant als índexs que al final dels llibres diuen a quines pàgines apareix cada terme important; vegeu la figura de la dreta.

En el nostre cas, podem veure que un índex és un diccionari que, donades paraules, retorna conjunts d’identificadors de documents (és a dir, de paraules). Per tant, el nostre índex tindrà aquest tipus:

Document: TypeAlias = str
Index: TypeAlias = dict[str, set[Document]]

La primera fase consisteix en construir l’índex tot llegint els documents:

def construir_index() -> Index:
    index: Index = {}
    for doc in tokens(str):
        n = read(int)
        for _ in range(n):
            par = read(str)
            if par in index:
                index[par].add(doc)
            else:
                index[par] = {doc}
    return index

Aquesta funció llegeix l’entrada document per document. Per cada document, deixa a la variable doc el seu identificador i a la variable n el seu nombre de paraules. Per a cadascuna de les n paraules par, insereix doc a l’entrada par de l’índex (mirant si és o no la primera vegada que s’afegeix). Així, a l’índex que s’acaba retornant, hi ha una entrada per a cada possible paraula de tots els documents i cada paraula conté el conjunt d’identificadors de documents que contenen aquella paraula.

Amb l’exemple anterior, l’índex retonat és aquest:

{'al': {'balco', 'mati'},
 'ara': {'gegant'},
 'balco': {'balco'},
 'balla': {'gegant'},
 'cada': {'mati'},
 'cami': {'gegant'},
 'canta': {'mati'},
 'cotxe': {'nina'},
 'dalt': {'nina'},
 'del': {'nina', 'gegant'},
 'dia': {'mati'},
 'el': {'balco', 'mati', 'gegant'},
 'els': {'nina'},
 'estaven': {'balco'},
 'gall': {'balco', 'mati'},
 'gallina': {'balco'},
 'gegant': {'gegant'},
 'ha': {'nina'},
 'hi': {'nina'},
 'i': {'balco'},
 'kiririki': {'mati'},
 'la': {'balco'},
 'mati': {'mati'},
 'nina': {'nina'},
 'pel': {'gegant'},
 'pi': {'gegant'},
 'picarols': {'nina'},
 'que': {'nina'},
 'repica': {'nina'},
 'un': {'nina'}}

La segona fase consisteix en recuperar tots els identificadors de documents que contenen una paraula donada:

def escriure_documents(index: Index, par: str) -> None:
    if par in index:
        print(f'La paraula {par} apareix en aquests documents:')
        for doc in index[par]:
            print(doc)
    else:
        print(f'La paraula {par} no apareix en cap document.')

Primer, es cerca la paraula a l’índex, amb in. Si la paraula hi és, només cal recórrer el seu valor en index[par], que és el conjunt d’identificadors de documents que cal escriure.

Per referència, aquest és el programa sencer:

from yogi import read, tokens
from typing import TypeAlias


Document: TypeAlias = str
Index: TypeAlias = dict[str, set[Document]]


def construir_index() -> Index:
    index: Index = {}
    for doc in tokens(str):
        n = read(int)
        for i in range(n):
            par = read(str)
            if par in index:
                index[par].add(doc)
            else:
                index[par] = {doc}
    return index


def escriure_documents(index: Index, par: str) -> None:
    if par in index:
        print(f'La paraula {par} apareix en aquests documents:')
        for doc in index[par]:
            print(doc)
    else:
        print(f'La paraula {par} no apareix en cap document.')

Apa! D’aquí a fer un Google només queda un petit pas… 😏




Lliçons.jutge.org
Jordi Petit
Universitat Politècnica de Catalunya, 2022

Prohibit copiar. Tots els drets reservats.
No copy allowed. All rights reserved.