Back to site
Since 2004, our University project has become the Internet's most widespread web hosting directory. Here we like to talk a lot about web servers, web development, networking and security services. It is, after all, our expertise. To make things better we've launched this science section with the free access to educational resources and important scientific material translated to different languages.

Uvod - upoređivanje stringova


Uvod

Upoređivanje stringova je vrlo važna stvar u široj oblasti obrade teksta. Algoritmi za upoređivanje stringova su osnovne komponente korišćene u imlementacijama praktičnih softvera kakvi postoje na većini operativnih sistema. Štaviše, oni ističu metode programiranja koje služe kao paradigme (obrasci) u drugim oblastima računarske nauke (dizajn sistema ili softvera). Na kraju, oni takođe igraju važnu ulogu u teoriji računarske nauke postavljajući izazovne probleme.

Iako se podaci pamte na različite načine, tekst ostaje glavni oblik razmene informacija. Ovo se naročito vidi u literaturi ili lingvistici gde se podaci sastoje od ogromne građe i rečnika. To se isto tako odnosi i na računarsku nauku, gde se velike količine podataka smeštaju u linearne fajlove. A to je takođe slučaj, recimo, u molekularnoj biologiji jer biološki molekuli često mogu približno da se predstave kao sekvence nukleotida ili amino kiselina. Dalje, količina dostupnih podataka u ovim oblastima teži da se udvostruči svakih osamnaest meseci. To je razlog zašto algoritmi treba da budu efikasni iako se brzina i kapacitet skladištenja podataka računara redovno povećavaju.

Upoređivanje stringova se sastoji u pronalaženju jednog, ili, uopšteno, svih pojavljivanja nekog stringa (koji se obično naziva obrazac - eng. pattern) u određenom tekstu. Svi algoritmi, dati u ovoj knjizi, kao izlaz daju sva pojavljivanja obrasca u datom tekstu. Obrazac se označava sa x=x[0 .. m-1]; njegova dužina jednaka je m. Tekst se označava sa y=y[0 .. n-1]; njegova dužina jednaka je n. Oba stringa napravljena su od elemenata konačnog skupa znakova (karaktera), zvanog alfabet, označenog sa , i čija je veličina jednaka .

Aplikacije zahtevaju dve vrste rešenja, zavisno od toga koji string, obrazac ili tekst, je prvi zadat. Algoritmi zasnovani na primeni apstraktnih mašina ili kombinatoričkih svojstava stringova, obično se primenjuju za prethodnu obradu obrasca i za rešavanje prve vrste problema. Koncept indeksa ostvarenih pomoću stabala ili apstraktnih mašina, koristi se u drugoj vrsti rešenja. Ova knjiga će se baviti samo proučavanjem algoritama prve vrste.

Algoritmi za upoređivanje stringova, iz ove knjige, funkcionišu na sledeći način. Skeniraju tekst uz pomoć prozora čija veličina je generalno jednaka m. Prvo poravnavaju leve krajeve prozora i teksta, a zatim porede karaktere iz prozora sa karakterima iz obrasca - ova posebna aktivnost se zove pokušaj - i, nakon potpunog poklapanja sa obrascem, ili nepoklapanja, pomeraju prozor udesno. Istu proceduru ponavljaju iznova sve dok desni kraj prozora ne dođe do desnog kraja teksta. Ovaj mehanizam se obično naziva mehanizam klizećeg prozora. Svakom pokušaju pridružujemo poziciju j u tekstu, koja odgovara položaju prozora y[j .. j+m-1].

Algoritam grube sile locira sva pojavljivanja x i y u vremenu O(mn). Mnogobrojna unapređenja metoda grube sile mogu se klasifikovati prema načinu na koji izvode poređenja između karaktera obrasca i karaktera teksta, u svakom pokušaju. Izdvojile su se četiri kategorije: najprirodniji način da se izvede poređenje je sa leva na desno, što je i smer čitanja; poređenje sa desna na levo generalno vodi ka algoritmima najboljim u praksi; najbolje teoretske granice se dostižu kada se poređenja rade određenim redom; konačno, postoje neki algoritmi za koje redosled kojim se rade poređenja nije bitan (kao što je algoritam grube sile).

Sa leva na desno

Heširanje (hashing) obezbeđuje jednostavan metod kojim se izbegava kvadratni broj upoređivanja karaktera u većini situacija u praksi, i koji se, pod razumnim probabilističkim pretpostavkama, izvršava u linearnom vremenu. Uveo ga je Harrison, a kasnije u potpunosti analizirali Karp i Rabin.

