Căutare pe şiruri

Proiect Analiza Algoritmilor

 

3.5 Algoritmul Rabin - Karp

 

Descriere

 

Rabin si Karp au propus un algoritm pentru potrivirea sirurilor care se comporta bine in practica si care se poate generaliza si la alti algoritmi pentru probleme asemanatoare, cum ar fi potrivirea modelelor bidimensionale. Timpul de executie, in cazul cel mai defavorabil, este O( (n - m + 1) * m ), insa are un timp mediu de executie bun.

 

Pentru prezentarea propusa, presupunem un alfabet finit ∑ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ( se poate considera de asemenea ∑ = {a, b, c, ..., z} ), deci fiecare caracter este o cifra zecimala (in general, putem presupune ca fiecare caracter este o cifra  in baza d). Astfel putem privi un sir de k caractere consecutive ca reprezentand un numar zecimal de lungime k.

 

Fiind dat modelul P[1...m], notam cu p valoarea sa zecimala corespunzatoare. Intr-o maniera similara, fiind dat textul T[1...n], notam cu ts valoarea zecimala a subsirului T[s + 1 ... s + m] de lungime m, pentru

s = 0, 1, ..., n - m. Desigur ts = p daca si numai daca T[s + 1 ... s + m] = P[1 ... m]; astfel s este un deplasament corect daca si numai daca ts = p. Daca putem calcula p in timpul O(m) si toate valorile ti, in timpul total O(n), atunci putem determina toate deplasamentele corecte s in timpul O(n) prin compararea lui p cu fiecare ts.

 

Putem calcula p in timpul O(m) folosind schema lui Horner:

 

p = P[m] + 10( P[m - 1] + 10( P[m -2] + .....+ 10( P[2] + 10P[1] ) ... ) ).

 

Valoarea t0 poate fi calculata in mod analog din T[1...m] in timpul O(m). Pentru calcularea valorilor t1, t2, ...tn-m, in timpul O(n - m), este suficient sa observam ca ts + 1 poate fi calculat din ts intr-un timp constant deoarece:

 

ts+1 = 10(ts - 10m-1T[s + 1]) + T[s + m + 1].

 

De exemplu fie m = 5 si ts = 31415. Daca dorim sa stergem cifra cea mai semnificativa T[s + 1] = 3 si sa aducem pe pozitia cea mai putin semnificativa o noua cifra (de exemplu T[s + 5 + 1] = 2) avem:

 

ts+1 = 10(31415 - 3 * 1000) + 2 = 14152

 

Scazand 10m - 1T[s + 1], se sterge cifra cea mai semnificativa din ts; inmultind rezultatul cu 10, se deplaseaza numarul spre stanga cu o pozitie si adunand la aceasta cifra T[s + m + 1] o aduce la pozitia cea mai putin semnificativa. Daca, in prealabil, calculam constanta 10m-1 atunci fiecare executie a ecuatiei necesita un numar constant de operatii aritmetice. Astfel p si t0, t1, t2, ...tn-m pot fi calculate in timpul O(n + m) si putem determina toate aparitiile modelului P[1...m] in textul T[1...n] intr-un timp O(n + m).

Singurul dezavantaj la aceasta procedura este ca p si ts pot fi prea mari ca sa se poate lucra convenabil cu ele. Daca P contine m caractere, atunci presupunerea ca fiecare operatie aritmetica asupra lui p dureaza un timp contant nu este destul de buna. Dar exista o  rezolvare simpla pentru aceasta problema, calculul lui p si ts modulo o valuare potrivita q. Deoarece calcilul lui p si t0 si recursivitatea pot fi calculate modulo q, atunci p si toate valorile ts pot fi calculate modulo q in timpul O(m + n). Valuarea q se alege de obicei un numar prim astfel incat 10q sa poata fi reprezentat pe un cuvant de memorie, ceea ce permite ca toate operatiile necesare sa fie efectuate cu precizie aritmetica simpla. In general avand dat un alfabet {0, 1, 2, ...,d - 1}, alegem q astfel incat sa se calculeze modulo q:

 

ts+1 = (d(ts - T[s + 1]h) + T[s + m + 1]) mod q,

 

unde h = dm-1(mod q) este valuarea pentru cifra "1" in pozitia cea mai semnificativa a ferestrei text de m-cifre. Calitatea folosirii modulo q confera rapiditate, desi  ts = p(mod q) nu implica ts = p. Pe de alta parte daca ts ≠ p(mod q) atunci avem ts ≠ p, astfel incat deplasamentul s este incorect. Deci putem folosi testul ts = p(mod q) ca pe un test rapid pentru depistarea deplasamentelor incorecte s. Orice deplasament s pentru care ts = p(mod q) trebuie sa fie testat in plus pentru a vedea daca nu este doar o falsa potrivire. Aceasta testare poate fi facuta prin verificarea conditiei P[1...m] = T[s + 1...s + m]. Daca q este destul de mare atunci potrivirile false apar destul de rar.

 

Sa consideram urmatorul exemplu: se va cauta numarul 31415  in sirul  2359023141526739921. Deoarece
31415 mod 13 = 7, o sa cautam toate combinatiile p unde  p mod 13 = 7:
 
2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
---------
    8

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
  ---------
      9

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
    ---------
        3

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
      ---------
         11 

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
        ---------
            0 

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
          ---------
              1 

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
            ---------
                7	potrivire la pozitia 7 

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
              ---------
                  8 

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
                ---------
                    4

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
                  ---------
                      5

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
                    ---------
                       10

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
                      ---------
                         11

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
                        ---------
                            7	potrivire falsa

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
                          ---------
                              9

2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1
                            ---------
                               11
 
 

Concluzii

 

Timpul de executie, in cel mai defavorabil caz, pentru algoritmul Rabin-Karp este O( (n - m + 1) * m ) deoarece algoritmul verifica explicit fiecare deplasament corect. Daca P = am si T = an, atunci verificarile dureaza un timp O( (n - m + 1) * m ) deoarece fiecare dintre cele n - m + 1 deplasamente posibile sunt corecte. In multe aplicatii ne asteptam la putine deplasamente corecte , astfel timpul de executie este O(n + m), plus timpul necesar pentru procesarea potrivirilor false. Ne putem astepta ca numarul de potriviri false sa fie O(n / q), deoarece posibilitatea ca un ts arbitrar sa fie echivalent cu p(mod q)  poate fi estimata la 1 / q. Atunci timpul de executie  estimat este:

 

O(n) + O( m(v + n / q) ) ,

 

unde v este numarul de deplasamente corecte. Acest timp de executie este O(n) daca alegem q >= m. Asadar, daca numarul estimat de deplasamente corecte este mic ( O(1) ) si  numarul prim q este ales mai mare decat lungimea modelului atunci se estimeaza pentru algoritmul Rabin - Karp un timp de executie O(n + m).

 

Pseudocodul pentru algoritmul Rabin - Karp

 

potrivireRabinKarp(T, P, d, q)

n <- lungime[T]

m <- lungime[P]

h <- dm-1 mod q

p <- 0

t0 <- 0

pentru i <- 1, m executa

    p <- (dp + P[i]) mod q

    t0 <- (dt0 + T[i]) mod q

pentru s <- 0, n - m executa

    daca p = ts atunci

        daca P[1..m] = T[s + 1..s + m] atunci

            tipareste "Modelul apare cu deplasamentul" s

    daca s < n - m atunci

        ts + 1 <- ( d( ts - T[s + 1]h ) + T[s + m + 1] ) mod q

O implementare in limbajul C++

#include <iostream.h>
#include <string.h>

unsigned int q = 65521; /* numarul prim < 2^16 */
unsigned int d = 257;   /* baza pentru interpretarea numerica a stringului */
unsigned int dM;        /* d^(M-1), unde M este lungimea modelului  */

void hash_init(int M) {
    dM = 1;
    for (int i = 1; i < M; i++) dM = (dM * d) % q ;
}


unsigned int hash(char* t, int n){
    unsigned h = t[0];
    for (int i = 1; i < n; i++)
        h = (d * h + t[i]) % q;
    return h;
}


unsigned int hash_next(char* t, int M, int h){
    unsigned int oldest = (dM * t[0]) % q;
    unsigned int oldest_removed = ( (h + q) - oldest ) % q;
    return (d * oldest_removed + t[M]) % q;
}


int equal_string(char* p, char* q, int n){
/* returneaza true daca primele n caractere ale lui p si q sunt identice */
    return n == 0 || ( *p == *q && equal_string(p + 1, q + 1, n - 1) );
}

int rksearch(char* p, char* a)
/*
returneaza indicele primei aparitii a sirului p in a.
returneaza lungimea sirului a daca sirul p nu apare in sirul a.
*/
{
    int M = strlen(p);
    int N = strlen(a);


    hash_init(M);
    unsigned int h1 = hash(p, M);
    cout << h1 << "\n";
    unsigned int h2 = hash(a, M);
    cout << h2 << "\n";
    for (char* b = a; b < a + N - M; b++) {
         cout << h1 << " " << h2 << " " << equal_string(p, b, M) << " " << b << "\n";
         if (h2 == h1 && equal_string(p, b, M)) return b-a;
         h2 = hash_next(b, M, h2);
    }


    return N;
}

int main()
{
    int index;
    char* p = "hello";
    char* a = "All test programs contain the word hello, bye.";

 

    cout << "\nGiven pattern \n\"" << p << "\" and text \n\"" << a << "\"\n";
    index = rksearch(p,a);
    cout << "rksearch returns " << index << "\n";


    a = "hello, world";
    cout << " Given pattern \n\"" << p << "\" and text \n\"" << a << "\"\n";
    index = rksearch(p,a);
    cout << "rksearch returns " << index << "\n";


    a = "Goodbye, cruel world";
    cout << " Given pattern \n\"" << p << "\" and text \n\"" << a << "\"\n";
    index = rksearch(p,a);
    cout << "rksearch returns " << index << "\n";


    return 0;
}

[ Index ] [ Introducere ] [ Scurtă istorie ] [ Algoritmi de căutare pe şiruri ]
[ Anexa A ] [ Anexa B ] [ Anexa C ]
[ Autori ] [ Bibliografie ]
[ Algoritmul forţei brute ] [ Algoritmul Knuth - Morris - Pratt ]
[ Algoritmul Boyer - Moore ] [ Algoritmul Turbo - BM ]