Cercare un pattern all’interno di un testo è una delle operazioni più comuni in assoluto: lo fa un editor di testo con il comando “Trova”, lo fa grep, lo fa un antivirus quando analizza un file alla ricerca di una firma. Il problema è semplice da enunciare: dato un testo y lungo n e un pattern x lungo m, trovare tutte le posizioni di y in cui compare x.
Semplice da enunciare, ma le differenze di prestazioni tra un approccio elementare e uno più accorto possono essere notevoli. In questo articolo vediamo tre classici del cosiddetto string matching esatto e li mettiamo a confronto con un piccolo programma di benchmark.
Brute force
L’approccio più diretto consiste nell’allineare il pattern a ogni posizione possibile del testo e, per ciascun allineamento, confrontare i caratteri uno a uno finché non si trova una differenza o non si esaurisce il pattern.
void BF(char *x, int m, char *y, int n) {
int i, j;
for (j = 0; j <= n - m; ++j) {
for (i = 0; i < m && x[i] == y[i + j]; ++i);
if (i >= m)
OUTPUT(j);
}
}
Il metodo è corretto e, nei casi comuni, anche piuttosto veloce. Il suo limite è il caso peggiore: con testo e pattern molto ripetitivi (si pensi a cercare aaaab dentro una lunga sequenza di a) ogni allineamento arriva quasi in fondo al pattern prima di fallire, per un costo dell’ordine di O(n·m). Il difetto di fondo è che, dopo un fallimento, il brute force non riutilizza i confronti già effettuati e riparte spostandosi di una sola posizione.
I due algoritmi seguenti nascono proprio per riutilizzare quell’informazione.
Knuth-Morris-Pratt
L’intuizione di Knuth, Morris e Pratt è che, quando un confronto fallisce dopo aver già riconosciuto un prefisso del pattern, sappiamo esattamente quali caratteri del testo abbiamo appena visto: sono i primi caratteri del pattern stesso. Possiamo quindi sfruttare la struttura interna del pattern per capire di quanto far scorrere l’allineamento, senza mai tornare indietro sul testo.
Questa informazione si precalcola una volta sola, prima della ricerca, in una tabella (kmpNext) che per ogni posizione dice dove riprendere il confronto in caso di mismatch:
void preKmp(char *x, int m, int kmpNext[]) {
int i, j;
i = 0;
j = kmpNext[0] = -1;
while (i < m) {
while (j > -1 && x[i] != x[j])
j = kmpNext[j];
i++;
j++;
if (x[i] == x[j])
kmpNext[i] = kmpNext[j];
else
kmpNext[i] = j;
}
}
La ricerca vera e propria scorre il testo con un solo indice che non arretra mai:
void KMP(char *x, int m, char *y, int n) {
int i, j, kmpNext[XSIZE];
preKmp(x, m, kmpNext); /* Preprocessing */
i = j = 0; /* Searching */
while (j < n) {
while (i > -1 && x[i] != y[j])
i = kmpNext[i];
i++;
j++;
if (i >= m) {
OUTPUT(j - i);
i = kmpNext[i];
}
}
}
Il risultato è una garanzia forte: KMP ispeziona ogni carattere del testo al più un numero costante di volte, quindi è O(n) nel tempo di ricerca (più O(m) di preprocessing), indipendentemente dalla struttura di testo e pattern. È la scelta indicata quando serve una garanzia sul caso peggiore.
Boyer-Moore
Boyer-Moore adotta due idee. La prima: confronta il pattern con il testo da destra verso sinistra. La seconda: quando trova una differenza, invece di spostarsi di una posizione può saltare in avanti di molti caratteri, spesso quasi quanto l’intera lunghezza del pattern. È ciò che lo rende, nella pratica, uno degli algoritmi più veloci: all’aumentare della lunghezza del pattern tende a diventare più rapido, perché i salti coprono porzioni di testo più ampie che non vengono nemmeno esaminate.
Per decidere di quanto saltare usa due euristiche, e a ogni mismatch sceglie quella che consente lo spostamento maggiore.
Euristica del carattere sbagliato (bad-character). Il carattere del testo che ha causato il mismatch viene cercato nel pattern: se non c’è, si può saltare tutto il pattern; se c’è, lo si allinea con la sua occorrenza più a destra. La tabella si precalcola così:
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;
}
Euristica del suffisso buono (good-suffix). Se prima del mismatch avevamo già riconosciuto un suffisso del pattern, possiamo allinearlo con un’altra occorrenza dello stesso suffisso più a sinistra nel pattern (o con un suo prefisso compatibile). È la parte più delicata da calcolare e si appoggia a una tabella dei suffissi.
Con le due tabelle pronte, il ciclo di ricerca è compatto:
void BM(char *x, int m, char *y, int n) {
int i, j, bmGs[XSIZE], bmBc[ASIZE];
preBmGs(x, m, bmGs); /* Preprocessing */
preBmBc(x, m, bmBc);
j = 0; /* Searching */
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
OUTPUT(j);
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
}
Esistono molte varianti che semplificano o raffinano questo schema. Una delle più note è Quick Search, che usa la sola euristica del carattere sbagliato ma la applica al carattere successivo alla finestra corrente, ottenendo un codice brevissimo e salti generosi:
void QS(char *x, int m, char *y, int n) {
int j, qsBc[ASIZE];
preQsBc(x, m, qsBc); /* Preprocessing */
j = 0; /* Searching */
while (j <= n - m) {
if (memcmp(x, y + j, m) == 0)
OUTPUT(j);
j += qsBc[y[j + m]]; /* shift */
}
}
Confronto delle prestazioni
Il programma allegato (strsearch.c) raccoglie i quattro algoritmi e li confronta con una semplice funzione di benchmark: riempie un buffer di 2 MB, vi nasconde in un punto casuale una frase contenente il pattern, poi cronometra ciascun algoritmo.
int benchmark(char *strFunction, void (*func)(),
char *x, int m, char *y, int n)
{
clock_t start, finish;
long units;
start = clock();
func(x, m, y, n);
finish = clock();
units = finish - start;
printf("%-6s %ld unita' di tempo (%f secondi)\n", strFunction, units,
(double)units / (double)CLOCKS_PER_SEC);
return 0;
}
Eseguendolo si ottiene qualcosa del genere (i numeri assoluti dipendono dalla macchina):
Ricerca di "panca la capra" in 2097152 bytes:
BF ~0.0010 secondi
KMP ~0.0038 secondi
BM ~0.0022 secondi
QS ~0.0014 secondi
Su un buffer a bassa entropia come questo è il brute force a risultare più veloce: quasi ogni confronto fallisce al primo carattere, il ciclo interno fa pochissimo lavoro e scorre il testo con buona località di cache, senza il costo di preprocessing che KMP e Boyer-Moore in questo caso pagano a vuoto.
È un risultato atteso una volta considerato il tipo di dati: gli algoritmi vanno misurati sull’input reale. Il vantaggio di Boyer-Moore e Quick Search emerge con testi più vari, alfabeti più ampi e soprattutto pattern più lunghi, dove i salti coprono molti caratteri alla volta. KMP non è quasi mai il più veloce in pratica, ma è l’unico dei tre a garantire prestazioni lineari anche nel caso peggiore, proprietà rilevante quando l’input può essere scelto da un avversario.
Non esiste quindi un algoritmo migliore in assoluto, ma quello più adatto al caso d’uso. Modificando pattern, lunghezze e contenuto del buffer nell’allegato si può osservare come cambia la classifica.
Nota sul codice: le implementazioni degli algoritmi seguono la nomenclatura del riferimento classico di C. Charras e T. Lecroq, Handbook of Exact String Matching Algorithms, ottima lettura per chi vuole approfondire anche le molte varianti qui non trattate (Turbo-BM, Two-Way, Apostolico-Giancarlo, Raita e altre).