Earlier I had posted a tutorial on Fuzzy String Matching with Python Code. Here in this post I am sharing the Wagner Fisher Algorithm Code in Java.
package com.codehackersblog.editdistance;
/**
*
* @author psychocoder
* @version 1.0
*/
public class WagnerFisher {
private String s1;
private String s2;
private int len_s1;
private int len_s2;
public WagnerFisher() {
s1 = null;
s2 = null;
}
public WagnerFisher(String s1, String s2) {
this.s1 = s1.toLowerCase();
this.s2 = s2.toLowerCase();
}
private void putValue(String m, String n) {
s1 = m.toLowerCase();
s2 = n.toLowerCase();
}
private int getMinimum(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
private int getWagnerFisher() {
len_s1 = s1.length();
len_s2 = s2.length();
int[][] d = new int[len_s1 + 1][len_s2 + 1];
int i, j, cost;
for (i = 0; i <= len_s1; i++) {
d[i][0] = i;
}
for (j = 0; j <= len_s2; j++) {
d[0][j] = j;
}
for (i = 1; i <= len_s1; i++) {
for (j = 1; j <= len_s2; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
d[i][j] = d[i - 1][j - 1];
} else {
d[i][j] = getMinimum(
d[i - 1][j] + 1, /*Deletion*/
d[i][j - 1] + 1, /*Insertion*/
d[i - 1][j - 1] + 1 /*Substitution*/
);
}
}
}
return d[len_s1][len_s2];
}
private int getWagnerFisher(String s1, String s2) {
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
len_s1 = s1.length();
len_s2 = s2.length();
int[][] d = new int[len_s1 + 1][len_s2 + 1];
int i, j, cost;
for (i = 0; i <= len_s1; i++) {
d[i][0] = i;
}
for (j = 0; j <= len_s2; j++) {
d[0][j] = j;
}
for (i = 1; i <= len_s1; i++) {
for (j = 1; j <= len_s2; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
d[i][j] = d[i - 1][j - 1];
} else {
d[i][j] = getMinimum(
d[i - 1][j] + 1, /*Deletion*/
d[i][j - 1] + 1, /*Insertion*/
d[i - 1][j - 1] + 1 /*Substitution*/
);
}
}
}
return d[len_s1][len_s2];
}
public static void main(String... args) {
WagnerFisher ob = new WagnerFisher("loookes", "looks");
System.out.println(ob.getWagnerFisher());
ob.putValue("Hiya", "Hey");
System.out.println(ob.getWagnerFisher());
System.out.println(ob.getWagnerFisher("Hello", "Heoll"));
}
}
0 comments :
Post a Comment