Computing Levenshtein Distance in Java

The Levenshtein distance between two strings is given by the minimum number of operations needed to transform one string into the other, where an operation is an insertion, deletion, or substitution of a single character.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class LevenshteinDistance {
 
 private static int minOfThree(int a, int b, int c) {
 return Math.min(a, Math.min(b, c));
 }
 
 private static int calculateCost(char s, char t) {
 return s==t?0:1;
 }
 
 private static int[][] initializeMatrix(int s, int t) {
 int[][] matrix = new int[s + 1][t + 1];
 for (int i = 0; i <= s; i++) {
 matrix[i][0] = i;
 }
 
 for (int j = 0; j <= t; j++) {
 matrix[0][j] = j;
 }
 return matrix;
 }
 
 public static int computeLevenshteinDistance(final String s, final String t) {
 
 char[] s_arr = s.toCharArray();
 char[] t_arr = t.toCharArray();		
 
 if(s.equals(t)) { return 0; }
 if (s_arr.length == 0) { return t_arr.length;}
 if (t_arr.length == 0) { return s_arr.length;}
 
 int matrix[][] = initializeMatrix(s_arr.length, t_arr.length);
 
 for (int i = 0; i < s_arr.length; i++) {
 for (int j = 1; j <= t_arr.length; j++) {
    matrix[i+1][j] = minOfThree(matrix[i][j] + 1,	
        matrix[i+1][j - 1] + 1, 
        matrix[i][j - 1] + calculateCost(s_arr[i], t_arr[j-1]));
 }
 }
 
 return matrix[s_arr.length][t_arr.length];
 }
 
}

Algorithm Visualization: http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node2.html
Code: LevenshteinDistance.java



Did you enjoy this post? Why not leave a comment below and continue the conversation, or subscribe to my feed and get articles like this delivered automatically to your feed reader.

Comments

No comments yet.

Leave a comment

(required)

(required)