EditDistanceUtil [source code]
java
Simple implementation to calculate Edit Distance to calculate String Similarity. Used to implement word-similarity
based tag dictionary pruning for the tagger if the feature is turned on.
Helpful links:
http://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/
public class EditDistanceUtil {
static int editDistance (String a, String b) {
char[] cha = a.toCharArray(), chb = b.toCharArray();
int m = cha.length, n = chb.length;
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i < m + 1; i++) {
for (int j = 0; j < n + 1; j++) {
if (i == 0)
dp[i][j] = j;
else if (j == 0)
dp[i][j] = i;
else if (cha[i - 1] == chb[j - 1])
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]);
}
}
return dp[m][n];
}
static int min(int... nums) {
int res = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] < res)
res = nums[i];
}
return res;
}
}