9. Prefixové stromy

Trie

je stromová dátová štruktúra, v ktorej uchovávame nejakú zadanú množinu reťazcov. Predpokladáme, že v tejto množine budeme potrebovať veľmi rýchlo hľadať buď celé slová alebo ich prefixy (začiatky slov). Táto stromová štruktúra využíva to, že sa každé takto uložené slovo rozloží na písmená a táto postupnosť písmen potom tvorí cesty ku niektorým vrcholom stromu (podobne ako v strome Huffmanovho kódovania). Tejto štruktúre sa hovorí Trie (v angličtine sa číta ako slovo „try“) ale niekedy aj prefixový, písmenkový alebo znakový strom. Dá sa nájsť aj s názvom lexikografický strom.

Každý vrchol tohto stromu má toľko podstromov, koľko rôznych písmen z tohto vrcholu pokračuje. Každá takáto hrana k podstromu je označená príslušným písmenom. Najlepšie to vysvetlíme na príklade: zostrojíme trie, ktorý bude uchovávať túto množinu slov: {bear, bell, bid, bull, buy, sell, stock, stop}.

  • z koreňa stromu budú vychádzať dve hrany (dva podstromy), lebo všetky slová začínajú písmenom 'b' alebo 's':
  • jeden podstrom bude obsahovať všetky slová na 'b': {bear, bell, bid, bull, buy} a druhý slová na 's': {sell, stock, stop}
  • podstrom pre 'b' bude mať toľko synov (podstromov), koľko je rôznych druhých písmen v slovách: sú to 'e', 'i', 'u'
    • takže prvý jeho podstrom bude uchovávať slová s 'e': {bear, bell}
    • druhý slová s 'i': {bid}
    • tretí s 'u': {bull, buy}
  • podobne podstrom pre prvé písmeno 's' sa bude rozvetvovať podľa druhých písmen slov {sell, stock, stop}, teda na dva podstromy 'e', 't':
    • jeho prvý podstrom bude uchovávať slová, ktoré začínajú 's' a druhé písmeno je 'e': {sell}
    • druhý slová s druhým písmenom 't': {stock, stop}
  • takto by sme pokračovali, kým by sme nerozobrali na písmená všetky slová

Zrejme výška stromu je daná dĺžkou najdlhšieho slova, ktoré je uložené v strome, v našom prípade je to slovo 'stock', teda výška je 5. V tomto prípade všetky slová končia v listoch stromu, lebo žiadne z nich nie je prefixom nejakého iného. Toto je v niektorých aplikáciách trie podmienkou: všetky slová musia končiť v listoch stromu a teda žiadne nie je prefixom iného. Inokedy nám to nevadí a vtedy treba nejakú informáciu o tom, že nejaký vnútorný vrchol stromu je koncovým písmenkom nejakého slova. Ak by sme do tohto stromu chceli vložiť aj anglické slovo ‚be‘, museli by sme príslušný vrchol (z ktorého pokračujú zvyšné písmená pre 'bear' a 'bell') nejako označiť (atribút s príznakom konca) alebo by sme na koniec každého slova prilepili nejaký špeciálny koncový znak napr. '#'.

Vrchol prefixového stromu definujeme najčastejšie takto:

class Node:
    def __init__(self):
        self.data = None
        self.child = {}

teda každý vrchol môže obsahovať nejakú informáciu (napr. že je to koncový vrchol nejakého slova) a asociatívne pole všetkých svojich podstromov.

Vložiť nové slovo do stromu znamená:

class Trie:

    class Node:
        def __init__(self):
            self.data = None
            self.child = {}

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

    def insert(self, word, data=1):
        node = self.root
        for char in word:
            if char not in node.child:
                node.child[char] = self.Node()
            node = node.child[char]
        node.data = data

Slová do stromu pridáme napr. takto:

tr = Trie()
for slovo in 'bear bell bid bull buy sell stock stop'.split():
    tr.insert(slovo)

Dostávame takýto prefixový strom:

_images/09_1.png

Uvedomte si, že vo vrcholoch tohto stromu nie sú tie znaky, ktoré sú tu zobrazené.

Pomocou rekurzívnej funkcie vieme vygenerovať všetky uložené slová v takomto strome:

class Trie:
    ...

    def all(self, node, word=''):
        if node.data is not None:
            yield word
        for char in node.child:
            yield from self.all(node.child[char], word + char)
for slovo in tr.all(tr.root):
    print(slovo)

Vieme z toho urobiť iterátor:

class Trie:
    ...

    def __iter__(self):
        yield from self.all(self.root)

