root / tmp / org.txm.groovy.core / src / groovy / org / txm / scripts / utils / Distance.groovy @ 2361
History  View  Annotate  Download (2.6 kB)
1 
// Copyright © 20102013 ENS de Lyon.


2 
// Copyright © 20072010 ENS de Lyon, CNRS, INRP, University of

3 
// Lyon 2, University of FrancheComté, University of Nice

4 
// Sophia Antipolis, University of Paris 3.

5 
//

6 
// The TXM platform is free software: you can redistribute it

7 
// and/or modify it under the terms of the GNU General Public

8 
// License as published by the Free Software Foundation,

9 
// either version 2 of the License, or (at your option) any

10 
// later version.

11 
//

12 
// The TXM platform is distributed in the hope that it will be

13 
// useful, but WITHOUT ANY WARRANTY; without even the implied

14 
// warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR

15 
// PURPOSE. See the GNU General Public License for more

16 
// details.

17 
//

18 
// You should have received a copy of the GNU General

19 
// Public License along with the TXM platform. If not, see

20 
// http://www.gnu.org/licenses.

21 
//

22 
// $LastChangedDate:$

23 
// $LastChangedRevision:$

24 
// $LastChangedBy:$

25 
//

26 
package org.txm.scripts.scripts;

27  
28  
29 
// TODO: Autogenerated Javadoc

30 
/**

31 
* The Class Distance.

32 
*/

33 
public class Distance { 
34 

35 
//****************************

36 
// Get minimum of three values

37 
//****************************

38 

39 
/**

40 
* Minimum.

41 
*

42 
* @param a the a

43 
* @param b the b

44 
* @param c the c

45 
* @return the int

46 
*/

47 
private static int Minimum (int a, int b, int c) { 
48 
int mi;

49 

50 
mi = a; 
51 
if (b < mi) {

52 
mi = b; 
53 
} 
54 
if (c < mi) {

55 
mi = c; 
56 
} 
57 
return mi;

58 

59 
} 
60 

61 
//*****************************

62 
// Compute Levenshtein distance

63 
//*****************************

64 

65 
/**

66 
* LD.

67 
*

68 
* @param s the s

69 
* @param t the t

70 
* @return the int

71 
*/

72 
public static int LD (String s, String t) 
73 
{ 
74 
int[][] d; // matrix 
75 
int n; // length of s 
76 
int m; // length of t 
77 
int i; // iterates through s 
78 
int j; // iterates through t 
79 
char s_i; // ith character of s 
80 
char t_j; // jth character of t 
81 
int cost; // cost 
82 

83 
// Step 1

84 
n = s.length (); 
85 
m = t.length (); 
86 
if (n == 0) { 
87 
return m;

88 
} 
89 
if (m == 0) { 
90 
return n;

91 
} 
92 
d = new int[n+1][m+1]; 
93 

94 
// Step 2

95 
for (i = 0; i <= n; i++) { 
96 
d[i][0] = i;

97 
} 
98 
for (j = 0; j <= m; j++) { 
99 
d[0][j] = j;

100 
} 
101 

102 
// Step 3

103 
for (i = 1; i <= n; i++) { 
104 
s_i = s.charAt (i  1);

105 
// Step 4

106 
for (j = 1; j <= m; j++) { 
107 
t_j = t.charAt (j  1);

108 

109 
// Step 5

110 
if (s_i == t_j) {

111 
cost = 0;

112 
} 
113 
else {

114 
cost = 1;

115 
} 
116 

117 
// Step 6

118 
d[i][j] = Minimum (d[i1][j]+1, d[i][j1]+1, d[i1][j1] + cost); 
119 
} 
120 
} 
121 
// Step 7

122 
return d[n][m];

123 
} 
124 
} 