Trie

Iz MaFiRaWiki

(Preusmerjeno iz Trie-drevo)
Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

V računalniški znanosti je trie podatkovna struktura, ki se uporablja za shranjevanje besednih nizov. Ime Trie izhaja iz besede retrieval, kar pomeni pridobitev, povrnitev. Je iskalno drevo. V korenskem vozlišču ne hranimo podatkov, ampak je vozlišče uporabljeno le za vzdrževanje strukture. Trie podpira 3 osnovne operacije:

  • ISKANJE- ugotovi, ali se ključna beseda nahaja v trie
  • VSTAVLJANJE- vstavi besedo v trie
  • BRISANJE- odstrani besedo iz trie


Primer za trie:


image:trieslika0.jpg

Vsebina

Kako gradimo trie?

Imamo dan niz ključnih besed {amy, ann, emma, rob, roger}. Kot smo že omenili, v korenu drevesa ne hranimo podatkov, ampak je vozlišče uporabljeno le za vzdrževanje strukture. Ko vstavimo besedo, dodamo zadnjemu znaku besede EndOfKey znak [], ki predstavlja konec besede. Ta znak je lahko tudi v vozlišču na sredini drevesa. Uporabimo ga lahko za shranjevanje števil, kot naprimer let, telefonskih številk,...

Začnemo s ključno besedo amy. Zgradili bomo drevo, v katerem bo vsak znak njenega imena sledil povezavi do vozlišča. Najprej ustvarimo koren. Iz korena sledi povezava do vozlišča s prvim znakom a. Nato povezava v drugi nivo in vozlišče z znakom m. Na takšen način pridemo do zadnjega znaka y. Beseda amy je vstavljena v trie.

image:trieslika1.jpg

Pomni, da vsak nivo v trie vsebuje določen znak iz besede amy. Prvi znak iz ključne besede je vedno v nivoju 1, drugi znak v nivoju 2, ...

image:trienivo.jpg

Pri vstavljanju besede ann se postopek ponovi. Pogledamo prvi znak besede in ugotovimo, da je že povezava do njega v prvem nivoju. Pomaknemo se do vozlišča in gledamo naslednji znak in povezavo. Ker se ta ne ujema z iskanim znakom ustvarimo novo povezavo in vozlišče. Postopek ponovimo za zadnji znak.

image:trieslika2.jpg

Dodamo emma. Pomni, da je e prvi znak v besedi in spada v 1 nivo. Ker nimamo povezave do vozlišča z znakom e, jo ustvarimo. Prav tako ustvarimo tudi povezave in vozlišča za ostale znake besede emma:

image:trieslika3.jpg

Ko dodamo ime rob, opazimo isto kot pri emma, da prvega znaka te besede še ni v prvem nivoju, zato ustvarimo povezave preko vozlišč, ki vsebujejo zaporedne znake besede:

image:trieslika4.jpg

Ko vstavljamo besedo roger ugotovimo, da r že obstaja. Gremo po povezavi naprej in primerjamo naslednji znak. Ker je tudi ta že vsebovan se pomaknemo naprej po drevesu. Primerjamo tretji znak, in ker nista enaka ustvarimo novo povezavo in ga vstavimo v drevo, kot tudi ostale znake besede:

image:trieslika5.jpg

Končen trie za {amy, ann, emma, rob, roger }.

Iskanje ključne besede v trie

To je metoda, ki ugotovi ali se iskana vrednost oz. ključna beseda nahaja v trie. Če se nahaja vrne true, sicer false, ali pa preprosto vrne iskano besedo. Kliče se rekurzivno.

  1. function iskanje(vozlišče, beseda) {
  2. if (beseda je prazen niz) {
  3. return false
  4. } else { // rekurziven klic
  5. i = prvi znak besede
  6. rep = beseda minus prvi znak
  7. sin = vozlišče.sinovi[i]
  8. if (sin je null) { // ne moremo nadaljevat, čeprav še nismo porabili vseh znakov besede
  9. return false
  10. } else {
  11. return iskanje(sin, rep)
  12. }
  13. }
  14. }

Če hočemo poiskati določeno besedo, začnemo pri korenu. Sledimo povezavi do vozlišča, ki vsebuje znak enak prvemu znaku v besedi. Od tam gremo v smeri povezave do vozlišča, ki vsebuje znak, enak drugemu znaku v iskani besedi. Sledimo torej povezavam preko vozlišč, ki vsebujejo zaporedne znake v besedi.

  • Če se pot izteče v listu(če je zadnji znak besede v nekem listu), potem je ta niz vsebovan v slovarju, predstavljenemu v trie.
  • Če pa ne moremo nadaljevati, nismo pa porabili vseh znakov besede, potem niz ni v slovarju.


Primer 1:

Vzamimo za primer iskanje v telefonskem imeniku. Če želimo izvedeti ali klicati določeno številko, moramo pogledati v imenik telefona in jo tudi poiskati.

