FileDocCategorySizeDatePackage
StringEditDistance.javaAPI DocGlassfish v2 API3988Fri May 04 22:25:22 BST 2007com.sun.enterprise.cli.framework

StringEditDistance

public class StringEditDistance extends Object

Fields Summary
private int[]
cost
cost vector.
private int[]
back
back buffer.
private final String
a
Two strings to be compared.
private final String
b
Constructors Summary
private StringEditDistance(String a, String b)

         this.a=a;
         this.b=b;
         cost = new int[a.length()+1];
         back = new int[a.length()+1];
             // back buffer
         for( int i=0; i<=a.length(); i++ )
             cost[i] = i;
Methods Summary
private intcalc()

         for( int j=0; j<b.length(); j++ ) {
             flip();
             cost[0] = j+1;
             for( int i=0; i<a.length(); i++ ) {
                 int match = (a.charAt(i)==b.charAt(j))?0:1;
                 cost[i+1] = min( back[i]+match, cost[i]+1, back[i+1]+1 );
             }
         }
         return cost[a.length()];
public static inteditDistance(java.lang.String a, java.lang.String b)
Computes the edit distance between two strings.

The complexity is O(nm) where n=a.length() and m=b.length().

         return new StringEditDistance(a,b).calc();
public static java.lang.StringfindNearest(java.lang.String key, java.lang.String[] group)
Finds the string in the group closest to key and returns it.

return
null if group.length==0.

         int c = Integer.MAX_VALUE;
         String r = null;
         for( int i=0; i<group.length; i++ ) {
             int ed = editDistance(key,group[i]);
             if( c>ed ) {
                 c = ed;
                 r = group[i];
             }
         }
         return r;
private voidflip()
Swaps two buffers.

         int[] t = cost;
         cost = back;
         back = t;
private intmin(int a, int b, int c)

          return Math.min(a,Math.min(b,c));