Pod pretpostavkom da dužina obrasca nije veća od veličine memorijske reči date mašine, algoritam “Shift Or” je efikasan algoritam za rešavanje problema tačnog poređenja stringova i lako se prilagođava širokoj paleti problema približnog poređenja stringova.

Prvi algoritam za upoređivanje stringova, koji radi u linearnom vremenu, potiče od Morris-a i Pratt-a. Unapredili su ga Knuth, Morris i Pratt. Pretraga se ponaša kao proces prepoznavanja od strane automata, a neki karakter iz teksta se poredi sa nekim karakterom iz obrasca ne više od log(m+1) puta ( je zlatni odnos ). Hancart je dokazao da ovakvo kašnjenje srodnog algoritma koji je otkrio Simon pravi ne više od 1+log2m poređenja po karakteru teksta. Ova tri algoritma u najgorem slučaju izvode do 2n-1 poređenja karaktera teksta.

Pretraga sa determinističkim konačnim automatom obavlja tačno n provera karaktera, ali to zahteva dodatni prostor u O(m). Algoritam “Forward Dawg Matching” izvodi potpuno isti broj provera karaktera, koristeći sufiksni automat obrasca.

Algoritam Apostolico-Crochemore je jednostavan algoritam koji u najgorem slučaju vrši n poređenja karaktera.

“Not So Naive” algoritam je veoma jednostavan algoritam sa, u najgorem slučaju, kvadratnom vremenskom kompleksnošću, ali on zahteva fazu prethodne obrade u konstantnom vremenu i prostoru, i u proseku je pomalo pod-linearan.

Sa desna na levo

Boyer-Moore algoritam se smatra najefikasnijim algoritmom za upoređivanje stringova kod uobičajenih primena. Njegova uprošćena verzija (ili ceo algoritam) se često primenjuje u programima za uređivanje teksta, za komande “search” (pretraži) i “substitute” (zameni). Cole je dokazao da je maksimalan broj poređenja karaktera strogo ograničen na 3n - za neperiodične obrasce, nakon prethodne obrade. Za periodične obrasce, u najgorem slučaju, ima kvadratno vreme.

U nekoliko varijanti Boyer-Moore algoritma izbegava se njegovo kvadratno ponašanje. Najefikasnija rešenja, po pitanju broja upoređivanja simbola, dizajnirali su Apostolico i Giancarlo, Crochemore i saradnici (“Turbo BM”), i Colussi (“Reverse Colussi”).

Iskustveni rezultati pokazuju da su varijacije Boyer i Moore-ovog algoritma, koje je dizajnirao Sunday (“Quick Search”) i algoritam zasnovan na sufiksnom automatu, čiji su autori Crochemore i saradnici (“Reverse Factor” i “Turbo Reverse Factor”), najefikasniji u praksi.

Algoritmi Zhu i Takaoka i Berry-Ravindran su varijante Boyer-Moore algoritma, koje zahtevaju dodatni prostor u O(2).

Određenim redom

Prva dva linearna algoritma za upoređivanje stringova, sa optimalnim korišćenjem memorijskog prostora, su nastali zahvaljujući algoritmima Galil-Seiferas i Crochemore-Perrin (“Two Way” algoritam). Oni dele obrazac na dva dela, prvo traže desni deo obrasca sa leva na desno, a zatim, ako se ne pojavi nepoklapanje, traže levi deo obrasca.

Algoritmi Colussi i Galil-Giancarlo dele skup pozicija obrasca na dva podskupa. Oni prvo traže karaktere obrasca čije pozicije spadaju u prvi podskup, sa leva na desno, a zatim, ako se ne pojavi nepoklapanje, traže preostale karaktere sa leva na desno. Colussi algoritam je unapređenje Knuth-Morris-Pratt algoritma i, u najgorem slučaju, izvodi najviše n poređenja karaktera teksta. Galil-Giancarlo algoritam unapređuje Colussi algoritam u jednom posebnom slučaju koji mu omogućava da, u najgorem slučaju, izvede do n poređenja karaktera teksta.

Sunday-evi “Optimal Mismatch” i “Maximal Shift” algoritmi razvrstavaju pozicije obrasca prema učestalosti njihovih karaktera i prema njihovom vodećem premeštaju.

“Skip Search”, “KMP Skip Search” i “Alpha Skip Search” algoritmi autora Charras-a (i saradnika) koriste “bukete” za određivanje početnih pozicija obrasca u tekstu.

