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


Bitwise XOR-exclusive OR

Read This
May 10, 2023

0-1 Knapsack

Read This
May 10, 2023

K-Way Merge

Read This
May 10, 2023

Subsets

Read This
May 10, 2023

Backtracking

Read This
May 10, 2023

Greedy Algorithm

Read This
May 10, 2023

Trie

Read This
May 10, 2023

Depth-First Search-DFS

Read This
May 10, 2023

Breadth-First Search-BFS

Read This
May 10, 2023

Binary Search Tree-BST

Read This
May 10, 2023

Top K Elements

Read This
May 10, 2023

Binary Search Pattern

Read This
May 10, 2023

Cyclic Sort pattern

Read This
May 10, 2023

Merge Intervals

Read This
May 10, 2023

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