I'm building a typo correction program. This is the function, which compute the levenshtein distance between two words (a dictionnary word and an input word). I will call this function many times, so it should be fast. I'm looking for therefore some optimizations. I've seen some faster algorithms, but I don't know how to implement them correctly.
static size_t compute_levenshtein_distance
(char const *const s,
size_t const ns,
char const *const t,
size_t const nt)
{
#define swap(d1, d2) \
size_t *tmp = (d1); \
(d1) = (d2); \
(d2) = tmp
#define max(a, b) \
((a) > (b) ? (a) : (b) \
#define min2(a, b) \
((a) < (b) ? (a) : (b)) \
#define min3(a, b, c) \
(min2(min2(a, b), c))
size_t t1[ns+1], t2[ns+1];
size_t *d1 = t1, *d2 = t2;
for (size_t i = 1UL; i <= ns; ++i)
d1[i] = i;
for (size_t i = 1UL; i <= nt; ++i) {
char const cCol = t[i-1];
d2[0UL] = i;
for (size_t j = 1UL; j <= ns; ++j) {
int const nCost = s[j-1] != cCol;
size_t const i1 = d1[j ] + 1;
size_t const i2 = d2[j-1] + 1;
size_t const i3 = d1[j-1] + nCost;
d2[j] = min3(i1, i2, i3);
}
swap(d1, d2);
}
return d1[ns];
#undef swap
#undef max
#undef min2
#undef min3
}
Do you have any ideas ? Thanks.