teraz môžeme získať všetky slová z tohto stromu:

print(*tr)

Vďaka prefixovému stromu vieme veľmi jednoducho získať všetky slová, ktoré majú zadaný prefix:

class Trie:
    ...

    def prefix(self, word):
        node = self.root
        for char in word:
            if char not in node.child:
                return None
            node = node.child[char]
        return self.all(node, word)

napr. pre súbor s anglickými slovami text5.txt:

with open('text5.txt') as f:
    for w in f.read().split():
        t.insert(w)
print(len(list(t)))

Vidíme, že sa vytvoril trie s 67527 slovami. Môžeme experimentovať s hľadaním všetkých slov, ktoré majú rovnaký nejaký prefix, napr.

>>> list(t.prefix('tree'))
['tree', 'treehopper', 'trees', 'treenail']
>>> list(t.prefix('trie'))
['trier', 'tried', 'triennial', 'triennium']
>>> list(t.prefix('python'))
['python', 'pythoness', 'pythonidae', 'pythoninae']

Realizácia asociatívneho poľa

Prefixový strom vieme využiťako asociatívne pole, ale musíme na to zadefinovať niekoľko metód:

  • __getitem__()
  • __setitem__()
  • __delitem__()
  • __len__()

Počet prvkov v trie by sme vedeli zistiť nejako takto:

class Trie:
    ...

    def count(self, node=None):
        if node is None:
            node = self.root
        p = node.data is not None
        for char in node.child:
            p += self.count(node.child[char])
        return p

Lenže táto metóda má zbytočne veľkú zložitosť zložitosť. Vhodnejšie by bolo použitie jedného počítadla, ktoré sa zvyšuje alebo znižuje v metódach __setitem__() a __delitem__().

Uvedomte si, že takéto asociatívne pole bude fungovať len pre kľúče znakové reťazce. Momentálne realizácia trie zisťuje, či nejaký vrchol reprezentuje koncový znak reťazca tým, že je tam hodnota rôzna od None. Lenže to znamená, že asociovaná hodnota by nemohla byť None. Aby to bola korektná realizácia asociatívneho poľa, bude treba vyriešiť aj tento problém.

Frekvenčná tabuľka

Prefixové stromy sa dajú veľmi vhodne využiť na evidovanie počtu výskytov jednotlivých slov. Vtedy samotná hodnota vo vrcholoch stromu bude označovať počet výskytov príslušného slova (ktoré skončilo v tomto vrchole).

Niekedy sa do každého vrcholu stromu vkladá ešte jedno počítadlo. Toto bude označovať počet rôznych slov, ktoré končia v celom podstrome tohto vrcholu. Zrejme, v koreni vtedy bude počet rôznych slov v celom prefixovom strome (teda len()).

Binárny trie

Zaujímavé môžu byť aj špeciálne typy trie, ktoré reprezentujú len slová zložené z dvoch typov znakov.

  • napr. {'a', 'b'}, {0, 1}
  • dostávame obyčajný binárny strom - môžeme použiť implementáciu obyčajného binárneho stromu (t.j. ľavý podstrom je pre prvé písmeno abecedy a pravý pre druhé)
  • v takomto trie môžeme ukladať aj postupnosti bitov celého čísla, t.j. bežné int

Realizácia pomocou brat/syn

Naša realizácia Trie využíva pythonovský dict - to môže byť niekedy veľký problém (napr. realizácia v inom programovacom jazyku). Z tohto dôvodu sa často používa realizácia všeobecného stromu pomocou dvoch smerníkov (referencií) v každom vrchole (v programovaní v 1. ročníku sme tomuto hovorilo „syn/brat“):

  • jedna referencia (child) je na prvého syna
  • druhá (next) na brata
  • v každom vrchole je okrem dátového atribútu (data) aj samotný symbol (resp. podreťazec)

Vrchol takéhoto stromu zapíšeme:

class Node:
    def __init__(self, char='', next=None):
        self.child = None
        self.next = next
        self.char = char
        self.data = None

Vkladanie nového slova:

def insert(self, word, data=1):
    node = self.root
    for char in word:
        node1 = node.child
        while node1 is not None and node1.char != char:
            node1 = node1.next
        if node1 is None:
            node1 = node.child = self.Node(char, node.child)
        node = node1
    node.data = data

Ten istý trie ako je zobrazený vyššie, teraz vyzerá takto:

_images/09_2.png

