/* 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