Bilo kojim redom

“Horspool” algoritam je varijanta Boyer-Moore algoritma, on koristi jednu od njegovih funkcija pomeranja, a redosled kojim se izvode poređenja karaktera teksta nije bitan. Ovo takođe važi i za sve ostale varijante, kao što su “Quick Search” od autora Sunday-a, “Tuned Boyer-Moore” od Hume-a i Sunday-a, Smith algoritam i Raita algoritam.

Definicije

Razmotrićemo praktična pretraživanja. Poći ćemo od pretpostavke da je alfabet skup ASCII kodova, ili bilo koji njegov podskup. Algoritmi su prikazani u programskom jeziku C, prema tome, za neku reč w, dužine , karakteri su w[0], ... , w[-1], i w[] koji sadrži specijalni završni karakter (“null” karakter) koji se u bilo kojoj reči ne može pojaviti ni na jednom drugom mestu, osim na kraju. Obe reči, i obrazac i tekst, smeštene su u glavnu memoriju.

Hajde da uvedemo neke definicije.

Za reč u kažemo da je prefiks reči w, ako postoji reč v (može biti i prazna) za koju važi da je w=uv.

Za reč v kažemo da je sufiks reči w, ako postoji reč u (može biti i prazna) za koju važi da je w=uv.

Za neku reč z kažemo da je podstring ili podreč ili faktor reči w, ako postoje dve reči, u i v (mogu biti i prazne), za koje važi da je w=uzv.

Za neku celobrojnu vrednost p kažemo da je period reči w, ako za i, 0 i < m-p, važi da je w[i]=w[i+p]. Najmanji period reči w se naziva karakteristični period, i označava se sa per(w).

Za neku reč w, dužine , kažemo da je periodična ako je dužina njenog najmanjeg perioda manja ili jednaka /2, u suprotnom je reč neperiodična.

Za neku reč w kažemo da je osnovna ako ne može biti napisana kao umnožak neke druge reči: ne postoje ni jedna reč z, niti celobrojna vrednost k, za koje bi važilo da je w=zk.

Za neku reč z kažemo da je granična reč (granica) reči w, ako postoje dve reči, u i v, za koje važi da je w=uz=zv, z je ujedno i prefiks i sufiks reči w. Obratite pažnju na to da je u ovom slučaju |u|=|v| period reči w.

Izvrnuta reč od reči w, dužine , koja se označava sa wR, je odraz u ogledalu reči w; wR=w[-1]w[-2] ... w[1]w[0].

Deterministički Konačni Automat (DKA) A je uređena četvorka (Q, q0, T, E), gde je:
Q konačan skup stanja;
q0 u Q početno stanje;
T, podskup Q, je skup završnih stanja;
E, podskup (Q..Q), je skup prelaza.

Jezik L(A), definisan od A, je sledeći skup:

Za svaki konkretan algoritam za upoređivanje stringova, predstavljen u ovoj knjizi, prvo navodimo njegova glavna svojstva, a zatim smo objasnili kako funkcioniše, pre prikazivanja njegovog koda, napisanog u jeziku C. Nakon toga pokazujemo kako se algoritam ponaša na tipičnom primeru, gde je x=GCAGAGAG i y=GCATCGCAGAGAGTATACAGTACG. Na kraju dajemo listu referenci gde će čitalac pronaći detaljnije prikaze i potvrde datog algoritma. U svakom pokušaju, pogoci (poklapanja) su prikazani svetlo sivom, a nepoklapanja tamno sivom bojom. Broj pokazuje redosled kojim se izvode poređenja karaktera, osim kod algoritama koji koriste automate, gde broj predstavlja stanje dostignuto nakon provere karaktera.

Primena

U ovoj knjizi ćemo koristiti klasične alate. Jedan od njih je povezana lista celobrojnih vrednosti. Ona će biti definisana u C-u na sledeći način:

  struct _cell{
    int element; 
    struct _cell *next;
  };
 
  typedef struct _cell *List;

Druge važne strukture su automati i, naročito, sufiksni automati (pogledajte poglavlje 22). U osnovi, automati su direktni grafovi. Koristićemo sledeći interfejs za manipulaciju automatima:

  Graph newGraph(int v, int e); 
  Graph newAutomaton(int v, int e); 
  Graph newSuffixAutomaton(int v, int e); 
  int newVertex(Graph g); 
  int getInitial(Graph g); 
  boolean isTerminal(Graph g, int v); 
  void setTerminal(Graph g, int v); 
  int getTarget(Graph g, int v, unsigned char c); 
  void setTarget(Graph g, int v, unsigned char c, int t); 
  int getSuffixLink(Graph g, int v); 
  void setSuffixLink(Graph g, int v, int s); 
  int getLength(Graph g, int v); 
  void setLength(Graph g, int v, int ell); 
  int getPosition(Graph g, int v); 
  void setPosition(Graph g, int v, int p); 
  int getShift(Graph g, int v, unsigned char c); 
  void setShift(Graph g, int v, unsigned char c, int s); 
  void copyVertex(Graph g, int target, int source);

Slede primeri moguće primene ovog interfejsa.

  struct _graph {
    int vertexNumber, 
        edgeNumber, 
        vertexCounter, 
        initial, 
        *terminal, 
        *target, 
        *suffixLink,
        *length, 
        *position, 
        *shift; 
  };
  
  typedef struct _graph *Graph; 
  typedef int boolean;
   
#define UNDEFINED -1
  
/* vraća novu strukturu podataka za
   graf sa temenima v i granama e */
Graph newGraph(int v, int e) {
   Graph g;

   g = (Graph)calloc(1, sizeof(struct _graph));
   if (g == NULL)
      error("newGraph");
   g->vertexNumber  = v;
   g->edgeNumber    = e;
   g->initial       = 0;
   g->vertexCounter = 1;
   return(g);
}

/* vraća novu strukturu podataka za
   automat sa temenima v i granama e */
Graph newAutomaton(int v, int e) {
   Graph aut;

   aut = newGraph(v, e);
   aut->target = (int *)calloc(e, sizeof(int));
   if (aut->target == NULL)
      error("newAutomaton");
   aut->terminal = (int *)calloc(v, sizeof(int));
   if (aut->terminal == NULL)
      error("newAutomaton");
   return(aut);
}


/* vraća novu strukturu podataka za
   sufiksni automat sa temenima v i granama e */
Graph newSuffixAutomaton(int v, int e) {
   Graph aut;

   aut = newAutomaton(v, e);
   memset(aut->target, UNDEFINED, e*sizeof(int));
   aut->suffixLink = (int *)calloc(v, sizeof(int));
   if (aut->suffixLink == NULL)
      error("newSuffixAutomaton");
   aut->length = (int *)calloc(v, sizeof(int));
   if (aut->length == NULL)
      error("newSuffixAutomaton");
   aut->position = (int *)calloc(v, sizeof(int));
   if (aut->position == NULL)
      error("newSuffixAutomaton");
   aut->shift = (int *)calloc(e, sizeof(int));
   if (aut->shift == NULL)
      error("newSuffixAutomaton");
   return(aut);
}
 
 
/* vraća novu strukturu podataka za
   stablo prefiksa sa temenima v i granama e */
Graph newTrie(int v, int e) {
   Graph aut;
 
   aut = newAutomaton(v, e);
   memset(aut->target, UNDEFINED, e*sizeof(int));
   aut->suffixLink = (int *)calloc(v, sizeof(int));
   if (aut->suffixLink == NULL)
      error("newTrie");
   aut->length = (int *)calloc(v, sizeof(int));
   if (aut->length == NULL)
      error("newTrie");
   aut->position = (int *)calloc(v, sizeof(int));
   if (aut->position == NULL)
      error("newTrie");
   aut->shift = (int *)calloc(e, sizeof(int));
   if (aut->shift == NULL)
      error("newTrie");
   return(aut);
}


/* vraća novo teme za graf g */
int newVertex(Graph g) {
   if (g != NULL && g->vertexCounter <= g->vertexNumber)
      return(g->vertexCounter++);
   error("newVertex");
}


/* vraća početno teme grafa g */
int getInitial(Graph g) {
   if (g != NULL)
      return(g->initial);
   error("getInitial");
}


/* vraća vrednost true ako je teme v završno u grafu g */
boolean isTerminal(Graph g, int v) {
   if (g != NULL && g->terminal != NULL &&
       v < g->vertexNumber)
      return(g->terminal[v]);
   error("isTerminal");
}


/* podešava teme v da bude završno u grafu g */
void setTerminal(Graph g, int v) {
   if (g != NULL && g->terminal != NULL &&
       v < g->vertexNumber)
      g->terminal[v] = 1;
   else
      error("isTerminal");
}


