Edit distance — dynamic programming
This article covers the edit distance pattern of dynamic programming. Most of this article is a summary of the explanation covered by Steven Skiena in the Algorithm Design Manual. I’ve clubbed together the leetcode problems as well as the text problems on Steven Skiena’s book.
What is the edit distance problem?
Say, I’ve been provided with two strings — “abccbcdcd” (Source string) and “accdcbbda” (Destination string). I’m allowed to use three operations — INSERT, DELETE and SUBSTITUTION — each with a cost of 1. What would be the minimum possible cost to convert the source string to the destination string?
If we need to build a recurrence relation for it, let’s try to think about a string of length = 1 first, and then try to generalize the solution to strings with length > 1.
Example : source string : “a” , destination string : “b” — we could modify from “a” to “b” by the following steps:
- substitute “a” to “b” — cost: 1
- Delete “a” , Insert “b” — cost: 2
- Insert “b”, Delete “a” — cost: 2
The most effective way to arrive at the solution is through substitution which has a cost of only 1.
If we generalize the above, we will come up with a cost matrix.
cost[i][j] = Minimum ( cost[i-1][j-1] + 1 (substitution) , cost[i-1][j] + 1 (insertion), cost[i][j-1] + 1 (deletion).
Here ‘i’ represents the index of the source string and ‘j’ represents the index of the destination string. So, if we feed in the recurrence above to our example, we see :
cost[1][1] = minimum ( cost[0][0] + 1 (substitution) , cost[0][1] + 1 (insertion), cost[1][0] + 1 (deletion))
cost[0][0] = comparing(“”, “”) = 0 (as the source and destination strings are the same)
cost[0][1] = comparing(“”, “b”) = 1 (as the destination string is one character more than the source string and we need to insert on the source string to get the destination string)
cost[1][0] = comparing(“a”, “”) = 1 (as the destination string is one character short of the source string and we need to delete the source string character to get the destination string character)
Thus, cost[1][1] = minimum(0 + 1, 1 + 1, 1 + 1) = 1
What happens if the characters in both strings are the same?
In this scenario, we would not need to add any cost to edit the string at all.
cost[i][j] = if (source[i] == destination[j]) => cost[i-1][j-1]
Thus, clubbing together both conditions, we get:
cost[i][j] = cost[i-1][j-1] , if (source[i] == destination[j])
cost[i][j] = Minimum ( cost[i-1][j-1] + 1 (substitution) , cost[i-1][j] + 1 (insertion), cost[i][j-1] + 1 (deletion), otherwise
Now, let’s formulate the source code for it:
Let’s define an enum for the actions : INSERT, MATCH, SUBSTITUTE, DELETE. We also add an added variable NOTHING — which signifies no action and is used to initialize the DP table.
public enum Actions {
INSERT,
DELETE,
MATCH,
SUBSTITUTE,
NOTHING
}Now, we formulate our recurrence relation to Code :
Let's name our class as EditDistance
Initialization : constructor - takes in two parameters - the source and the destinationString source, destination;
Cell[][] matrix;
public EditDistance(String source, String destination) {
this.source = source;
this.destination = destination;
matrix = new Cell[source.length() + 1]
[destination.length() + 1];
}
Cell represents the DP matrix that we intend to build up on.
Now, we compare the strings and evaluate the editDistance cost in this function:
public int editDistanceCost(String source, String destination) {
for (int i = 0; i <= source.length(); i++) {
if (i == 0)
matrix[i][0] = new Cell(i, Actions.NOTHING);
else
matrix[i][0] = new Cell(i, Actions.DELETE);
matrix[i][0].cost = i;
}
for (int i = 0; i <= destination.length(); i++) {
if (i == 0)
matrix[0][i] = new Cell(i, Actions.NOTHING);
else
matrix[0][i] = new Cell(i, Actions.INSERT);
matrix[0][i].cost = i;
}
for(int i = 1; i <= source.length(); i++) {
for(int j = 1; j <= destination.length(); j++) {
matrix[i][j] = new Cell(Integer.MAX_VALUE, Actions.NOTHING);
}
}
for (int i = 1; i <= source.length(); i++) {
for (int j = 1; j <= destination.length(); j++) {
char chI = source.charAt(i - 1);
char chJ = destination.charAt(j - 1);
if (chI == chJ) {
matrix[i][j].cost = matrix[i - 1][j - 1].cost;
matrix[i][j].parent = Actions.MATCH;
} else {
int min = 1 + matrix[i - 1][j - 1].cost;
matrix[i][j].parent = Actions.SUBSTITUTE;
if (1 + matrix[i - 1][j].cost < min) {
min = 1 + matrix[i - 1][j].cost;
matrix[i][j].parent = Actions.DELETE;
}
if (1 + matrix[i][j - 1].cost < min) {
min = 1 + matrix[i][j - 1].cost;
matrix[i][j].parent = Actions.INSERT;
}
matrix[i][j].cost = min;
}
}
}
return matrix[source.length()][destination.length()].cost;
}If we wish to retrieve the sequence of actions that we need to take in order to move from the source to the destination string — all we would need to do is write up a recursive function that traces the sequence of steps from the last cell.
public String getActions(String action, int row, int col) {
if(matrix[row][col].parent == Actions.NOTHING)
return action;
if(matrix[row][col].parent == Actions.INSERT) {
return getActions(action + "I", row, col - 1);
} else if (matrix[row][col].parent == Actions.DELETE) {
return getActions(action + "D", row - 1, col);
} else if(matrix[row][col].parent == Actions.SUBSTITUTE) {
return getActions(action + "S" , row - 1, col - 1);
} else
return getActions(action + "M", row - 1, col - 1);
}The call to getActions would be -> getActions("", source.length(), destination.length());
This was a basic explanation and implementation of Edit Distance. In the next few articles, we will discuss about the variants of edit distance.