Come calcolare la distanza Levenshtein in Java?

1. Introduzione

In questo articolo, descriviamo la distanza di Levenshtein, in alternativa nota come distanza di modifica. L'algoritmo qui spiegato è stato ideato da uno scienziato russo, Vladimir Levenshtein, nel 1965.

Forniremo un'implementazione Java iterativa e ricorsiva di questo algoritmo.

2. Qual è la distanza Levenshtein?

La distanza di Levenshtein è una misura della dissomiglianza tra due stringhe. Matematicamente, dati due Corde x ed y , le misure di distanza il numero minimo di modifiche carattere da trasformare x in y .

In genere sono consentiti tre tipi di modifiche:

  1. Inserimento di un personaggio c
  2. Cancellazione di un carattere c
  3. Sostituzione di un carattere c con c '

Esempio: Se x = 'tiro' e Y '= macchia' , la distanza di montaggio tra i due è 1 perché 'tiro' può essere convertito 'posto' sostituendo ' h ' a ' p '.

In alcune sottoclassi del problema, il costo associato a ciascun tipo di modifica potrebbe essere diverso.

Ad esempio, un costo inferiore per la sostituzione con un carattere situato nelle vicinanze sulla tastiera e un costo maggiore in caso contrario. Per semplicità, considereremo tutti i costi uguali in questo articolo.

Alcune delle applicazioni di modifica distanza sono:

  1. Controllo ortografico: rileva gli errori di ortografia nel testo e trova l'ortografia corretta più simile nel dizionario
  2. Rilevamento del plagio (fare riferimento - Carta IEEE)
  3. Analisi del DNA: trovare la somiglianza tra due sequenze
  4. Riconoscimento vocale (fare riferimento a - Microsoft Research)

3. Formulazione dell'algoritmo

Prendiamo due stringhe x e y di lunghezze m e n rispettivamente. Possiamo indicare ogni stringa come x [1: m] e y [1: n].

Sappiamo che alla fine della trasformazione, entrambe le stringhe saranno di uguale lunghezza e avranno caratteri corrispondenti in ogni posizione. Quindi, se consideriamo il primo carattere di ogni stringa, abbiamo tre opzioni:

  1. Sostituzione:
    1. Determina il costo ( D1 ) della sostituzione di x [1] con y [1] . Il costo di questo passaggio sarebbe zero se entrambi i personaggi fossero uguali. In caso contrario, il costo sarebbe uno
    2. Dopo il passaggio 1.1, sappiamo che entrambe le stringhe iniziano con lo stesso carattere. Quindi il costo totale ora sarebbe la somma del costo del passaggio 1.1 e del costo della trasformazione del resto della stringa x [2: m] in y [2: n]
  2. Inserimento:
    1. Inserisci un carattere in x per abbinare il primo carattere in y , il costo di questo passaggio sarebbe uno
    2. Dopo 2.1, abbiamo elaborato un carattere da y . Quindi il costo totale ora sarebbe la somma del costo del passaggio 2.1 (cioè 1) e il costo della trasformazione dell'intero x [1: m] nel rimanente y (y [2: n])
  3. Cancellazione:
    1. Elimina il primo carattere da x , il costo di questo passaggio sarebbe uno
    2. Dopo 3.1, abbiamo elaborato un carattere da x , ma la y completa resta da elaborare. Il costo totale sarebbe la somma del costo di 3.1 (cioè 1) e il costo di trasformare il rimanente x per l'intero y

La parte successiva della soluzione è capire quale opzione scegliere tra queste tre. Poiché non sappiamo quale opzione porterebbe al costo minimo alla fine, dobbiamo provare tutte le opzioni e scegliere quella migliore.

4. Implementazione ricorsiva ingenua

Possiamo vedere che il secondo passaggio di ciascuna opzione nella sezione # 3 è per lo più lo stesso problema di distanza di modifica ma su sottostringhe delle stringhe originali . Ciò significa che dopo ogni iterazione ci ritroviamo con lo stesso problema ma con stringhe più piccole .

Questa osservazione è la chiave per formulare un algoritmo ricorsivo. La relazione di ricorrenza può essere definita come:

D (x [1: m], y [1: n]) = min {

D (x [2: m], y [2: n]) + Costo di sostituzione da x [1] a y [1],

D (x [1: m], y [2: n]) + 1,

D (x [2: m], y [1: n]) + 1

}

