KRATEK OPIS

Trie je podatkovna struktura, ki se uporablja za shranjevanje besednih nizov. Poleg besednih nizov lahko v podatkovno strukturo trie shranimo tudi posamezne vrednosti (npr. starost, telefonske številke,…). Beseda trie izhaja iz besede »retrieval«, kar pomeni pridobitev, povrnitev. Podatkovno strukturo trie je izumil Edward Fredkin. Trie ima strukturo drevesa, vendar je njegova posebnost v tem, da v korenskem vozlišču ne hranimo podatkov, ampak nam to vozlišče služi samo za vzdrževanje strukture. Posebnost je tudi znak [] (EndOfKey), ki nam predstavlja konec besede. Trie je zelo učinkovit, če želimo poiskati večje število ključnih besed, če pa iščemo le nekaj besed potem raje uporabimo kakšno drugo metodo. Iskanje ključne besede je v trie hitrejše kot pri dvojiškem iskalnem drevesu.

Trie pozna tri osnovne operacije, in sicer:

• ISKANJE (ugotovimo ali se ključna beseda nahaja v trie)
  
• VSTAVLJANJE (vstavimo besedo v trie)
  
• BRISANJE (odstranimo besedo iz trie)
  

Vsi trije postopki so natančneje opisani v nadaljevanju.

Nekaj zgledov za Trie:

Zgled 1

Zgled 2

Zgled 3

Zgled 4

GRADNJA PODATKOVNE STRUKTURE TRIE

Dan imamo niz ključnih besed {alen, ana, anica, ema, robert, rok}.
Kot smo že v predstavitvi trie omenili, v korenu ne hranimo podatkov, ampak nam to vozlišče služi le za vzdrževanje strukture. Ko besedilo vstavimo dodamo zadnjemu znaku besede znak [] (EndOfKey), ki nam predstavlja konec besede. Ta znak se ne nahaja samo v listih drevesa, ampak je lahko tudi v vozlišču na sredini drevesa. Uporabimo ga lahko tudi za shranjevanje števil, kot so telefonske številke, leta,…
Na začetku bomo v trie vstavili ključno besedo alen. To storimo tako, da najprej ustvarimo koren. Koren je vedno v nivoju 0. Iz korena sledi povezava do vozlišča s prvim znakom v besedi alen in to je znak . Znak se torej nahaja v prvem nivoju drevesa. Sledi povezava v drugi nivo in vozlišče z znakom . Nato sledi povezava v tretji nivo in vozlišče z znakom . Tako smo prišli do zadnjega znaka v besedi. Vstavimo ga v trie na enak način kot predhodne znake besede ter dodamo še znak , ki predstavlja konec besede.
Tako je beseda alen vstavljena v trie.

Slika 1

Vsak nivo v trie vsebuje določen znak iz ključne besede. Koren se nahaja v nivoju 0. Prvi znak ključne besede je vedno v prvem nivoju, drugi znak v drugem nivoju, tretji znak v tretjem nivoju in tako dalje.

Prikaz nivojev na besedi alen

Naslednja beseda, ki jo vstavimo v trie je beseda ana. Pogledamo prvi znak besede in ugotovimo, da se ta beseda začne na znak , enako kot prejšnja. Torej že imamo povezavo do vozlišča z znakom v prvem nivoju in se zato pomaknemo do tega vozlišča. Od tu dalje bomo nadaljevali z vstavljanjem preostalih znakov besede ana. Naslednji znak je znak . Ker iz vozlišča z znakom ni nobene povezave do vozlišča z iskanim znakom ustvarimo novo povezavo in vozlišče z znakom . Ostane nam še znak , ki ga vstavimo na enak način kot predhodni znak.

slika 2

Nadaljujemo z besedo ema. Postopek vstavljanja je enak kot pri prejšnjih že vstavljenih besedah. Ker še nimamo povezave do vozlišča z znakom jo moramo ustvariti. Torej vozlišče z znakom e se bo nahajal v prvem nivoju. Ravno tako moramo ustvariti povezave in vozlišča do preostalih dveh znakov besede ema.

slika 3

