Similitudine tra Stringhe

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:

  1. se l’ultimo carattere delle due stringhe è identico semplicemente si ignora il carattere e si prosegue confrontando il resto delle due stringhe;
  2. 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:
    1. 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.
    2. Rimozione dell’ultimo carattere da s1: quindi ora s1 ha lunghezza m-1 ed s2 ancora n. Si procede ricorsivamente sulle due stringhe.
    3. 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.

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:

distance_score_1

Mentre se al contrario vogliamo la percentuale di caratteri che corrispondono, la formula applicabile è:

distance_score_2

How useful was this post?

Click on a star to rate it!

Average rating 5 / 5. Vote count: 1

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!