Căutare pe şiruri

Proiect Analiza Algoritmilor

 

3.5 Algoritmul Turbo - BM

 

Descriere

 

Algoritmul Turbo-BM este o varianta imbunatatita a algoritmului Boyer - Moore. Nu sunt necesare procesari suplimentare, insa spre deosebire de algoritmul Boyer - Moore este necesar un spatiu de memorie suplimentar, constant. Faza preprocesarii are complexitatea O(m + σ) iar cea a cautarii, O( n ). Cazul cel mai defavorabil prezinta o complexitate de O(2n).

 

Algoritmul consta in memorarea unui factor (o secventa) al textului care s-a potrivit unui sufix al modelului in timpul ultimei incercari (si numai daca o deplasare - sufix buna a avut loc). Aceasta tehnica prezinta 2 avantaje: este posibila sarirea peste acest factor si permite efectuarea unui turbo - shift.

 

O deplasare turbo-shift poate aparea in timpul incercarii curente, daca sufixul modelului care se cauta in text este mai mic decat cel memorat din incercarea precedenta. In acest caz o sa notam cu u factorul memorat si cu v sufixul care se potriveste in incercarea curenta, astefl incat uzv este un sufix al modelului presupus x (fie textul y). Fie a si b caracterele care au cauzat nepotrivirea curenta in model si respectiv, in text. Atunci av este un sufix al lui x, si prin urmare si al lui u din moment ce |v| < |u| (prin notatia |s| vom intelege lungimea sirului s). Cele doua caractere a si b apar la distanta p in text, iar sufixul lui x de lungime |uzv| are o perioada p = |zv| din moment ce u este o margine a lui uzv, si astfel nu se poate suprapune peste cele doua caractere nepotrivite a si b, la distanta p, in text. Cea mai mica deplasare posibila are lungimea |u| - |v|, pe care o vom numi turbo-shift.

 

 

Daca lungimea deplasarii caracterului nepotrivit este mai mare decat lungimea deplasarii sufixului bun si a deplasarii turbo-shift, atunci lungimea deplasarii adevarate trebuie sa fie mai mare sau egala cu |u| + 1. Intr-adevar, in acest caz, cele doua caractere c si d sunt diferite din moment ce am presupus ca precedenta deplasare a fost a sufixului bun.

 

 

Atunci, o deplasare mai mare decat un 'turbo-shift' dar mai mica decat |u| + 1, va alinia c si d cu acelasi caracter in v. Astfel, in acest caz lungimea deplasarii reale trebuie sa fie cel putin egala cu |u| + 1.

 

O implementare in limbajul C++

 

void preBmBc(char *x, int m, int bmBc[]) {
    int i;
    for (i = 0; i < ASIZE; ++i)
        bmBc[i] = m;
    for (i = 0; i < m - 1; ++i)
        bmBc[x[i]] = m - i - 1;
}

 

void preBmGs(char *x, int m, int bmGs[]) {
    int i, j, suff[XSIZE];
    suffixes(x, m, suff);
    for (i = 0; i < m; ++i)
        bmGs[i] = m;
    j = 0;
    for (i = m - 1; i >= -1; --i)
        if (i == -1 || suff[i] == i + 1)
            for (; j < m - 1 - i; ++j)
                if (bmGs[j] == m)
                    bmGs[j] = m - 1 - i;
    for (i = 0; i <= m - 2; ++i)
        bmGs[m - 1 - suff[i]] = m - 1 - i;
}

 

void TBM(char *x, int m, char *y, int n) {
    int bcShift, i, j, shift, u, v, turboShift, bmGs[XSIZE], bmBc[ASIZE];

    /* procesare */
    preBmGs(x, m, bmGs);
    preBmBc(x, m, bmBc);

    /* cautare */
    j = u = 0;
    shift = m;
    while (j <= n - m) {
        i = m - 1;
        while (i >= 0 && x[i] == y[i + j]) {
            --i;
            if (u != 0 && i == m - 1 - shift)
                i -= u;
        }
        if (i < 0) {
            OUTPUT(j);
            shift = bmGs[0];
            u = m - shift;
        }
        else {
            v = m - 1 - i;
            turboShift = u - v;
            bcShift = bmBc[y[i + j]] - m + 1 + i;
            shift = MAX(turboShift, bcShift);
            shift = MAX(shift, bmGs[i]);
            if (shift == bmGs[i])
                u = MIN(m - shift, v);
            else {
                if (turboShift < bcShift)
                    shift = MAX(shift, u + 1);
                u = 0;
            }
        }
        j += shift;
    }
}

 

#define MAX(x, y) x > y ? x : y

#define MIN(x, y) x < y ? x : y

 

#define OUTPUT(x) printf("%d\n", x)

[ 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 Rabin - Karp ]