public static int compactDistance ( String s1 , String s2 ) { if ( s1 . length ( ) == 0 ) return s2 . length ( ) ; if ( s2 . length ( ) == 0 ) return s1 . length ( ) ; // the maximum edit distance there is any point in reporting. int maxdist = Math . min ( s1 . length ( ) , s2 . length ( ) ) / 2 ; // we allocate just one column instead of the entire matrix, in // order to save space. this also enables us to implement the // algorithm somewhat faster. the first cell is always the // virtual first row. int s1len = s1 . length ( ) ; int [ ] column = new int [ s1len + 1 ] ; // first we need to fill in the initial column. we use a separate // loop for this, because in this case our basis for comparison is // not the previous column, but a virtual first column. int ix2 = 0 ; char ch2 = s2 . charAt ( ix2 ) ; column [ 0 ] = 1 ; // virtual first row for ( int ix1 = 1 ; ix1 <= s1len ; ix1 ++ ) { int cost = s1 . charAt ( ix1 - 1 ) == ch2 ? 0 : 1 ; // Lowest of three: above (column[ix1 - 1]), aboveleft: ix1 - 1, // left: ix1. Latter cannot possibly be lowest, so is // ignored. column [ ix1 ] = Math . min ( column [ ix1 - 1 ] , ix1 - 1 ) + cost ; } // okay, now we have an initialized first column, and we can // compute the rest of the matrix. int above = 0 ; for ( ix2 = 1 ; ix2 < s2 . length ( ) ; ix2 ++ ) { ch2 = s2 . charAt ( ix2 ) ; above = ix2 + 1 ; // virtual first row int smallest = s1len * 2 ; // used to implement cutoff for ( int ix1 = 1 ; ix1 <= s1len ; ix1 ++ ) { int cost = s1 . charAt ( ix1 - 1 ) == ch2 ? 0 : 1 ; // above: above // aboveleft: column[ix1 - 1] // left: column[ix1] int value = Math . min ( Math . min ( above , column [ ix1 - 1 ] ) , column [ ix1 ] ) + cost ; column [ ix1 - 1 ] = above ; // write previous above = value ; // keep current smallest = Math . min ( smallest , value ) ; } column [ s1len ] = above ; // check if we can stop because we'll be going over the max distance if ( smallest > maxdist ) return smallest ; } // ok, we're done return above ; }
Optimized version of the Wagner & Fischer algorithm that only keeps a single column in the matrix in memory at a time . It implements the simple cutoff but otherwise computes the entire matrix . It is roughly twice as fast as the original function .