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];
}

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 ] ; }
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 .
