levenshtein distance


See On Github

Data

Tags

Source Code

package levenshtein.distance;

public class Levenshtein {
	 
    public static int distance(String a, String b) {
        a = a.toLowerCase();
        b = b.toLowerCase();

        int [] costs = new int [b.length() + 1];
        for (int j = 0; j < costs.length; j++)
            costs[j] = j;
        for (int i = 1; i <= a.length(); i++) {

        	costs[0] = i;
            int nw = i - 1;
            for (int j = 1; j <= b.length(); j++) {
                int cj = Math.min(1 + Math.min(costs[j], costs[j - 1]), a.charAt(i - 1) == b.charAt(j - 1) ? nw : nw + 1);
                nw = costs[j];
                costs[j] = cj;
            }
        }
        return costs[b.length()];
    }
 
}
package levenshtein.distance;

public class Levenshtein_test {

	public static void main(String[] args) {
		
		String [] data = { "kitten", "sitting", "saturday", "sunday" };
        for (int i = 0; i < data.length; i += 2)
            System.out.println("distance(" + data[i] + ", " + data[i+1] + ") = " + Levenshtein.distance(data[i], data[i+1]));
		
	}
	
}