Levenshtein Distance Algorithm
The Levenshtein Distance Algorithm, also known as the edit distance, is a measure of similarity between two strings by calculating the minimum number of single-character edits required to transform one string into another. These edits can include insertions, deletions, or substitutions of characters. Developed by the Russian mathematician Vladimir Levenshtein in 1965, this algorithm has widespread applications in natural language processing, data mining, computational biology, and spell-checking systems, to name a few.
The algorithm employs dynamic programming to efficiently compute the edit distance between two strings. It initializes a matrix with dimensions equal to the lengths of the input strings and iteratively fills in the matrix based on the differences between corresponding characters. The final cell of the matrix (bottom-right) contains the Levenshtein distance, which represents the minimum number of edits needed to transform one string into another. As a result, the algorithm can be used to identify the degree of similarity between two strings and can be easily extended to handle strings of different lengths, making it a versatile and powerful tool for comparing sequences.
package DynamicProgramming;
/**
* @author Kshitij VERMA (github.com/kv19971)
* LEVENSHTEIN DISTANCE dyamic programming implementation to show the difference between two strings (https://en.wikipedia.org/wiki/Levenshtein_distance)
*/
public class LevenshteinDistance {
private static int minimum(int a, int b, int c) {
if (a < b && a < c) {
return a;
} else if (b < a && b < c) {
return b;
} else {
return c;
}
}
private static int calculate_distance(String a, String b) {
int len_a = a.length() + 1;
int len_b = b.length() + 1;
int[][] distance_mat = new int[len_a][len_b];
for (int i = 0; i < len_a; i++) {
distance_mat[i][0] = i;
}
for (int j = 0; j < len_b; j++) {
distance_mat[0][j] = j;
}
for (int i = 0; i < len_a; i++) {
for (int j = 0; j < len_b; j++) {
int cost;
if (a.charAt(i) == b.charAt(j)) {
cost = 0;
} else {
cost = 1;
}
distance_mat[i][j] = minimum(distance_mat[i - 1][j], distance_mat[i - 1][j - 1], distance_mat[i][j - 1]) + cost;
}
}
return distance_mat[len_a - 1][len_b - 1];
}
public static void main(String[] args) {
String a = ""; // enter your string here
String b = ""; // enter your string here
System.out.print("Levenshtein distance between " + a + " and " + b + " is: ");
System.out.println(calculate_distance(a, b));
}
}
