Introduzione
I metodi base offerti da java per il confronto tra stringhe sono equals
ed equalsIgnoreCase
della classe String
. Questi restituiscono true
nel caso in cui le stringhe siano esattamente identiche, nel primo caso, o che lo siano a meno dei caratteri maiuscoli e minuscoli, nel secondo. Diversamente restituiscono false
sia se le stringhe sono molto differenti sia se lo sono per pochi caratteri (es. i termini casa e cose sono simili ma differenti tra loro).
Identificare un criterio che consenta di determinare un grado di similitudine tra stringhe ha comunque molte applicazioni pratiche, come ad esempio quello di determinare i suggerimenti offerti da un correttore ortografico. Allo scopo possiamo utilizzare la Distanza di Levenshtein anche detta Distanza di Edit.
Definizione
Date due stringhe A ed B la distanza di edit è definita come il numero minimo di operazioni elementari necessarie a trasformare la prima nella seconda stringa, dove le operazioni elementari possibili sono:
- la cancellazione di un carattere (delete);
- la sostituzione di un carattere con un altro (replace);
- l’inserimento di un carattere (insert).
Ad esempio la distanza tra le stringhe “horizon” e “horzon” è uno, infatti rimuovendo il carattere ‘i’ dalla prima stringa si ottiene la seconda. Un esempio più complesso è dato dalle stringhe “horizon” e “horizontal” che richiedono tre operazioni, ovvero l’inserimento dei caratteri ‘t’, ‘a’, ‘l’ nella prima stringa.
Algoritmo
L’implementazione dell’algoritmo per il calcolo della distanza di Levenshtein consiste nel confrontare i caratteri delle due stringhe uno alla volta partendo da destra. Nel confronto le opzioni possibili sono due:
- se l’ultimo carattere delle due stringhe è identico semplicemente si ignora il carattere e si prosegue confrontando il resto delle due stringhe;
- differentemente, se i caratteri sono diversi, si tentano le tre operazioni di insert, delete e replace e si prosegue calcolando la distanza per ognuna delle stringhe generate, e selezionando la soluzione con distanza minore.
Traduciamo quanto detto in modo più formale al fine di comprenderne meglio l’implementazione ricorsiva dell’algoritmo presentata in seguito. Siano s1 ed s2 stringhe rispettivamente di lunghezza m ed n:
- Caso 1: l’ultimo carattere è ignorato ovvero l’algoritmo è applicato ricorsivamente alle sottostringhe di lunghezza m-1 ed n-1, ottenute eliminando il carattere da entrambe le stringhe.
- Caso 2: l’ultimo carattere è differente, quindi si applicano ricorsivamente le seguenti tre operazioni:
- Inserimento dell’ultimo carattere di s2 in s1: quindi ora s1 ha lunghezza m+1 ed s2 è ancora di lunghezza n. Si ignora l’ultimo carattere e si procede ricorsivamente sulle stringhe di lunghezza m ed n-1.
- Rimozione dell’ultimo carattere da s1: quindi ora s1 ha lunghezza m-1 ed s2 ancora n. Si procede ricorsivamente sulle due stringhe.
- Sostituzione dell’ultimo carattere di s1 con l’ultimo di s2. La lunghezza delle due stringhe rimane invariata e si applica l’algoritmo ricorsivamente ignorando l’ultimo carattere di entrambe le stringhe.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
public class EditDistance { /** * * @param s1 Prima stringa * @param s2 Seconda stringa * @param m Ultimo carattere della prima stringa * @param n Ultimo carattere della seconda stringa * @return */ public int calculate(String s1, String s2, int m, int n) { // If any of the string is empty then number of operations // needed would be equal to the length of other string // (Either all characters will be removed or inserted) if (m == 0) return n; // all elements will be inserted. if (n == 0) return m; // all elements will be removed. // If last characters are matching, ignore the last character // and make a recursive call with last character removed. if (s1.charAt(m - 1) == s2.charAt(n - 1)) { return calculate(s1, s2, m - 1, n - 1); } // If nothing above worked then we need to try all 3 operations // and choose the minimum among them return 1 + Math.min( calculate(s1, s2, m, n - 1), // Insert Math.min( calculate(s1, s2, m - 1, n), // Remove calculate(s1, s2, m - 1, n - 1) ) ); // Replace } public static void main(String[] args) { EditDistance ed = new EditDistance(); String s1 = "horizon"; String s2 = "horizontal"; System.out.println( "Distance: " + ed.calculate( s1, s2, s1.length(), s2.length() ) ); } |
Score
Da quanto detto è evidente che:
- una distanza di 0 (zero) indica che le due stringhe sono identiche;
- il valore massimo per la distanza (caratteri completamente differenti) è dato dal massimo tra la lunghezza delle due stringhe di input;
Quindi per conoscere la percentuale di caratteri che non corrispondono a partire dalla distanza di edit possiamo applicare la seguente formula:
Mentre se al contrario vogliamo la percentuale di caratteri che corrispondono, la formula applicabile è: