public static int levenshtein(String[] candidate,String[] source){
  if (source.length == 0)   return candidate.length;
  if (candidate.length == 0)   return source.length;
  int distances[][]=new int[source.length + 1][candidate.length + 1];
  for (int i=0; i <= source.length; i++)   distances[i][0]=i;
  for (int j=0; j <= candidate.length; j++)   distances[0][j]=j;
  for (int i=1; i <= source.length; i++) {
    Object sourceItem=source[i - 1];
    for (int j=1; j <= candidate.length; j++) {
      Object targetItem=candidate[j - 1];
      int cost;
      if (sourceItem.equals(targetItem))       cost=0;
 else       cost=1;
      int deletionCost=distances[i - 1][j] + 1;
      int insertionCost=distances[i][j - 1] + 1;
      int substitutionCost=distances[i - 1][j - 1] + cost;
      distances[i][j]=minimum(insertionCost,deletionCost,substitutionCost);
    }
  }
  return distances[source.length][candidate.length];
}

public static int levenshtein ( String [ ] candidate , String [ ] source ) { if ( source . length == 0 ) return candidate . length ; if ( candidate . length == 0 ) return source . length ; int distances [ ] [ ] = new int [ source . length + 1 ] [ candidate . length + 1 ] ; for ( int i = 0 ; i <= source . length ; i ++ ) distances [ i ] [ 0 ] = i ; for ( int j = 0 ; j <= candidate . length ; j ++ ) distances [ 0 ] [ j ] = j ; for ( int i = 1 ; i <= source . length ; i ++ ) { Object sourceItem = source [ i - 1 ] ; for ( int j = 1 ; j <= candidate . length ; j ++ ) { Object targetItem = candidate [ j - 1 ] ; int cost ; if ( sourceItem . equals ( targetItem ) ) cost = 0 ; else cost = 1 ; int deletionCost = distances [ i - 1 ] [ j ] + 1 ; int insertionCost = distances [ i ] [ j - 1 ] + 1 ; int substitutionCost = distances [ i - 1 ] [ j - 1 ] + cost ; distances [ i ] [ j ] = minimum ( insertionCost , deletionCost , substitutionCost ) ; } } return distances [ source . length ] [ candidate . length ] ; }
calculates the levenshtein distance for a candidate paraphrase given the source . the code is based on the example by michael gilleland found at http : / / www . merriampark . com / ld . htm .
