Monday, June 29, 2015

Code for Wagner Fisher Algorithm in Java

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

Follow Me!

Blog Archive

Followers

Visitor Map