Sledi beseda robert. Vstavimo jo v trie na enak način kot besedo ema.

slika 4

Vstaviti moramo še besedo rok. Kot vidimo je prvi znak te besede r. Ker smo vozlišče z znakom že ustvarili pri besedi robert gremo po povezavi naprej in primerjamo naslednji znak. Ugotovimo, da tudi za znak obstaja povezava, zato se pomaknemo naprej po drevesu. Primerjamo še zadnji znak (znak ), ker povezava do tega znaka ne obstaja jo ustvarimo in znak vstavimo v drevo.

Slika 5

Slika 4 nam prikazuje končen trie za niz ključnih besed {alen, ana, ema, robert, rok}.

ISKANJE KLJUČNE BESEDE V TRIE

Iskanje ključne besede začnemo pri korenu. Iz korena sledimo povezavi, ki vodi do vozlišča, ki vsebuje znak enak prvemu znaku v iskani besedi. Če take povezave ni potem vemo, da te iskane besede ni v trie. V primeru pa da ta povezava obstaja pot nadaljujemo v smeri povezave do vozlišča, ki vsebuje znak enak drugemu znaku v iskani besedi. Postopek ponavljamo dokler ne pridemo do zadnjega znaka v besedi. Torej na splošno sledimo povezavam preko vozlišč, ki vsebujejo zaporedne znake v iskani besedi.

Upoštevati moramo naslednje:

• Če se zadnji znak v besedi nahaja v nekem listu, potem je iskana ključna beseda vsebovana v slovarju, predstavljenem v trie.
  
• Če pa ne moremo več nadaljevati poti in nismo porabili vseh znakov besede, potem iskana ključna beseda ni vsebovana v slovarju, predstavljenem v trie.
  

ZGLED 1:

Za zgled vzemimo iskanje določene telefonske številke v telefonskem imeniku. V spodaj danem trie želimo poiskati ime ana ter njeno pripadajočo telefonsko številko.

slika 6

V tem primeru imamo v znaku EndOfKey shranjene telefonske številke določenih oseb. Začnemo pri korenu. Prvi znak v besedi ana je , zato sledimo povezavi, ki nas vodi do vozlišča, ki vsebuje iskani znak (vozlišče z znakom je na spodnji sliki označeno z rdečo barvo).

slika 7

Ko pridemo do vozlišča z znakom sledimo tisti povezavi, ki nas vodi do vozlišča, ki vsebuje znak enak drugemu znaku v iskani besedi. Torej povezavi do vozlišča z znakom .

slika 8

Po enakem postopku sledimo tudi povezavi do vozlišča z znakom .

slika 9

Vse znake besede, ki smo jih iskali po postopku iskanja smo v drevesu našli, kar pomeni, da se ime nahaja v našem telefonskem imeniku. Njena telefonska številka pa je shranjena v znaku EndOfKey.

ZGLED 2:

V spodaj danem trie bi radi poiskali besedo balon.

slika 10

Iz korena se premaknemo po povezavi, ki vodi v prvi nivo do vozlišča z znakom (na sliki 11 je to vozlišče označeno z rdečo barvo).

slika 11

Drugi znak v besedi je , zato pot nadaljujemo po povezavi, ki vodi do vozlišča s tem znakom.

slika 12

Tudi nad tretjim znakom ponovimo postopek iskanja. Po izvedbi postopka ugotovimo, da iz vozlišča z znakom v drugem nivoju (glej sliko 12) ne izhaja nobena povezava, ki bi nas pripeljala do vozlišča z znakom . Torej poti ne moremo nadaljevati in zato se naše iskanje konča. Od tod sledi, da beseda balon ni vsebovana v našem danem trie.

VSTAVLJANJE KLJUČNE BESEDE V TRIE

Postopek vstavljanja je sprva enak postopku iskanja ključne besede. Dokler je začetek besede, ki jo vstavljamo enak začetku neke besede, ki je že v trie se samo sprehajamo po drevesu. Ko pa ustreznega znaka ne najdemo več ga vstavimo v trie. Vstaviti pa moramo tudi vse preostale znake besede.

