KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > hudson > util > EditDistance


1 /*
2  * The contents of this file are subject to the terms
3  * of the Common Development and Distribution License
4  * (the "License"). You may not use this file except
5  * in compliance with the License.
6  *
7  * You can obtain a copy of the license at
8  * https://jwsdp.dev.java.net/CDDLv1.0.html
9  * See the License for the specific language governing
10  * permissions and limitations under the License.
11  *
12  * When distributing Covered Code, include this CDDL
13  * HEADER in each file and include the License file at
14  * https://jwsdp.dev.java.net/CDDLv1.0.html If applicable,
15  * add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your
17  * own identifying information: Portions Copyright [yyyy]
18  * [name of copyright owner]
19  */
20 package hudson.util;
21
22 /**
23  * Computes the string edit distance.
24  *
25  * <p>
26  * Refer to a computer science text book for the definition
27  * of the "string edit distance".
28  *
29  * @author
30  * Kohsuke Kawaguchi (kohsuke.kawaguchi@sun.com)
31  */
32 public class EditDistance {
33
34     /**
35      * Computes the edit distance between two strings.
36      *
37      * <p>
38      * The complexity is O(nm) where n=a.length() and m=b.length().
39      */
40     public static int editDistance( String JavaDoc a, String JavaDoc b ) {
41         return new EditDistance(a,b).calc();
42     }
43
44     /**
45      * Finds the string in the <code>group</code> closest to
46      * <code>key</code> and returns it.
47      *
48      * @return null if group.length==0.
49      */
50     public static String JavaDoc findNearest( String JavaDoc key, String JavaDoc[] group ) {
51         int c = Integer.MAX_VALUE;
52         String JavaDoc r = null;
53
54         for (String JavaDoc g : group) {
55             int ed = editDistance(key, g);
56             if (c > ed) {
57                 c = ed;
58                 r = g;
59             }
60         }
61         return r;
62     }
63
64     /** cost vector. */
65     private int[] cost;
66     /** back buffer. */
67     private int[] back;
68
69     /** Two strings to be compared. */
70     private final String JavaDoc a,b;
71
72     private EditDistance( String JavaDoc a, String JavaDoc b ) {
73         this.a=a;
74         this.b=b;
75         cost = new int[a.length()+1];
76         back = new int[a.length()+1]; // back buffer
77
78         for( int i=0; i<=a.length(); i++ )
79             cost[i] = i;
80     }
81
82     /**
83      * Swaps two buffers.
84      */
85     private void flip() {
86         int[] t = cost;
87         cost = back;
88         back = t;
89     }
90
91     private int min(int a,int b,int c) {
92         return Math.min(a,Math.min(b,c));
93     }
94
95     private int calc() {
96         for( int j=0; j<b.length(); j++ ) {
97             flip();
98             cost[0] = j+1;
99             for( int i=0; i<a.length(); i++ ) {
100                 int match = (a.charAt(i)==b.charAt(j))?0:1;
101                 cost[i+1] = min( back[i]+match, cost[i]+1, back[i+1]+1 );
102             }
103         }
104         return cost[a.length()];
105     }
106 }
107
Popular Tags