question: protected String distanceAlign ( String in , String out ) { String [ ] istr = in . split ( Pattern . quote ( entrySeparator ) ) ; String [ ] ostr = out . split ( Pattern . quote ( entrySeparator ) ) ; String delim = "#" ; int [ ] p_d = new int [ ostr . length + 1 ] ; int [ ] d = new int [ ostr . length + 1 ] ; int [ ] _d ; boolean [ ] p_sk = new boolean [ ostr . length + 1 ] ; boolean [ ] sk = new boolean [ ostr . length + 1 ] ; boolean [ ] _sk ; String [ ] p_al = new String [ ostr . length + 1 ] ; String [ ] al = new String [ ostr . length + 1 ] ; String [ ] _al ; p_d [ 0 ] = 0 ; p_al [ 0 ] = "" ; p_sk [ 0 ] = true ; for ( int j = 1 ; j < ostr . length + 1 ; j ++ ) { p_al [ j ] = p_al [ j - 1 ] + " " + ostr [ j - 1 ] ; p_d [ j ] = p_d [ j - 1 ] + symDist ( istr [ 0 ] , ostr [ j - 1 ] ) ; p_sk [ j ] = false ; } int skConst = this . skipcost ; for ( int i = 1 ; i < istr . length ; i ++ ) { d [ 0 ] = p_d [ 0 ] + skConst ; al [ 0 ] = p_al [ 0 ] + " " + delim ; sk [ 0 ] = true ; for ( int j = 1 ; j < ostr . length + 1 ; j ++ ) { int tr_cost = symDist ( istr [ i ] , ostr [ j - 1 ] ) ; int sk_cost = p_sk [ j ] ? skConst : 0 ; if ( sk_cost + p_d [ j ] < tr_cost + d [ j - 1 ] ) { d [ j ] = sk_cost + p_d [ j ] ; al [ j ] = p_al [ j ] + " " + delim ; sk [ j ] = true ; } else { d [ j ] = tr_cost + d [ j - 1 ] ; al [ j ] = al [ j - 1 ] + " " + ostr [ j - 1 ] ; sk [ j ] = false ; } } _d = p_d ; p_d = d ; d = _d ; _sk = p_sk ; p_sk = sk ; sk = _sk ; _al = p_al ; p_al = al ; al = _al ; } return p_al [ ostr . length ] ; }
target:  This computes the alignment that has the lowest distance between two Strings. <p/> There are three differences to the normal Levenshtein-distance: <p/> 1. Only insertions and deletions are allowed, no replacements (i.e. no "diagonal" transitions) 2. insertion costs are dependent on a particular phone on the input side (the one they are aligned to) 3. deletion is equivalent to a symbol on the input side that is not aligned. There are costs associated with that. <p/> The method returns the output string with alignment boundaries ('#') inserted.