DL Distance

dldist.cc

static inline int levenshtein_dist(const int depth, const char p, const char c, const unsigned char* term, const int term_len,
                                   const int* irow, const int* jrow, int* krow)
{
  int row_min = std::numeric_limits<int>::max();
  const int columns = term_len+1;
  krow[0] = jrow[0] + 1;

  // Calculate levenshtein distance incrementally (j => column, b => term):
  // https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance#Optimal_string_alignment_distance

  for(int column=1; column<columns; column++) {
    int delete_cost = jrow[column] + 1;
    int insert_cost = krow[column - 1] + 1;

    int cost = (c != term[column-1]) ? 1 : 0;
    int replace_cost = jrow[column - 1] + cost;

    krow[column] = min(min(insert_cost, delete_cost), replace_cost);

    if(depth > 1 && column > 1 && c == term[column-2] && p == term[column-1]) {
      krow[column] = std::min(krow[column], irow[column-2] + cost);
    }

    if(krow[column] < row_min) {
      row_min = krow[column];
    }
  }

  return row_min;
}