private double weightedEdit ( char [ ] x , char [ ] y ) { // switch parameters to use the shorter one as y to save space. if ( x . length < y . length ) { char [ ] swap = x ; x = y ; y = swap ; } int radius = ( int ) Math . round ( r * Math . max ( x . length , y . length ) ) ; double [ ] [ ] d = new double [ 2 ] [ y . length + 1 ] ; d [ 0 ] [ 0 ] = 0.0 ; for ( int j = 1 ; j <= y . length ; j ++ ) { d [ 0 ] [ j ] = d [ 0 ] [ j - 1 ] + weight [ 0 ] [ y [ j ] ] ; } for ( int i = 1 ; i <= x . length ; i ++ ) { d [ 1 ] [ 0 ] = d [ 0 ] [ 0 ] + weight [ x [ i ] ] [ 0 ] ; int start = 1 ; int end = y . length ; if ( radius > 0 ) { start = i - radius ; if ( start > 1 ) d [ 1 ] [ start - 1 ] = Double . POSITIVE_INFINITY ; else start = 1 ; end = i + radius ; if ( end < y . length ) d [ 1 ] [ end + 1 ] = Double . POSITIVE_INFINITY ; else end = y . length ; } for ( int j = start ; j <= end ; j ++ ) { double cost = weight [ x [ i - 1 ] ] [ y [ j - 1 ] ] ; d [ 1 ] [ j ] = Math . min ( d [ 0 ] [ j ] + weight [ x [ i - 1 ] ] [ 0 ] , // deletion d [ 1 ] [ j - 1 ] + weight [ 0 ] [ y [ j - 1 ] ] , // insertion d [ 0 ] [ j - 1 ] + cost ) ; // substitution } double [ ] swap = d [ 0 ] ; d [ 0 ] = d [ 1 ] ; d [ 1 ] = swap ; } return d [ 0 ] [ y . length ] ; }
Weighted edit distance .