Unnikked - Esperienze personali in campo informatico

Calcolare la distanza tra due stringhe

In questo articolo vedremo un tecnica algoritmica che fa uso della programmazione dinamica per il calcolo della distanza tra due stringhe.

Il problema di calcolare la distanza tra due stringhe è utile per esempio nella stesura di un programma di spell checking, ovvero i correttori ortografici. Nell’articolo non approfondiremo la struttura di uno spell ckecker ma presenterò una tecnica algoritmica molto semplice per introdurre questo problema.

Possiamo definire la distanza tra due stringhe X e Y come il numero di operazioni da compiere per trasformare la stringa X nella stringa Y. In particolare possiamo definire tre operazioni elementari per questo processo:

  • inserisci(c): inserisci il carattere c nella posizione corrente
  • elimina(c): elimina il carattere c dalla posizione corrente
  • sostituisci(c,d): sostituisci il carattere c con il carattere d nella posizione corrente

Assumeremo che ogni operazione abbia costo unitario, pertanto definiamo la distanza tra due stringhe come numero di operazioni necessarie per trasformare la stringa X nella stringa Y. Ovviamente siamo interessati alla distanza minima tra due stringe, a tal motivo ci avvaleremo della programmazione dinamica per risolvere questo problema.

Indichiamo con d(X, Y) la distanza tra esse. Invece di approcciare direttamente il problema P ci concentreremo sui suoi sottoproblemi P(i, j), ovvero trovare la distanza d(Xi, Yj) tra i prefissi Xi=[1...i] e Yj=[1...j]

Notiamo che:

  • Alcuni sottoproblemi sono banali da risolvere, per esempio la soluzione per il problema P(0,j) consiste nel partire dalla stinga vuota X0 = ε fino al prefisso Yj; la distanza d(X0, Yj) è dunque j. Analogo ragionamento vale per il caso P(i, 0) per cui la distanza tra i due prefissi è data da i.
  • Il problema finale P=P(m, n), ovvero d(X, Y) = d(Xm,Yn).

Queste osservazioni ci consentono di progettare l’algoritmo.

public static int distanzaStringhe(String X, String Y) {
		int m = X.length(), n = Y.length();
		int[][] D = new int[m][n];
		for(int i = 0; i < m; i++) D[i][0] = i;
		for (int j = 0; j < n; j++) D[0][j] = j;
		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				if(X.charAt(i) != Y.charAt(j)) {
					D[i][j] = 1 + minimo(D[i][j-1], D[i-1][j], D[i-1][j-1]);
				} else {
					D[i][j] = D[i-1][j-1];
				}
			}
		}
		return D[m-1][n-1];
	}

L’approccio utilizzato è stato il seguente:

  • I sottoproblemi da risolvere P(i, j) sono rappresentati da una matrice m * n per memorizzare i dati intermedi, memorizziamo in D(i, j) la soluzione del sottoproblema P(i, j) che conterrà la distanza tra i prefissi d(Xi,Yj)
  • I valori iniziali della matrice sono dedotti dalla prima osservazione fatta, inizializziamo la prima riga e la prima colonna della matrice come dedotto. (righe 4 e 5)
  • La soluzione globale del problema è memorizzata nella cella D[m-1][n-1], corrispondete al problema originario P=P(m, n) come dedotto nella seconda osservazione.

Il generico passo dell’algoritmo, cioè la generica soluzione del sottoproblema P(i, j) è stata risolta come di seguito:

  • Se <strong>X[i] = Y[j]</strong> allora il minimo costo per trasformare Xi in Xj è dato dal costo per trasformare Xi-1 in Yi-1, ovvero non bisogna modificare la stringa.
  • Se X[i] != Y[j] allora:
    • inserisci(Y[j]):il minimo costo per trasformare Xi in Xj è dato dal costo per trasformare Xi in Yi-1 più 1 inserimento per il carattere Y[j]
    • elimina(X[i]):il minimo costo per trasformare Xi in Xj è dato dal costo per trasformare Xi-i in Yi più 1 cancellazione per il carattere X[i]
    • sostituisci(X[i], Y[j]):il minimo costo per trasformare Xi in Xj è dato dal costo per trasformare Xi-i in Yi-1 più 1 sostituzione dell carattere X[i] in Y[j]

Dal momento che siamo interessati la soluzione ottima per il problema, allora scegliamo il minimo tra i tre casi (riga 9).

L’algoritmo richiede un tempo di esecuzione O(m*n), dove X e Y sono le due stringhe in ingresso, con |X| = m e |Y| = n. L’occupazione in memoria è O(m*n).