Una possibile definizione del problema di corrispondenza approssimativa delle stringhe è la seguente: Data una stringa di pattern P = p 1 p 2 . . . p m {\stile di visualizzazione P = p_{1} p_{2}…p_{m}}
e una stringa di testo T = t 1 t 2 t … n {\displaystyle T=t_{1}t_{2}\dots t_{n}}
, trovare una sottostringa T j ‘, j = t j ‘t … j {\displaystyle T_{j’,j}=t_{j’}\dots t_{j}}
in T, che, di tutte le sottostringhe di T, ha la minima distanza di modifiche per il modello P.
Un brute-force approccio sarebbe per calcolare la distanza modifica di P per tutte le sottostringhe di T, e quindi scegliere la sottostringa con la distanza minima. Tuttavia, questo algoritmo avrebbe il tempo di esecuzione O (n3 m).
Una soluzione migliore, che è stata proposta dai venditori, si basa sulla programmazione dinamica. Esso utilizza una formulazione alternativa del problema: per ogni posizione j nel testo T e ogni posizione che ho il modello P, calcolare il valore minimo di modificare la distanza tra i primi caratteri del pattern P i {\displaystyle P_{i}}
e ogni sottostringa T j ‘, j {\displaystyle T_{j’,j}}
di T che termina nella posizione j.
Per ogni posizione j nel testo T e ogni posizione i nel modello P, passare attraverso tutte le sottostringhe di T che terminano nella posizione j e determinare quale di esse ha la distanza minimaledit ai primi caratteri i del modello P. Scrivi questa distanza minima come E(i, j). Dopo aver calcolato E (i, j) per tutti i i e j, possiamo facilmente trovare una soluzione al problema originale: è la sottostringa per la quale E(m, j) è minima (m è la lunghezza del modello P.)
Calcolare E(m, j) è molto simile al calcolo della distanza di modifica tra due stringhe. In effetti, possiamo usare l’algoritmo di calcolo della distanza di Levenshtein per E(m, j), l’unica differenza è che dobbiamo inizializzare la prima riga con zeri e salvare il percorso di calcolo, cioè se abbiamo usato E(i − 1, j), E(i,j − 1) o E(i − 1, j − 1) nel calcolo E (i,j).
Nell’array contenente i valori E(x, y), scegliamo quindi il valore minimo nell’ultima riga, lascia che sia E(x2, y2) e seguiamo il percorso di calcolo all’indietro, tornando al numero di riga 0. Se il campo in cui siamo arrivati era E (0, y1), allora T … T è una sottostringa di T con la minima distanza di modifica dal modello P.
Calcolare l’array E(x, y) richiede tempo O(mn) con l’algoritmo di programmazione dinamica, mentre la fase di lavoro all’indietro richiede tempo O(n + m).
Un’altra idea recente è la similarità join. Quando il database corrispondente si riferisce a una vasta scala di dati, il tempo O(mn) con l’algoritmo di programmazione dinamica non può funzionare entro un tempo limitato. Quindi, l’idea è, invece di calcolare la somiglianza di tutte le coppie di stringhe, di ridurre il numero di coppie candidate. Gli algoritmi ampiamente utilizzati sono basati su verifica del filtro, hashing, hashing sensibile alla località (LSH), Tries e altri algoritmi avidi e di approssimazione. La maggior parte di essi è progettata per adattarsi a un framework (come Map-Reduce) per calcolare contemporaneamente.