private static int distance ( String s , String t , int maxDistance ) { // create two work vectors of integer distances // it is possible to reduce this to only one array, but performance isn't that important here. // We could also avoid calculating a lot of the entries by taking maxDistance into account in // the inner loop. This would only be worth optimizing if it showed up in a profile. int [ ] v0 = new int [ t . length ( ) + 1 ] ; int [ ] v1 = new int [ t . length ( ) + 1 ] ; // initialize v0 (the previous row of distances) // this row is A[0][i]: edit distance for an empty s // the distance is just the number of characters to delete from t for ( int i = 0 ; i < v0 . length ; i ++ ) { v0 [ i ] = i ; } for ( int i = 0 ; i < s . length ( ) ; i ++ ) { // calculate v1 (current row distances) from the previous row v0 // first element of v1 is A[i+1][0] // edit distance is delete (i+1) chars from s to match empty t v1 [ 0 ] = i + 1 ; int bestThisRow = v1 [ 0 ] ; char sChar = Ascii . toLowerCase ( s . charAt ( i ) ) ; // use formula to fill in the rest of the row for ( int j = 0 ; j < t . length ( ) ; j ++ ) { char tChar = Ascii . toLowerCase ( t . charAt ( j ) ) ; v1 [ j + 1 ] = Math . min ( v1 [ j ] + 1 , // deletion Math . min ( v0 [ j + 1 ] + 1 , // insertion v0 [ j ] + ( ( sChar == tChar ) ? 0 : 1 ) ) ) ; // substitution bestThisRow = Math . min ( bestThisRow , v1 [ j + 1 ] ) ; } if ( bestThisRow > maxDistance ) { // if we couldn't possibly do better than maxDistance, stop trying. return maxDistance + 1 ; } // swap v1 (current row) to v0 (previous row) for next iteration. no need to clear previous // row since we always update all of v1 on each iteration. int [ ] tmp = v0 ; v0 = v1 ; v1 = tmp ; } // The best answer is the last slot in v0 (due to the swap on the last iteration) return v0 [ t . length ( ) ] ; }
Performs a case insensitive Levenshtein edit distance based on the 2 rows implementation .