Uvedomte si, že vodorovné šípky označujú referenciu next. t.j. „brat“ a smerom nadol označujú child, t.j. „prvý syn“. Všetci synovia nejakého vrcholu sú vlastne všetci bratia prvého syna plus tento prvý syn.

Compressed trie

Zhustený prefixový strom - všetky vrcholy, ktoré by mali len jedného syna, sa spoja s týmto jediným synom a teda hrana nemusí označovať len jeden symbol, ale niekoľko za sebou idúcich symbolov. Predchádzajúce trie by teraz vyzeralo takto:

_images/09_3.png

Sufixový trie

Je to prefixový strom, ktorý je zložený zo všetkých „sufixov“, t.j. prípon slova, resp. slov. Napr. slovo 'abrakadabra' má tieto sufixy: 'a', 'ra', 'bra', 'abra', 'dabra', 'adabra', 'kadabra', 'akadabra', 'rakadabra', 'brakadabra', 'abrakadabra' a všetky tieto sa vložia do sufixového stromu. Sufixové trie sa využívajú hlavne na rýchle hľadanie reťazcov a podreťazcov v nejakých textoch.

Využitie

Pomocou trie by sme vedeli riešiť napríklad takýto problém:

  • spracujeme nejakú množinu webov tak, že všetky „slová“ z týchto stránok vložíme do prefixového stromu, hodnotami budú množiny stránok, kde sa tieto slová vyskytujú
  • takto dostávame dosť veľký strom, v ktorom pre každé slovo uchovávame adresy príslušných webových stránok
  • keďže tieto množiny stránok môžu byť dosť rozsiahle, uchovávať ich nemusíme v operačnej pamäti, ale napr. niekde na disku
  • keď teraz dostaneme nejakú množinu slov, vyhľadáme ich v tomto trie, urobíme prienik príslušných množín, prípadne ich ešte usporiadame podľa nejakých preferencií

Takto dostávame veľmi rýchly algoritmus, ktorý (podobne ako google) nájde všetky stránky, ktoré obsahujú všetky zadané slová.



Cvičenia

L.I.S.T.

  1. Nakresli bez počítača prefixový strom

    • pre množinu slov:

      {auto, aula, ano, body, byk, boja, balet, cop, cap, cip, cakan}
      
    • zisti, koľko je v tomto strome vnútorných vrcholov, v ktorých nekončí žiadne slovo


  1. V triede Trie z prednášky spojazdni a otestuj tieto metódy

    • insert

    • all

    • prefix

    • __iter__

    • __len__

    • môžeš ich otestovať na niektorom zo súborov: text1.txt, text2.txt, text3.txt, text4.txt, text5.txt, napr.

      t = Trie()
      with open('text2.txt', encoding='utf-8') as f:
          for w in f.read().split():
              t.insert(w)
      print(len(t))
      

  1. Do triedy Trie pridaj metódu na vykreslenie stromu.

    • metóda draw:

      class Trie:
          ...
      
          canvas = None
      
          def draw(self, node=None, char='"', width=None, x=None, y=None):
      
              def sipka(x1, y1, x2, y2, r=15, farba='black', hrubka=1):
                  d = ((x1-x2)**2+(y1-y2)**2)**.5
                  xx, yy = (x2-x1)*r/d, (y2-y1)*r/d
                  self.canvas.create_line(x1+xx, y1+yy, x2-xx, y2-yy, width=hrubka, fill=farba, arrow='last')
      
              if self.canvas is None:
                  self.canvas = tkinter.Canvas(bg='white', width=1000, height=600)
                  self.canvas.pack()
              if node is None:
                  self.canvas.delete('all')
                  node = self.root
                  if width is None: width = int(self.canvas['width'])-20
                  if x is None: x = 10
                  if y is None: y = 30
              n = len(node.child)
              x0 = x + width // 2
              if n > 0:
                  width1 = width // n
                  for i, char1 in enumerate(sorted(node.child)):
                      sipka(x0, y, x+i*width1+width1//2, y + 50)
                      #vstrede(x-width//4, y+25, 0)
                      self.draw(node.child[char1], char1, width1, x+i*width1, y + 50)
              f = 'white' if node.data is None else 'lightgray'
              self.canvas.create_oval(x0-15, y-15, x0+15, y+15, fill=f)
              self.canvas.create_text(x0, y, text=char, font='courier 12 bold')
              if node is self.root:
                  self.canvas.update()
                  self.canvas.after(500)
      
    • môžeš otestovať napr.

      t = Trie()
      for word in 'bear bell bid bull buy sell stock stop'.split():
          t.insert(word)
          t.draw()
      while word:
          word = input('zadaj slovo: ')
          t.insert(word)
          t.draw()
      

  1. Triedu Trie prerob tak, aby fungovala ako asociatívne pole. Niektoré metódy musíš prepísať:

    • __getitem__()

    • __setitem__()

    • __delitem__()

    • __repr__() - vráti reťazec v tvare {kluc: hodnota, kluc: hodnota, kluc: hodnota, ...}

    • __len__() - metóda by mala mať zložitosť O(1)

    • využi základnú triedu:

      from collections.abc import MutableMapping as MapBase
      
      class TrieMap(MapBase):
          ...
      
    • toto asociatívne pole otestuj freknečnou tabuľkou slov z nejakého súboru, napr.

      d = {}
      for word in file.read().split():
          d[word] = d.get(word, 0) + 1
      

  1. Pôvodnú verziu Trie z (2) úlohy prerob tak, aby nepoužívala pythonovský dict, ale

    • použi namiesto toho list:

      class Trie:
      
          class Node:
              def __init__(self):
                  self.data = None
                  self.child = []
      
          def __init__(self):
              self.root = self.Node()
      
          ...
      
    • alebo realizáciu pomocou brat/syn:

      class Trie:
      
          class Node:
              def __init__(self, char='', next=None):
                  self.data = None
                  self.child = None
                  self.next = next
                  self.char = char
      
          def __init__(self):
              self.root = self.Node()
      
          ...
      
    • svoje riešenie otestuj


  1. Strom z úlohy (1) ručne prekresli do zhusteného prefixového stromu (compressed trie).
    • zisti, koľko je v tomto strome vnútorných vrcholov, v ktorých nekončí žiadne slovo


7. Domáce zadanie

L.I.S.T.

TrieMap

Implementujte 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).

