Aho-Corasick algoritem

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?


Aho-Corasick algoritem

Aho-Corasick algoritem je algoritem za iskanje ključnih besed v besedilu.

Kaj je trie?

Trie je iskalno drevo. Beseda trie izhaja iz besede "retrieval".

Primer za trie:

slika:trie.png

Trie se imenuje graf oz. drevo pri Aho-Corasick algoritmu.

Algoritem sestavljata dva dela. Imamo seznam ključnih besed. Prvi del predstavlja kako zgradimo drevo iz ključnih besed. Ključne besede potem s pomočjo drevesa poiščemo v besedilu. Medtem ko drugi del pregleduje besedilo po ključnih besedah uporabljenih po predhodno zgrajenem drevesu. Če se znak ujema sledi t.i. goto povezava, sicer sledi fail (neuspešna) povezava.

Gradnja drevesa

Iz seznama ključnih besed sestavimo trie. To pomeni, da dodajamo ključne besede k drevesu. Vozlišče drevesa predstavlja eno črko, oziroma vsako naslednje vozlišče predstavlja ključno besedo od korena do vozlišča. Koren vozlišča je uporabljen le kot prostorski imetnik in vsebuje povezave k drugim črkam. Povezave ustvarjene na tej prvi stopnji predstavljajo goto funkcijo, katera vrne naslednje stanje, kadar se znak ujema.

slika:gradnja_drevesa.png

Povezave "fail"

V drugi fazi dodamo drevesu "fail" povezave. "Fail" povezava je uporabljena, pri iskanju nekega niza, kadar se znak ne ujema. Na primer, če iščemo besedo "shis" bomo uporabili fail povezavo, in sicer iz vozlišča "sh" do vozlišča "h". Ker niza "shis" nismo našli, gledamo niz "his", katerega pa najdemo.

slika:gradnja_drevesa2.png

Iskanje

Iskanje pomeni prečkanje zgrajenega drevesa ključnih besed in uporaba fail povezav, če je to potrebno. S pomočjo trie in "fail" povezavami poiščemo, kje se ključna beseda iz seznama nahaja v besedilu.

Če hočemo poiskati nek niz, začnemo pri korenu, sledimo povezavi označenimi z znaki niza, toliko dolgo kot je možno:

  • če pot vodi do vozlišča v katerem se nahaja celoten niz, potem je ta niz ključna beseda v slovarju
  • če se pot izteče preden končamo niz, potem niz ni v slovarju; v tem primeru dalje gledamo niz brez prvega znaka, kajti mogoče pa bo ta niz v slovarju. To naredimo tako, da gremo po "fail" povezavah, ki smo jih ustvarili na drugi stopnji.

Zgled:

Iščemo ključno besedo "shis". Najprej pogledamo prvi znak te besede, tj. "s". Ker imamo tudi vozlišče z znakom "s" se pomaknemo do njega. Pogledamo drugi znak "h", gremo dalje. Tukaj pa se nam konča, ker povezave "i" nimamo. To pomeni, da te ključne besede nismo našli. Sedaj gledamo ključno besedo brez prvega znaka, in sicer "his". Gremo po fail povezavi do vozlišča "h", temu vozlišču pa po istem postopku sledita še povezavi za "i" in "s". Tako smo dobili ključno besedo "his"(spodnja slikca).

slika:iskanje.png

Primer

Gradnja drevesa

Vzemimo seznam nekaj ključnih besed, in sicer: {he, she, his, hers}. Iz teh ključnih besed postopoma sestavljamo drevo, in sicer tako, da drevesu dodajamo znake. Sledi predstavitev kako iz seznama ključnih besed sestavimo trie.

slika:zgled1.png

slika:zgled2.png

slika:zgled3.png

slika:zgled4.png

slika:zgled5.png

slika:zgled6.png

slika:zgled7.png

slika:zgled8.png

slika:zgled9.png

slika:zgled10.png

slika:zgled11.png

Druga faza

Dodajamo "fail" povezave. Sledi predstavitev.

slika:zgled12.png

slika:zgled13.png

slika:zgled14.png

slika:zgled15.png

slika:zgled16.png

slika:zgled17.png

slika:zgled18.png

slika:zgled19.png

slika:zgled20.png

slika:zgled21.png

slika:zgled22.png

slika:zgled23.png

slika:zgled24.png

slika:zgled25.png

slika:zgled26.png

slika:zgled27.png

slika:zgled28.png

slika:zgled29.png

slika:zgled30.png

slika:zgled31.png

slika:zgled32.png

Tretja faza - ISKANJE

Iščemo ključno besedo "ushers".

slika:zgled33.png

slika:zgled34.png

slika:zgled35.png

slika:zgled36.png

slika:zgled37.png

slika:zgled38.png

slika:zgled39.png

slika:zgled40.png

Povzetek

Če povzamemo je Aho-Corasick algoritem algoritem za iskanje ključnih besed v nekem besedilu. Algoritem je zelo učinkovit, če hočemo poiskati veliko število ključnih besed v besedilu poljubne dolžine. Če hočemo iskati le nekaj ključnih besed uporabimo kašno drugo metodo.

Glej tudi

Osebna orodja