Statistics
| Revision:

root / tmp / org.txm.core / src / groovy / org / txm / scripts / Distance.groovy @ 187

History | View | Annotate | Download (2.6 kB)

1
// Copyright © 2010-2013 ENS de Lyon.
2
// Copyright © 2007-2010 ENS de Lyon, CNRS, INRP, University of
3
// Lyon 2, University of Franche-Comté, 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;
27

    
28

    
29
// TODO: Auto-generated 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[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);                                
119
                        }
120
                }
121
                // Step 7        
122
                return d[n][m];
123
        }        
124
}