Galil-Giancarlo algoritem

Iz MaFiRaWiki

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

Kaj pomeni to opozorilo?

Galil-Giancarlo algoritem je le eden iz med mnogih algoritmov za iskanje vzorcev v nekem tekstu. Algoritem je le nekoliko izboljšan Clussi algoritem za iskanje vzorcev, saj razlika nastopi le v fazi iskanja, ko se vsi elementi, ki niso luknje ujemajo. Sestavljata ga dve ločeni fazi, in sicer faza v kateri analiziramo vzorec ter si shranimo dobljene rezultate tako, da v drugi fazi s pomočju dobljenih rezultatov iz prve faze lažje in hitreje rešimo zastavljeni problem.

Vsebina


Strategija

Pri tem algoritmu primerjamo znake v dveh fazah, najprej preverjamo znake iz leve proti desni nato pa iz desne proti levi, in sicer:

  • v prvi fazi, ko primerjamo znake iz leve proti desni primerjamo tiste znake, ki niso enaki prvemu znaku v vzorcu. To so zanki, ki so v spodnjem primeru obarvani z modro barvo in pa tudi znake, ki so enaki prvemu znaku, vendar se znak ali več znakov ujema z znaki na začetku, ki se ne ujemajo v celoti.

Primeri:

  • Znaki, ki so obarvani modro so znaki, ki niso enaki prvemu znaku
G C A G C G G G


  • Znak G vzamemo, ker se znaka GC pred znakom G ujemata z znakoma GC na začetku.
G C A G C G G G


  • Znak G vzamemo, ker se znak G pred znakom G ujema z znakom G na začetku.
G C A G C G G G


  • Znak G ne vzamemo, ker se v celoti ujema. Takim znakom, ki zadoščajo zgornjim pogojem pravimo znaki, ki niso luknje. To so znaki pri katerih lahko pričakujemo, da se del znakov za trenutnim znakom ujema z znaki iz začetka.
G C G C G C G C


  • v drugi fazi pa se primerjanje znakov izvaja iz desne proti levi, in sicer na znakih, ki so enaki kot prvi znak, vendar pa se pripona znakov pred primerjanim znakom ne ujema z znaki na začetku ali pa se znaki za trenutnim znakom v celoti ujemajo.

Primeri:

  • Znak G vzamemo, ker se znaki pred znakom G ne ujemajo z znaki na začetku.
G C A G C G G G


  • Znak G vzamemo, ker se v celoti ujema.Takim znakom, ki zadoščajo zgornjemu pogoju pravimo znaki, ki so luknje. To so znaki pri katerih lahko pričakujemo, da se zanki začetka delno ali v celoti ujemajo z znaki na koncu.
G C G C G C G C


  • Taka strategija nam prinaša dve prednosti, in sicer sledeči:
    • ko pridemo do neujemanja v prvi fazi nam v naslednjem poizkusu ni potrebno ponovno primerajti znakov, ki so poravnani tako kot luknje v prejšnjem poizkusu
    • ko pridemo do neujemanja v drugi fazi se predpona vzorca ujema s tekstom tako, da se v naslednjem poizkusu lahko pripona vzorca prav tako ujema z vzorcem in nam na ta način ni potrebno ponovno primerjati znakov.

Faze algoritma

Implementacija

Uporaba v praksi

V praksi bi Galil-Giancarlo algoritem lahko uporabili povsod kjer iščemo kakšne vzorce v tekstu. Naprimer, pri iskanju kakšne besede v tekstu, ki bi jo radi zamenjali z drugo, če bi izdelovali svoj program za oblikovanje ter pisanje besedila, bi le tega lahko oplemenitili z ukazoma zamenjaj nize v besedilu z drugim nizom in najdi določen niz, ki bi uporabljali naš algoritem za iskanje nizov v tekstu.

Glej tudi

Zunanje povezave

Viri

The Gaspard-Monge institute of electronics and coputer science 11 Jun. 2006. <http://www-igm.univ-mlv.fr/index_en.shtml>

Osebna orodja