Dobbiamo anche definire i casi base per il nostro algoritmo ricorsivo, che nel nostro caso è quando una o entrambe le stringhe diventano vuote:

  1. Quando entrambe le stringhe sono vuote, la distanza tra loro è zero
  2. Quando una delle stringhe è vuota, la distanza di modifica tra loro è la lunghezza dell'altra stringa, poiché abbiamo bisogno di tanti numeri di inserimenti / eliminazioni per trasformarli l'uno nell'altro:
    • Esempio: se una stringa è "cane" e l'altra stringa è "" (vuota), abbiamo bisogno di tre inserimenti in una stringa vuota per renderla "cane" , o abbiamo bisogno di tre eliminazioni in "cane" per renderla vuota. Quindi la distanza di modifica tra loro è 3

Un'implementazione ricorsiva ingenua di questo algoritmo:

public class EditDistanceRecursive { static int calculate(String x, String y) { if (x.isEmpty()) { return y.length(); } if (y.isEmpty()) { return x.length(); } int substitution = calculate(x.substring(1), y.substring(1)) + costOfSubstitution(x.charAt(0), y.charAt(0)); int insertion = calculate(x, y.substring(1)) + 1; int deletion = calculate(x.substring(1), y) + 1; return min(substitution, insertion, deletion); } public static int costOfSubstitution(char a, char b) { return a == b ? 0 : 1; } public static int min(int... numbers) { return Arrays.stream(numbers) .min().orElse(Integer.MAX_VALUE); } }

Questo algoritmo ha la complessità esponenziale. Ad ogni passaggio, ci diramiamo in tre chiamate ricorsive, creando una complessità O (3 ^ n) .

Nella prossima sezione vedremo come migliorarlo.

5. Approccio dinamico alla programmazione

Analizzando le chiamate ricorsive, osserviamo che gli argomenti per i sottoproblemi sono suffissi delle stringhe originali . Ciò significa che possono esserci solo m * n chiamate ricorsive univoche (dove m e n sono un numero di suffissi di x e y ). Quindi la complessità della soluzione ottima dovrebbe essere quadratica, O (m * n) .

Vediamo alcuni dei sotto-problemi (secondo la relazione di ricorrenza definita nella sezione # 4):

  1. I sottoproblemi di D (x [1: m], y [1: n]) sono D (x [2: m], y [2: n]), D (x [1: m], y [2 : n]) e D (x [2: m], y [1: n])
  2. I sottoproblemi di D (x [1: m], y [2: n]) sono D (x [2: m], y [3: n]), D (x [1: m], y [3 : n]) e D (x [2: m], y [2: n])
  3. I sottoproblemi di D (x [2: m], y [1: n]) sono D (x [3: m], y [2: n]), D (x [2: m], y [2 : n]) e D (x [3: m], y [1: n])

In tutti e tre i casi, uno dei sottoproblemi è D (x [2: m], y [2: n]). Invece di calcolare questo tre volte come facciamo nell'implementazione ingenua, possiamo calcolarlo una volta e riutilizzare il risultato ogni volta che è necessario.

Questo problema ha molti sottoproblemi sovrapposti, ma se conosciamo la soluzione ai sotto-problemi, possiamo facilmente trovare la risposta al problema originale. Pertanto, abbiamo entrambe le proprietà necessarie per formulare una soluzione di programmazione dinamica, ovvero Sottoproblemi sovrapposti e Sottostruttura ottimale.

Possiamo ottimizzare l'implementazione ingenua introducendo la memoizzazione, cioè memorizzare il risultato dei sottoproblemi in un array e riutilizzare i risultati memorizzati nella cache.

In alternativa, possiamo anche implementarlo in modo iterativo utilizzando un approccio basato su tabelle:

static int calculate(String x, String y) { int[][] dp = new int[x.length() + 1][y.length() + 1]; for (int i = 0; i <= x.length(); i++) { for (int j = 0; j <= y.length(); j++) { if (i == 0) { dp[i][j] = j; } else if (j == 0) { dp[i][j] = i; } else { dp[i][j] = min(dp[i - 1][j - 1] + costOfSubstitution(x.charAt(i - 1), y.charAt(j - 1)), dp[i - 1][j] + 1, dp[i][j - 1] + 1); } } } return dp[x.length()][y.length()]; } 

Questo algoritmo ha prestazioni significativamente migliori rispetto all'implementazione ricorsiva. Tuttavia, comporta un consumo di memoria significativo.

Questo può essere ulteriormente ottimizzato osservando che abbiamo bisogno solo del valore di tre celle adiacenti nella tabella per trovare il valore della cella corrente.

6. Conclusione

In questo articolo, abbiamo descritto cos'è la distanza di Levenshtein e come può essere calcolata utilizzando un approccio ricorsivo e basato sulla programmazione dinamica.

La distanza di Levenshtein è solo una delle misure della somiglianza delle stringhe, alcune delle altre metriche sono Cosine Similarity (che utilizza un approccio basato su token e considera le stringhe come vettori), Dice Coefficient, ecc.

Come sempre l'implementazione completa degli esempi può essere trovata su GitHub.