1 /*
2 * @(#)$Id: LevenshteinDistance.java 689 2009-07-22 00:10:27Z bsigner $
3 *
4 * Author : Ueli Kurmann, igesture@uelikurmann.ch
5 *
6 * Purpose : Computes the Levenshtein distance. The algorithm is
7 * based on the implementation presented at
8 * http://en.wikipedia.org/wiki/Levenshtein_distance.
9 *
10 * -----------------------------------------------------------------------
11 *
12 * Revision Information:
13 *
14 * Date Who Reason
15 *
16 * Dec 11, 2006 ukurmann Initial Release
17 * Mar 18, 2007 bsigner Cleanup
18 *
19 * -----------------------------------------------------------------------
20 *
21 * Copyright 1999-2009 ETH Zurich. All Rights Reserved.
22 *
23 * This software is the proprietary information of ETH Zurich.
24 * Use is subject to license terms.
25 *
26 */
27
28
29 package org.ximtec.igesture.algorithm.signature;
30
31 /**
32 * Computes the Levenshtein distance.
33 *
34 * @version 1.0 Dec 2006
35 * @author Ueli Kurmann, igesture@uelikurmann.ch
36 * @author Beat Signer, signer@inf.ethz.ch
37 */
38 public class LevenshteinDistance implements DistanceFunction {
39
40 public int computeDistance(GestureSignature sig1, GestureSignature sig2) {
41 final String str1 = sig1.toString();
42 final String str2 = sig2.toString();
43 final int[][] distance = new int[str1.length() + 1][];
44
45 for (int i = 0; i <= str1.length(); i++) {
46 distance[i] = new int[str2.length() + 1];
47 distance[i][0] = i;
48 }
49
50 for (int j = 0; j < str2.length() + 1; j++) {
51 distance[0][j] = j;
52 }
53
54 for (int i = 1; i <= str1.length(); i++) {
55
56 for (int j = 1; j <= str2.length(); j++) {
57 distance[i][j] = minimum(distance[i - 1][j] + 1,
58 distance[i][j - 1] + 1, distance[i - 1][j - 1]
59 + ((str1.substring(i - 1, i).equals(
60 str2.subSequence(j - 1, j)) ? 0 : 1)));
61 }
62
63 }
64
65 return distance[str1.length()][str2.length()];
66 } // computeDistance
67
68
69 private static int minimum(int a, int b, int c) {
70 return Math.min(Math.min(a, b), c);
71 } // minimum
72
73 }