Dynamic Programming - Edit Distance



John Rankin @ December 19, 2016

Edit Distance

 

Edit Distance is about calculating how similiar 2 Strings are.    

The idea is that if 2 Characters do not line up, there is a Cost, or Penalty associated to its current position at that given moment.

 

In Edit Distance, there is only a few Conditional that takes place to make something similair.

  1. If Things are the Same
  2. If There is an Insertion
  3. If there is a Deletion
  4. If there is a Replacement.

 

Luckily,  we can, in a way, group Insertion/Deletion/Replacement into 1 Conditional, so we only need 2 Conditionals!!!  

  • if  [ both characters are the same] 
  • else  [  insertion ||  deletion || replacement ] 

 

  • The Final Solution will be In the LAST cell of your COST array ( C[word1.length()][word2.length()] )
  • Ideally, the least costly way (the most similiar way) is when your Cost function is to be set from a diagnol,

 

if  [ both characters are the same] 

If both characters are the same, we can call the UP-LEFT diagnol ( which is C[i-1][j-1] )   and set the current value of the Up-Left Diagnols .  

So in other words, if this condition is met -- we simply do    C[i][j] = C[i-1][j-1] 

 

Again, there is NO COST Penalty because we found a match.. and we Pick Diagnols because going Diagnol is the Fastest way to the end of the Array.

 

else  [ insertion ||  deletion || replacement] 

If the program enters this Conditional, what it needs to do is find the Minimum Value of Either,   [LEFT, UP, or UP-LEFT] and add +1 to its value.

C[i][j] = Math.min(C[i - 1][j - 1], Math.min(C[i - 1][j], C[i][j - 1]))       + 1 ;

 

 

 

 

 

Solution:

 

	public EditString(String string1, String string2) {

		this.string1 = string1;
		this.string2 = string2;

		n = string1.length();
		m = string2.length();

		
	
		// First we need to Create Array[][] to Hold our Data  (The **COST** for each step we in order to get to the end)
		// We add the length of the String +1 to allow create space for our starting place, 0.
		// We will need to do this for both words.  
		// We name this   'C' because this list is suppose to be our **COST** list 
		C = new int[n+1][m+1];

		
		// Next, we simply initialize the first Row and Column of the Length value of itself.
		// This will Result in something like  (# will be filled with a High value, so I'm Omitting the actual value)
		//
		//
		//     J O H N 
		//   0 1 2 3 4 
		// R 1 0 0 0 0
		// A 2 0 0 0 0  
		// N 3 0 0 0 0
		// K 4 0 0 0 0 
		for (int i = 0; i <= n; i++)
			C[i][0] = i;
		for (int j = 0; j <= m; j++)
			C[0][j] = j;

		// Now we Iterate, starting @  **1** 
		for (int i=1;i<=string1.length();i++) {
		
			for (int j=1;j<=string2.length();j++) {
				
				if (string1.charAt(i-1) == string2.charAt(j-1)) {  
					// Since the Char's are the same, there is ***No Cost/Penalty ****
					// So Store The Upper-Diagnols Value, into the current C[i][j]'s place.
					C[i][j] = C[i - 1][j - 1];


				} else { //IF Char's are not the same, then it will be a Modify/Insert/Delete.
			
					// Minimum of Current Values of [LEFT,UP,Up-Left] + 1 --  For the Cost/Penalty of it NOT being a match.
					C[i][j] = 1 + Math.min(C[i - 1][j - 1], 
											Math.min(C[i - 1][j], C[i][j - 1]));
				}
			}
		}
		System.out.println("Total Cost: " + C[string1.length()][string2.length()]);
	}

 

 

 

 

 

 

Most Recent Posts


Blog Test

Read This
October 16, 2018

Day 7 - DynamoDB - and Working with 2 Services - Lambda

Read This
August 25, 2018

Day 6 - Lambda - Creating an API

Read This
August 23, 2018

AWS - Day 5 - S3 - Simple Storage Service

Read This
August 22, 2018

AWS - Day 4 - AWS CLI Useful Scripts

Read This
August 21, 2018

AWS - Day 3 - Create Container from another container

Read This
August 20, 2018

Day 2 - Docker Intro

Read This
August 17, 2018

AWS - Day1 - Tutorial - Launching my first Docker Container

Read This
August 16, 2018

AWS - Day 1 - Signing up and testing out their tutorials

Read This
August 16, 2018

Dynamic Programming - Edit Distance

Read This
December 19, 2016

Dynamic Programming - Fibonacci

Read This
December 19, 2016

What I Do

Read This
June 23, 2015

First Blog Post

Read This
June 23, 2015