Skúška 12.2.2020 - TrieMap


Implementuj asociatívne pole, v ktorom sa kľúče ukladajú do prefixového stromu (dátová štruktúra TrieMap). Kľúčmi asociatívneho poľa budú len znakové reťazce. Asociovaná hodnota sa priradí do príslušného vrcholu stromu (atribút value). Použi tieto deklarácie (z úlohového servera L.I.S.T. si stiahni kompletnú verziu skuska.py):

class TrieMap:
    class Node:
        def __init__(self):      # NEMENIT
            self.value = None
            self.child = []      # zoznam dvojic (pismeno, podstrom)

    def __init__(self):
        self.root = self.Node()
        ...

    def __setitem__(self, key, address):
        ...

    def __getitem__(self, key):
        raise KeyError

    def __len__(self):
        return 0

    def __iter__(self):
        ...

    def remove(self, address):
        ...

    def all(self, words):
        return set(), set()

    def extend(self, address, sentence):   # NEMENIT
        for word in sentence.split():
            self[word] = address

kde sa niektoré metódy správajú trochu inak, ako pri štandardnom asociatívnom poli:

  • __setitem__(key, address) pre daný kľúč pridá do množiny príslušnú hodnotu reťazca address.

    • ak kľúč obsahuje nepísmenové znaky, tak tieto ignoruje; veľké písmená prerobí na malé; kľúče, ktoré sú kratšie ako 3 písmená, ignoruje (nezaraďuje do asociatívneho poľa)

  • __getitem__(key) pre daný kľúč vráti príslušnú hodnotu, resp. vyvolá chybu KeyError, ak taký kľúč neexistuje.

    • ak kľúč obsahuje nepísmenové znaky, tak tieto ignoruje; veľké písmená prerobí na malé

  • __iter__() vráti generátor všetkých kľúčov v strome, zrejme tieto kľúče môže vrátiť v ľubovoľnom poradí.

  • extend(address, sentence) rozoberie danú vetu na slová a každé slovo pridá do asociatívneho poľa s danou hodnotou address; metóda je už naprogramovaná, nemeň ju.

    • vďaka tejto metóde, môžeme ukladať slová z nejakej webovej stránky do stromu a ku každému slovu pridať adresu stránky, kde sa toto slovo vyskytlo; takto po načítaní viacerých stránok máme pri každom slove informáciu, na ktorých stránkach sa vyskytlo

  • remove(address) prezrie všetky hodnoty v strome, keď je to množina, ktorá obsahuje zadanú hodnotu address, tak ju z tejto množiny vyhodí, ak by takto vznikla prázdna množina, tak ju nahradí hodnotou None.

  • all(words) dostáva nejakú postupnosť slov a vráti dve množiny; metóda postupne pre každé slovo z postupnosti zistí asociovanú hodnotu, ak je to nejaká množina adries, tak z takýchto množín začne vytvárať ich prienik (to bude prvá výsledná množina), ak dané slovo nemá asociovanú hodnotu (vyvolalo sa KeyError), tak toto slovo pridá do druhej výslednej množiny.

    • takže metóda vráti množinu všetkých adries, na ktorých sa vyskytli všetky slová z postupnosti, okrem tých, ktoré nie sú v strome - tieto sa uložia do druhej množiny

  • Vnorenú triedu Node nemeň (testovač aj tak použije jej pôvodnú verziu):

    • v atribúte child sa pre každý podstrom uchováva samotný znak (malé písmeno abecedy) a referencia na podstrom (typu Node)

  • Atribút root musí obsahovať koreň prefixového stromu - testovač bude tento strom kontrolovať na správnosť. Nepoužívaj žiadne ďalšie atribúty so zloženou štruktúrou (napríklad list, dict …), môžeš si zadefinovať pomocné metódy.

  • Uvedom si, že niektoré vrcholy v strome nereprezentujú kľúč a preto treba v atribúte Node.value uložiť hodnotu None. Tie vrcholy, ktoré reprezentujú nejaký kľúč, budú mať hodnotu atribútu Node.value neprázdnu množinu reťazcov, t.j. priradených adries (parameter address).

Program môžeš testovať, napríklad takto:

if __name__ == '__main__':
    m = TrieMap()
    m.extend('prvy.sk', 'python aj java su najlepsie nastroje')
    m.extend('druhy.sk', 'java mi chuti')
    m.extend('treti.sk', 'v lese som stretol python')
    m.extend('stvrty.sk', 'pouzivam nastroje ako python a ruby')
    print(len(m), *m)
    m.remove('treti.sk')
    print(len(m), *m)
    for w in m:
        print(repr(w), m[w])
    print(m.all('python, java na matfyze'.split()))
    print(m.all('javascript alebo c++'.split()))

Výpis potom bude takýto:

11 ako chuti java lese najlepsie nastroje pouzivam python ruby som stretol
8 ako chuti java najlepsie nastroje pouzivam python ruby
'ako' {'stvrty.sk'}
'chuti' {'druhy.sk'}
'java' {'prvy.sk', 'druhy.sk'}
'najlepsie' {'prvy.sk'}
'nastroje' {'prvy.sk', 'stvrty.sk'}
'pouzivam' {'stvrty.sk'}
'python' {'prvy.sk', 'stvrty.sk'}
'ruby' {'stvrty.sk'}
({'prvy.sk'}, {'na', 'matfyze'})
(set(), {'c++', 'javascript', 'alebo'})

Aby si mohol spúšťať skúškové testy, riešenie skuska.py odovzdaj na úlohový server L.I.S.T.. Testy postupne preverujú vlastnosti tvojich algoritmov, pri prvej chybe sa testovanie preruší a ďalšie časti sa netestujú.

Praktická časť končí o 11:00 a skúška ďalej pokračuje od 12:00 vyhodnotením v kancelárii m162.