/* vraća odredište grane sa temena v
   označene sa c u grafu g */
int getTarget(Graph g, int v, unsigned char c) {
   if (g != NULL && g->target != NULL &&
       v < g->vertexNumber && v*c < g->edgeNumber)
      return(g->target[v*(g->edgeNumber/g->vertexNumber) +
                       c]);
   error("getTarget");
}


/* dodaje granu od temena v do temena t
   označenu znakom c u grafu g */
void setTarget(Graph g, int v, unsigned char c, int t) {
   if (g != NULL && g->target != NULL &&
       v < g->vertexNumber &&
       v*c <= g->edgeNumber && t < g->vertexNumber)
      g->target[v*(g->edgeNumber/g->vertexNumber) + c] = t;
   else
      error("setTarget");
}


/* vraća sufiksnu vezu od temena v u grafu g */
int getSuffixLink(Graph g, int v) {
   if (g != NULL && g->suffixLink != NULL &&
       v < g->vertexNumber)
      return(g->suffixLink[v]);
   error("getSuffixLink");
}


/* postavlja sufiksnu vezu od temena v
   do temena s u grafu g */
void setSuffixLink(Graph g, int v, int s) {
   if (g != NULL && g->suffixLink != NULL &&
       v < g->vertexNumber && s < g->vertexNumber)
      g->suffixLink[v] = s;
   else
      error("setSuffixLink");
}


/* vraća udaljenost od temena v u grafu g */
int getLength(Graph g, int v) {
   if (g != NULL && g->length != NULL &&
       v < g->vertexNumber)
      return(g->length[v]);
   error("getLength");
}


/* postavlja udaljenost od temena v na celobrojnu vrednost ell u grafu g */
void setLength(Graph g, int v, int ell) {
   if (g != NULL && g->length != NULL &&
       v < g->vertexNumber)
      g->length[v] = ell;
   else
      error("setLength");
}


/* vraća poziciju temena v u grafu g */
int getPosition(Graph g, int v) {
   if (g != NULL && g->position != NULL &&
       v < g->vertexNumber)
      return(g->position[v]);
   error("getPosition");
}


/* postavlja udaljenost od temena v na celobrojnu vrednost ell u grafu g */
void setPosition(Graph g, int v, int p) {
   if (g != NULL && g->position != NULL &&
       v < g->vertexNumber)
      g->position[v] = p;
   else
      error("setPosition");
}


/* vraća pomeraj grane od temena v
   označene znakom c u grafu g */
int getShift(Graph g, int v, unsigned char c) {
   if (g != NULL && g->shift != NULL &&
       v < g->vertexNumber && v*c < g->edgeNumber)
      return(g->shift[v*(g->edgeNumber/g->vertexNumber) +
             c]);
   error("getShift");
}


/* postavlja pomeraj grane od temena v
   označene znakom c na celobrojnu vrednost s u grafu g */
void setShift(Graph g, int v, unsigned char c, int s) {
   if (g != NULL && g->shift != NULL &&
       v < g->vertexNumber && v*c <= g->edgeNumber)
      g->shift[v*(g->edgeNumber/g->vertexNumber) + c] = s;
   else
      error("setShift");
}


/* kopira sve karakteristike od izvornog temena
   do odredišnog temena u grafu g */
void copyVertex(Graph g, int target, int source) {
   if (g != NULL && target < g->vertexNumber &&
       source < g->vertexNumber) {
      if (g->target != NULL)
         memcpy(g->target +
                target*(g->edgeNumber/g->vertexNumber),
                g->target +
                source*(g->edgeNumber/g->vertexNumber),
                (g->edgeNumber/g->vertexNumber)*
                sizeof(int));
      if (g->shift != NULL)
         memcpy(g->shift +
                target*(g->edgeNumber/g->vertexNumber),
                g->shift +
                source*(g->edgeNumber/g->vertexNumber),
                g->edgeNumber/g->vertexNumber)*
                sizeof(int));
      if (g->terminal != NULL)
         g->terminal[target] = g->terminal[source];
      if (g->suffixLink != NULL)
         g->suffixLink[target] = g->suffixLink[source];
      if (g->length != NULL)
         g->length[target] = g->length[source];
      if (g->position != NULL)
         g->position[target] = g->position[source];
   }
   else
      error("copyVertex");
}





Published (Last edited): 27-09-2012 , source: http://www-igm.univ-mlv.fr/~lecroq/string/node2.html#SECTION0020