[Paper] Text Mining - 1 : Fuzzy String Matching

Psycho_Coder · 05-22-2014, 06:14 PM

New Update. Added Java Code for Damerau Lavenshtein. See the update in Github.

Here's the method code snippet : -

[

Code:
java]
private int getDamerauLavenshtein(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)) {
                    cost = 0;
                } else {
                    cost = 1;
                }

                d[i][j] = getMinimum(
                        d[i - 1][j] + 1, /*Deletion*/
                        d[i][j - 1] + 1, /*Insertion*/
                        d[i - 1][j - 1] + cost /*Substitution*/
                );

                if (i > 1 && j > 1 && s1.charAt(i - 1) == s2.charAt(j - 1)
                        && s2.charAt(j - 1) == s1.charAt(i - 1)) {
                    d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);  /*transposition*/

                }
            }
        }

        return d[len_s1][len_s2];

    }

Full Source : https://github.com/PsychoCoderHC/TextMin...htein.java