Un punto di partenza approssimativo per la ricerca di stringhe è quello della distanza Levenshtein . Questo algoritmo conta il numero di modifiche a un singolo carattere (inserimento, eliminazione e sostituzione) per cambiare una parola in un'altra.
Un esempio di questo è kitten - > sitting che ha una distanza di modifica di tre
-
k itten - > s itten (sostituisci 's' per 'k')
- sitt e n - > sitt i n (sostituisci "i" per "e")
- sittin - > sittin g (aggiungi 'g' alla fine)
Ci sono variazioni su questo algoritmo, in particolare la distanza Damerau-Levenshtein che consente di trasposizione di due caratteri adiacenti ('hte' a 'the' ha una distanza DL di 1 e una distanza di Levenshtein di 2) e quindi è spesso più appropriato per il controllo ortografico. Esistono altre varianti per le applicazioni in cui le lacune sono importanti (stringhe di DNA).
La distanza di Levenshtein è ben nota e non troppo difficile da trovare (una volta ho avuto motivo di dare la caccia a un'implementazione di esso come function in oracle - è stato molto più veloce di tirare giù tutti i dati e quindi eseguire il lato del codice della query). Rosettacode ha una moltitudine (54) di implementazioni della distanza Levenshtein (nota che alcune lingue hanno questo come parte della libreria di stringhe da qualche parte - se stai facendo Java, guarda il apache commons lang ). Wikibooks ha 31 implementazioni e una rapida occhiata ai due non mostrano lo stesso codice per la stessa lingua.
Il modo in cui funziona è costruire una matrice che corrisponde alla relazione tra le due stringhe:
.kitten
.0123456
s1123456
i2212345
t3321234
t4432123
i5543223
n6654332
g7765443
La riga e la colonna . rappresentano che puoi raggiungere la stringa di destinazione semplicemente inserendo ogni lettera da una stringa vuota. Questo non è il caso ideale, ma è lì per seminare l'algoritmo.
Se il valore è lo stesso spot ('i' == 'i'), il valore è lo stesso del valore diagonalmente verso sinistra. Se i due punti sono dissimili ('s'! = 'K') il valore è il minimo di:
- diagonale verso l'alto e verso sinistra + 1 (una sostituzione)
- direttamente sopra + 1 (un inserimento)
- direttamente a sinistra + 1 (una cancellazione)
Il valore di ritorno della distanza di modifica è il valore nella parte inferiore destra della matrice.
Se segui in basso a destra in alto a sinistra con il minimo, puoi vedere le modifiche fatte:
.kitten
.0. .
s.1 .
i 1 .
t 1 .
t 1.
i.....2
n 2
g......3
Si noti che questo è l'approccio piuttosto intensivo della memoria. Può essere ridotto in ambito di memoria non costruendo la matrice completa - tutto ciò che interessa l'algoritmo è un sottoinsieme dei dati e può essere ridotto da N*M spazio a 2*max(N,M) spazio semplicemente memorizzando la riga precedente (e cosa è stato calcolato sulla riga corrente). Progetto codice mostra come ciò può essere fatto (con il codice C # da scaricare).