What is the fastest levenshtein algorithm for high frequent use [duplicate]

Question

This question already has answers here:

Sort an array by the "Levenshtein Distance" with best performance in Javascript (7 answers)

Closed 8 years ago.

For a client side search tool I need to find the Levenshtein distance of a word with millions of other words. A user should be able to compare a short text of about twenty words with a book. The user could do this by finding locations of the most characterizing words of the text in the book. 'Finding locations'does not mean looking for an exact match but nearly match as with levenshtein. I started with already available implementations but I needed more speed. I ended up with this:

var rowA = new Uint16Array(1e6);
var rowB = new Uint16Array(1e6);
function levenshtein(s1, s2) {
    var s1_len = s1.length, s2_len = s2.length, i1, i2 = 0, a, b, c, c2, i = 0;
    if (s1_len === 0)
        return s2_len;
    if (s2_len === 0)
        return s1_len;
    while (i < s1_len)
        rowA[i] = ++i;
    while (i2 < s2_len) {
        c2 = s2[i2];
        a = i2;
        ++i2;
        b = i2;
        for (i1 = 0; i1 < s1_len; ++i1) {
            c = a + (s1[i1] !== c2 );
            a = rowA[i1];
            b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
            rowB[i1] = b;
        }
        if (i2 === s2_len)
            return b;
        c2 = s2[i2];
        a = i2;
        ++i2;
        b = i2;
        for (i1 = 0; i1 < s1_len; ++i1) {
            c = a + (s1[i1] !== c2 );
            a = rowB[i1];
            b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
            rowA[i1] = b;
        }
    }
    return b;
}

As you see I used techniques like placing the objects out of the function in order to re use them. I also repeated myself a bit by linearizing the loop somewhat. Could it be faster? I am curious of your advice.

Update: After tips from Bergi and some more thinking I came to this solution:

    var row = new Uint16Array(1e6);
    function levenshtein(s1, s2) {
        var s1_len = s1.length, s2_len = s2.length, i2 = 1, a, b = 0, c, c2, i1 = 0;
        if (s1_len === 0)
            return s2_len;
        if (s2_len === 0)
            return s1_len;
        c2 = s2[0];
        if (s1[0] === c2) {
            while (i1 < s1_len) {
                row[i1] = i1++;
            }
            b = s1_len - 1;
        } else {
            row[0] = 1;
            ++b;
            if (s1_len > 1)
                for (i1 = 1; i1 < s1_len; ++i1) {
                    if (s1[i1] === c2) {
                        row[i1] = b;
                        for (++i1; i1 < s1_len; ++i1) {
                            row[i1] = ++b;
                        }
                    } else {
                        row[i1] = ++b;
                    }
                }
        }
        if (s2_len > 1)
            while (i2 < s2_len) {
                c2 = s2[i2];
                c = i2 + (s1[0] !== c2);
                a = row[0];
                ++i2;
                b = i2 < a ? (i2 < c ? i2 + 1 : c) : (a < c ? a + 1 : c);
                row[0] = b;
                if (s1_len > 1) {
                    for (i1 = 1; i1 < s1_len; ++i1) {
                        c = a + (s1[i1] !== c2);
                        a = row[i1];
                        b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
                        row[i1] = b;
                    }
                }
            }
        return b;
    }

This is again much faster. I cannot squeeze more out of it. I keep looking for other ideas and will try some more.

Answer 1

Since you are comparing against the same word over and over, you can get a little performance improvement by using partial application and caching there:

function levenshtein(s1) {
    var row0 = [], row1 = [], s1_len = s1.length;
    if (s1_len === 0)
        return function(s2) {
            return s2.length;
        };
    return function(s2) {
        var s2_len = s2.length, s1_idx, s2_idx = 0, a, b, c, c2, i = 0;
        if (s2_len === 0)
            return s1_len;
        …
        return b;
    };
}

I also repeated myself a bit by linearizing the loop somewhat.

Not sure whether it gets lot faster, but you can omit one of the arrays - you do not need to read/write them in an alternating manner:

function levenshtein(s1) {
    var s1_len = s1.length, row = new Array(s1_len);
    if (s1_len === 0)
        return function(s2) {
            return s2.length;
        };
    return function(s2) {
        var s2_len = s2.length, s1_idx, s2_idx = 0, a, b, c, c2, i = 0;
        if (s2_len === 0)
            return s1_len;
        while (i < s1_len)
           row[i] = ++i;
        while (s2_idx < s2_len) {
            c2 = s2[s2_idx];
            a = s2_idx;
            ++s2_idx;
            b = s2_idx;
            for (s1_idx = 0; s1_idx < s1_len; ++s1_idx) {
                c = a + (s1[s1_idx] === c2 ? 0 : 1);
                a = row[s1_idx];
                b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
                row[s1_idx] = b;
            }
        }
        return b;
    };
}

I don't think further optimisations can be made without putting your millions of words in a dedicated data structure (e.g. a prefix trie).