Statistics
| Revision:

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

History | View | Annotate | Download (2.6 kB)

1 321 mdecorde
// Copyright © 2010-2013 ENS de Lyon.
2 321 mdecorde
// Copyright © 2007-2010 ENS de Lyon, CNRS, INRP, University of
3 321 mdecorde
// Lyon 2, University of Franche-Comté, University of Nice
4 321 mdecorde
// Sophia Antipolis, University of Paris 3.
5 321 mdecorde
//
6 321 mdecorde
// The TXM platform is free software: you can redistribute it
7 321 mdecorde
// and/or modify it under the terms of the GNU General Public
8 321 mdecorde
// License as published by the Free Software Foundation,
9 321 mdecorde
// either version 2 of the License, or (at your option) any
10 321 mdecorde
// later version.
11 321 mdecorde
//
12 321 mdecorde
// The TXM platform is distributed in the hope that it will be
13 321 mdecorde
// useful, but WITHOUT ANY WARRANTY; without even the implied
14 321 mdecorde
// warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 321 mdecorde
// PURPOSE. See the GNU General Public License for more
16 321 mdecorde
// details.
17 321 mdecorde
//
18 321 mdecorde
// You should have received a copy of the GNU General
19 321 mdecorde
// Public License along with the TXM platform. If not, see
20 321 mdecorde
// http://www.gnu.org/licenses.
21 321 mdecorde
//
22 321 mdecorde
// $LastChangedDate:$
23 321 mdecorde
// $LastChangedRevision:$
24 321 mdecorde
// $LastChangedBy:$
25 321 mdecorde
//
26 1000 mdecorde
package org.txm.scripts.scripts;
27 321 mdecorde
28 321 mdecorde
29 321 mdecorde
// TODO: Auto-generated Javadoc
30 321 mdecorde
/**
31 321 mdecorde
 * The Class Distance.
32 321 mdecorde
 */
33 321 mdecorde
public class Distance {
34 321 mdecorde
35 321 mdecorde
        //****************************
36 321 mdecorde
        // Get minimum of three values
37 321 mdecorde
        //****************************
38 321 mdecorde
39 321 mdecorde
        /**
40 321 mdecorde
         * Minimum.
41 321 mdecorde
         *
42 321 mdecorde
         * @param a the a
43 321 mdecorde
         * @param b the b
44 321 mdecorde
         * @param c the c
45 321 mdecorde
         * @return the int
46 321 mdecorde
         */
47 321 mdecorde
        private static int Minimum (int a, int b, int c) {
48 321 mdecorde
                int mi;
49 321 mdecorde
50 321 mdecorde
                mi = a;
51 321 mdecorde
                if (b < mi) {
52 321 mdecorde
                        mi = b;
53 321 mdecorde
                }
54 321 mdecorde
                if (c < mi) {
55 321 mdecorde
                        mi = c;
56 321 mdecorde
                }
57 321 mdecorde
                return mi;
58 321 mdecorde
59 321 mdecorde
        }
60 321 mdecorde
61 321 mdecorde
        //*****************************
62 321 mdecorde
        // Compute Levenshtein distance
63 321 mdecorde
        //*****************************
64 321 mdecorde
65 321 mdecorde
        /**
66 321 mdecorde
         * LD.
67 321 mdecorde
         *
68 321 mdecorde
         * @param s the s
69 321 mdecorde
         * @param t the t
70 321 mdecorde
         * @return the int
71 321 mdecorde
         */
72 321 mdecorde
        public static int LD (String s, String t)
73 321 mdecorde
        {
74 321 mdecorde
                int[][] d; // matrix
75 321 mdecorde
                int n; // length of s
76 321 mdecorde
                int m; // length of t
77 321 mdecorde
                int i; // iterates through s
78 321 mdecorde
                int j; // iterates through t
79 321 mdecorde
                char s_i; // ith character of s
80 321 mdecorde
                char t_j; // jth character of t
81 321 mdecorde
                int cost; // cost
82 321 mdecorde
83 321 mdecorde
                // Step 1
84 321 mdecorde
                n = s.length ();
85 321 mdecorde
                m = t.length ();
86 321 mdecorde
                if (n == 0) {
87 321 mdecorde
                        return m;
88 321 mdecorde
                }
89 321 mdecorde
                if (m == 0) {
90 321 mdecorde
                        return n;
91 321 mdecorde
                }
92 321 mdecorde
                d = new int[n+1][m+1];
93 321 mdecorde
94 321 mdecorde
                // Step 2
95 321 mdecorde
                for (i = 0; i <= n; i++) {
96 321 mdecorde
                        d[i][0] = i;
97 321 mdecorde
                }
98 321 mdecorde
                for (j = 0; j <= m; j++) {
99 321 mdecorde
                        d[0][j] = j;
100 321 mdecorde
                }
101 321 mdecorde
102 321 mdecorde
                // Step 3
103 321 mdecorde
                for (i = 1; i <= n; i++) {
104 321 mdecorde
                        s_i = s.charAt (i - 1);
105 321 mdecorde
                        // Step 4
106 321 mdecorde
                        for (j = 1; j <= m; j++) {
107 321 mdecorde
                                t_j = t.charAt (j - 1);
108 321 mdecorde
109 321 mdecorde
                                // Step 5
110 321 mdecorde
                                if (s_i == t_j) {
111 321 mdecorde
                                        cost = 0;
112 321 mdecorde
                                }
113 321 mdecorde
                                else {
114 321 mdecorde
                                        cost = 1;
115 321 mdecorde
                                }
116 321 mdecorde
117 321 mdecorde
                                // Step 6
118 321 mdecorde
                                d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
119 321 mdecorde
                        }
120 321 mdecorde
                }
121 321 mdecorde
                // Step 7
122 321 mdecorde
                return d[n][m];
123 321 mdecorde
        }
124 321 mdecorde
}