Write a typo correction program with Levenshtein distance algorithm

Question

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.

Answer 1

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