Za boljšo razumevanje razlage si poglejmo postopek vstavljanja na spodnjem zgledu.

ZGLED:
V spodaj danem trie bomo vstavili besedo robi.

slika 13

Prvi znak besede, ki jo želimo vstaviti je . Iz korena sledimo povezavi, ki nas vodi do vozlišča z enakim znakom (na spodnji sliki označeno z rdečo barvo). V primeru, da take povezave ni moramo iz korena ustvariti novo povezavo in vozlišče, ki vsebuje prvi znak besede, ki jo vstavljamo. Enako pa storimo tudi s preostalim znaki besede.

slika 14

Drugi znak besede je . Ker iz vozlišča z znakom izhaja povezava do iskanega vozlišča se pomaknem po povezavi naprej.

slika 15

Tretji znak besede je . Enako kot pri prejšnjem znaku tudi tu obstaja taka povezava, ki nas vodi do iskanega vozlišča, zato se po njej pomaknemo naprej.

slika 16

Četrti znak (zadnji v našem primeru) je . Iz vozlišča z znakom b sledimo povezavam v četrti nivo in primerjamo znake. Ker se noben znak ne ujema z našim iskanim moramo ustvariti novo povezavo iz vozlišča z znakom b, ki nas bo pripeljala do znaka i. Ko to storimo je postopek vstavljanja zaključen.

slika 17

BRISANJE KLJUČNE BESEDE IZ TRIE

Postopek brisanja razdelimo na dva dela. Prvi del postopka je enak postopku iskanja ključne besede (glej prosojnico 5). Torej vse dokler ima beseda, ki jo želimo izbrisati enak začetek kot beseda v trie se sprehajamo po drevesu vključno do zadnjega znaka iskane besede. Ko smo besedo, ki jo želimo izbrisati poiskali nadaljujemo z drugim delom postopka. V drugem delu postopka se premikamo po drevesu navzgor (torej od zadnjega znaka do prvega znaka besede, ki jo želimo izbrisati). Na enak način kot smo pri postopku vstavljanja vstavljali povezave in vozlišča v trie jih sedaj odstranimo. Pri tem pa moramo biti pazljivi na vozlišča, ki imajo še kakšno dodatno povezavo do drugega vozlišča. V takem primeru tako vozlišče ne odstranimo.
Pri brisanju ključnih besed iz trie pa ne smemo pozabiti tudi na znak EndOfKey, ki predstavlja konec besede.

ZGLED:

Za zgled vzamemo kar trie, ki smo ga dobili, ko smo vanj vstavili besedo robi. V tem primeru bomo besedo robi odstranili iz trie.

slika 18

Izvedemo postopek iskanja ključne besede, v našem primer je to beseda robi Iskanje se konča ko pridemo do zadnjega znaka v besedi.

slika 19

Ko smo poiskali iskano besedo lahko začnemo z brisanjem. Kot smo prej omenili brisanje začnemo v nasprotni smeri kot vstavljanje. Torej se pomikamo po drevesu navzgor. Najprej izbrišemo znak EndOfKey.

slika 20

Nato odstranimo vozlišče z znakom v četrtem nivoju. To lahko storimo, kajti iz tega vozlišča ne izhajajo nobene povezave.

slika 21

Pomaknemo se po povezavi navzgor do naslednjega vozlišča z znakom . Ker pa ima to vozlišče tudi povezavo do drugega znaka (v našem primeru je to znak ), ga ne smemo odstraniti, saj povezuje neko besedo. Enako kot vozlišče z znakom , ne smemo izbrisati tudi vozlišče z znakom in , ker ravno tako povezujeta neko besedo. S tem pa se postopek brisanja konča.

Končni dobljeni trie izgleda takole:

slika 22

PREDSTAVITEV BRISANJA KLJUČNE BESEDE Z WINK-OM

PREDSTAVITEV GRADNJE PS TRIE Z WINK-OM (velik primer)

VIRI IN LITERATURA

wikipedia

http://wiki.fmf.uni-lj.si/wiki/Trie-drevo

http://www.cs.bu.edu/teaching/c/tree/trie/

http://blog.ivank.net/trie-in-as3.html

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Trie/