Predstavila bom iskanje imena roger v danem trie.

image:trieslika_primer1.jpg

Iskanje določene besede začnemo pri korenu. Sledimo povezavi do vozlišča, ki vsebuje znak enak prvemu znaku v iskani besedi. V našem primeru je to r.

image:trieslika_primer2.jpg

Ko pridemo do vozlišča z iskanim znakom, se pomaknemo po povezavi do naslednjega vozlišča z enakim znakom kot znak v besedi. In sicer znak o.

image:trieslika_primer3.jpg

PPo enakem postopku sledimo tudi ostalim povezavam preko vozlišč, ki vsebujejo ostale zaporedne znake naše iskane besede.

image:trieslika_primer4.jpg

Porabili smo vse znake iskane besede. To pomeni, da se beseda(ime) nahaja v imeniku. Izpiše se nam skupaj s številko, ki je shranjena v znaku EndOfKey.

Primer 2:

Iskanje besede sea:

image:trieslika_isci1.jpg

Pomaknemo se iz korena po povezavi do vozlišča z znakom s v prvem nivoju.

image:trieslika_isci2.jpg

Naš drugi iskani znak je e. Sledimo povezavi do vozlišča, ki je enak našemu drugemu znaku.

image:trieslika_isci3.jpg

Sledi iskanje zadnjega znaka a. Ponovimo postopek iskanja, vendar ne najdemo povezave do vozlišča z iskanim znakom. Ker ne moremo nadaljevat se iskanje konča. Metoda vrne false.

Vstavljanje ključne besede v trie


Postopek vstavljanja nove besede v trie je bolj zahteven kot pa iskanje besede. Postopek je sprva tak kot pri iskanju ključne besede. Dokler ima torej vstavljena beseda enak začetek kot neka beseda, ki je že v trie, se sprehajamo po drevesu. Ko pa ustreznega znaka ne najdemo več, ga (in preostale) vstavimo v trie.


Primer 1:

V dani trie želimo vstaviti besedo ana

image:trieslika_vstavi1.jpg

Naš prvi znak besede katero želimo vstaviti je a. Sledimo povezavi do vozlišča z enakim znakom. Ko ga najdemo se pomaknemo po povezavi do naslednjega vozlišča.

image:trieslika_vstavi2.jpg

Drugi znak besede je n. Pomaknemo se po povezavi do vozlišča z enakim znakom.

image:trieslika_vstavi3.jpg

Tretji znak je a. Sledimo povezavi v tretji nivo in primerjamo znake. Ker nista enaka, ustvarimo novo povezavo in vozlišče z iskanim znakom. S tem je vstavljanje končano.

image:trieslika_vstavi4.jpg

Brisanje ključne besede iz trie

Prvi del postopka brisanja je enak postopku iskanja ključne besede. Dokler ima torej beseda, ki jo želimo izbrisati enak začetek kot beseda v trie, se sprehajamo po drevesu do zadjega znaka iskane besede. V drugem delu se pomikamo po drevesu navzgor. Na enak način, kot smo vsavili povezave v trie jih sedaj odstranimo. Vendar moramo biti pozorni na vozlišča, ki imajo dodatno povezavo do drugega vozlišča. V tem primeru ga ne izbrišemo. V primerih brisanja ima pomembno vlogo končni znak, ki predstavlja konec besede.


Primer 1:

Iz danega trie želimo izbrisati besedo ann.

image:trieslika_brisi1.jpg

Začnemo z iskanjem besede v trie.

image:trieslika_brisi2.jpg

Iskanje se ustavi ko pridemo do zadnjega znaka iskane besede. Začnemo z brisanjem, vendar v nasprotni smeri kot vstavljanje. Najprej izbrišemo EndOfKey znak, potem pa postopoma odstranimo vozlišče v tretjem nivoju. Pomaknemo se po povezavi navzgor po drevesu do naslednjega vozlišča. Ker ta nima dodatne povezave, razen te, ki povezuje ključno besedo, jo odstranimo. Pomaknemo se po povezavi do znaka a. Ker ima to vozlišče povezavo do nekega drugega znaka, ga ne smemo izbrisati, ker povezuje neko besedo. Tukaj se ustavimo in brisanje se konča. Končen trie:

image:trieslika_brisi3.jpg

Povzetek


Opisala in pokazala sem primere iskanja, vstavljanja in brisanja besed iz trie. Trie je zelo učinkovit, če hočemo poiskati večje število ključnih besed, če pa iščemo le nekaj besed, potem raje uporabimo kakšno drugo metodo.

V trie je iskanje ključne besede hitrejše kot pri dvojiškem iskalnem drevesu. Za besede dolžine m je najslabši čas O(m), najboljši pa O(log n), kjer je n število elementov v drevesu.


Zunanje povezave

Glej tudi

Osebna orodja