Edit Distance.java

Edit Distance.java

import java.util.*;
/*
-------------------------------------
Edit Distance = Distanta Levenshstein
-------------------------------------


Distanta Levenshtein este o masura care cuantifica cat de diferite sunt doua siruri de caractere
prin numarul minim de operatii necesare ptrneu a transforma un sir in altil.


Avem 2 siruri

A de lungime n

B de lungime m

Dorim sa transformam  A in B folosind un  numar minim de operatii elementare

- inserare (adaugi un caracter)
- stergere (elimini un caracter)
- inlocuire (schimbam un caracter)

Fiecare operatie are costul 1

Definitie formala:

Edit Distance dintre A si B este  

numarul minim de operatii (insert, remove, replace) necesare sa transformam A in B


Ideea de programare dinamica:
-----------------------------


Se foloseste o matrice DP[i][j] 

DP[i][j] este distanta inrte prefixul A[0...i] si B[0...j]


TRanzitii:

daca ultimile caractere sunt egale

dp[i][j] = DP[i-1][j-1];

Daca sunt diferite:

DP[i][j] = 1 + minimum(DP[i-1][j], DP[i][j-1], DP[i-1][j-1])

                       stergere, inserare, inlocuire


                       Conditie de baza:

                       DP[0][j] = j TRansformam sirul vid in prefix de lungime j

                       DP[i][0] = i 



A = DAIANA (sursa)
B = DIANA (destinatie)

primul pas:
- completam prima linie si prima coloana
- care este costul sa ajungem din sirul vid in sir destinatie
- care este costul sa ajungem din sirul A in sirul B care este vid

DIANA - DIANA

  0 D I A N A
0 0 1 2 3 4 5
D 1 0 1 2 3 4
A 2 1 1 1 2 3
I 3 2 1 2 2 3
A 4 2 1 1 2 2
N 5 4 3 2 1 2
A 6 5 4 3 2 1         
 
 DP[N][M]

*/

static void EditDistance {


static void solve(String source, String dest) {

        

        int n = source.length();
        int m = dest.length();

        //DP[i][j] = costul minim de transformare [0..i] [0..j]

        int[][] DP = new int[n+1][m+1];


        String[][] from = new String[n+1][m+1];


        //conditiile de baza:

        //prima coloana: transformam 0..i-1 in sirul vid
        for(int i = 0; i <= n; ++i) {

        	DP[i][0] = i;
        	from[i][0] = "delete";
        }

        
        //prima linie: transformam sirul vid in destinatie
        for(int j = 0; j <= m; ++j) {

        	DP[0][j] = j;
        	from[0][j] = "insert";
        }


        for(int i = 1; i <= n; ++i) { //prefix sursa

        	   for(int j = 1; j <= m; ++j) { //prefix destinatie

                       if(source.charAt(i-1) == dest.charAt(j-1) {

                                 DP[i][j] = DP[i-1][j-1];
                                 from[i][j] = "match";

                       }  else {

                            //alegem minimul dintre cele 3 operatii

                       	int replace = DP[i-1][j-1];//inlocuim
                       	int delete = DP[i-1][j]; //stergem
                       	int insert = DP[i][j-1]; //inserare

                       	int best = Math.min(reaplace, Math.min(delete, insert));

                       	DP[i][j] = 1 + best;
                       }

        	   }
        }

  return DP[n][m];
}

static void main(String[] args) {

     Scanner scanner = new Scanner(System.in);

     System.out.print("Source: ");
     String source = scanner.next();
     
     System.out.print("Destination: ");
     String dest = scanner.next();

     solve(source, dest);

     scanner.close();
       
}


}