Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
/* 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 <kikairoya@gmail.com>
*/
#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
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment