# Write a typo correction program with Levenshtein distance algorithm

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.

• One problem I see is that you very often call the minimum macro. Try using bit twiddling this part. There is an excellent article about how to obtain the minimum of two numbers without branching on graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax – stefan Jul 10 '12 at 15:36
• Thanks for your comment, I've already read this article, but the given version run slower down than the ternary version. – md5 Jul 16 '12 at 9:30
• You're welcome. Well then I only see the problem of a too big dictionary. Can you reduce the number of calls of the distance function by e.g. only checking against words with similar length? – stefan Jul 16 '12 at 10:18

I see very little space for improvements.

First, your min3 macro (btw, max is missing a closing bracket) will, in some cases, execute inside branching more than needed (i.e., if c > min2(a,b)). I'd write it directly:

#define min3(a, b, c)   \
((a) < (b) ? ((a) < (c) ? (a) : (c)) : ((b) < (c) ? (b) : (c)))


Second, this part:

for (size_t i = 1UL; i <= nt; ++i) {
char const cCol = t[i-1];
d2[0UL]         = i;


can save one subtraction:

for (size_t i = 0UL; i < nt; ) {
char const cCol = t[i];
d2[0UL]         = ++i;


Maybe the inside loop can be made faster by using pointer arithmetic instead of indexing, but I'm not sure. So, you can try replacing

    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);
}


with

    size_t *d1j = d1+1, *d2j1 = d2, *d1j1 = d1;
for (size_t j = 1UL; j <= ns; ++j) {
int    const nCost = s[j-1] != cCol;
size_t const i1    = *d1j + 1;
size_t const i2    = *d2j1 + 1;
size_t const i3    = *d1j1 + nCost;
*d2j = min3(i1, i2, i3);
d1j1 = d1j++;
d2j1++;
}