mod_levenshtein.c

/* modified levenshtein distance calculation

   This program can be used, redistributed or modified under any of
   Boost Software License 1.0, GPL v2 or GPL v3

   copyright(c) 2014 kikairoya <[email protected]>
*/


#include <string.h>
#include <stdlib.h>

#define MOD_LEVENSHTEIN_INSERT_COST 1
#define MOD_LEVENSHTEIN_REMOVE_COST 1
#define MOD_LEVENSHTEIN_REPLACE_COST 3

int mod_levenshtein_min(int a, int b) {
  return a < b ? a : b;
}

int mod_levenshtein(const char *s1, const char *s2) {
#define TABLE(x,y) t[(x) + (y) * (l1+1)]
  int l1, l2;
  int *t;
  int i1, i2, ret;
  if (!s1 || !s2) return -1;
  l1 = (int)strlen(s1); /* assumes strlen(s) < INT_MAX */
  l2 = (int)strlen(s2);
  t = (int *)malloc(sizeof(int) * (l1+1) * (l2+1));
  for (i1 = 0; i1 <= l1; ++i1) TABLE(i1,0) = i1;
  for (i2 = 0; i2 <= l2; ++i2) TABLE(0,i2) = i2;
  for (i1 = 1; i1 <= l1; ++i1) {
    for (i2 = 1; i2 <= l2; ++i2) {
      int inscost = TABLE(i1-1,i2) + MOD_LEVENSHTEIN_INSERT_COST;
      int remcost = TABLE(i1,i2-1) + MOD_LEVENSHTEIN_REMOVE_COST;
      int insremcost = mod_levenshtein_min(inscost, remcost);
      int replcost = TABLE(i1-1,i2-1) + (s1[i1-1] == s2[i2-1] ? 0 : MOD_LEVENSHTEIN_REPLACE_COST);
      TABLE(i1,i2) = mod_levenshtein_min(insremcost, replcost);
    }
  }
  ret = TABLE(l1,l2);
  free(t);
  return ret;
#undef TABLE
}