File D:\maven-qcr-plugin-testsunitaires\qcr4java\jenkins-master\target\site\qc\core\src\main\java\hudson\util\EditDistance.java.html

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 import java.util.Collection;
23 import java.util.Arrays;
24
25 /**
26 * Computes the string edit distance.
27 *
28 * <p>
29 * Refer to a computer science text book for the definition
30 * of the "string edit distance".
31 *
32 * @author
33 * Kohsuke Kawaguchi (kohsuke.kawaguchi@sun.com)
34 */
35 public class EditDistance {
36
37 /**
38 * Computes the edit distance between two strings.
39 *
40 * <p>
41 * The complexity is O(nm) where n=a.length() and m=b.length().
42 */
43 public static int editDistance( String a, String b ) {
44 return new EditDistance(a,b).calc();
45 }
46
47 /**
48 * Finds the string in the <code>group</code> closest to
49 * <code>key</code> and returns it.
50 *
51 * @return null if group.length==0.
52 */
53 public static String findNearest( String key, String[] group ) {
54 return findNearest(key,Arrays.asList(group));
55 }
56
57 public static String findNearest( String key, Collection<String> group ) {
58 int c = Integer.MAX_VALUE;
59 String r = null;
60
61 for (String g : group) {
62 int ed = editDistance(key, g);
63 if (c > ed) {
64 c = ed;
65 r = g;
66 }
67 }
68 return r;
69 }
70
71 /** cost vector. */
72 private int[] cost;
73 /** back buffer. */
74 private int[] back;
75
76 /** Two strings to be compared. */
77 private final String a,b;
78
79 private EditDistance( String a, String b ) {
80 this.a=a;
81 this.b=b;
82 cost = new int[a.length()+1];
83 back = new int[a.length()+1]; // back buffer
84
85 for( int i=0; i<=a.length(); i++ )
86 cost[i] = i;
87 }
88
89 /**
90 * Swaps two buffers.
91 */
92 private void flip() {
93 int[] t = cost;
94 cost = back;
95 back = t;
96 }
97
98 private int min(int a,int b,int c) {
99 return Math.min(a,Math.min(b,c));
100 }
101
102 private int calc() {
103 for( int j=0; j<b.length(); j++ ) {
104 flip();
105 cost[0] = j+1;
106 for( int i=0; i<a.length(); i++ ) {
107 int match = (a.charAt(i)==b.charAt(j))?0:1;
108 cost[i+1] = min( back[i]+match, cost[i]+1, back[i+1]+1 );
109 }
110 }
111 return cost[a.length()];
112 }
113 }
114