Na riešenie úlohy použite deklarácie v súbore riesenie7.py z úlohového servera L.I.S.T. kde

  • __setitem__(key, value) pre daný kľúč priradí príslušnú hodnotu.
  • __getitem__(key) pre daný kľúč vráti príslušnú hodnotu, resp. vyvolá chybu KeyError, ak taký kľúč neexistuje.
  • __delitem__(key) vymaže daný kľúč (resp. vyvolá chybu KeyError), pričom zo stromu vyhodí tie vrcholy, ktoré už nemajú potomkov (asociatívne pole child je prázdne) a ani nenesú informáciu value.
  • node_count() vráti počet vrcholov (typu Node) v celom prefixovom strome: prázdny strom má tento počet 0, strom s jediným kľúčom '' má tento počet 1, strom s jediným kľúčom napr. 'a' má tento počet 2 (aj strom s dvoma kľúčmi '' a 'a' má tento počet 2), atď.
  • __iter__() vráti iterátor všetkých kľúčov v strome, zrejme tieto kľúče môže vrátiť v ľubovoľnom poradí.
  • Vnorenú triedu TrieMap.Node nemeňte (testovač aj tak použije jeho pôvodnú verziu).
  • Uvedomte si, že niektoré vrcholy v strome nereprezentujú kľúč a preto treba v atribúte Node.value uložiť nejakú informáciu tak, aby ste vedeli rozpoznať, že vo vrchole nekončí žiaden kľúč; nepoužite na to ale hodnotu None, keďže aj toto môže byť hodnotou v asociovanom poli.

Váš program môžete testovať napr. takto:

if __name__ == '__main__':
    m = TrieMap()
    for w in 'mama ma emu a ema ma mamu'.split():
        try:
            m[w] = m[w] + 1
        except KeyError:
            m[w] = 1

    print(list(m), m.node_count(), len(m))
    for w in list(m):
        del m[w]
        print(w, m.node_count(), len(m))

Výpis potom bude takýto:

['ma', 'mama', 'mamu', 'emu', 'ema', 'a'] 11 6
ma 11 5
mama 10 4
mamu 6 3
emu 5 2
ema 2 1
a 0 0

Aby ste mohli spúšťať testy, program uložte do súboru riesenie7.py. Na začiatok súboru pridajte tieto tri komentárové riadky (s vašim menom a dátumom):

# 7. zadanie: triemap
# autor: Alan Turing
# datum: 12.12.2018

Riešenie odovzdajte na úlohový server L.I.S.T. najneskôr do 23:00 21. decembra. Môžete zaň získať 10 bodov.



© Copyright 2018-2019, Andrej Blaho.
Naposledy aktualizované 14. feb. 2019.
Vytvorené pomocou Sphinx 1.8.4.

Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.