How to optimize levenshtein distance for checking for a distance of 1?

Question

I'm working on a game where I only need to check if there's a distance of 0 or 1 between two words and return true if that's the case. I found a general purpose levenshtein distance algorithm:

function levenshtein(s, t) {
  if (s === t) { return 0; }
  var n = s.length, m = t.length;
  if (n === 0 || m === 0) { return n + m; }
  var x = 0, y, a, b, c, d, g, h, k;
  var p = new Array(n);
  for (y = 0; y < n;) { p[y] = ++y; }
  for (;
    (x + 3) < m; x += 4) {
    var e1 = t.charCodeAt(x);
    var e2 = t.charCodeAt(x + 1);
    var e3 = t.charCodeAt(x + 2);
    var e4 = t.charCodeAt(x + 3);
    c = x; b = x + 1; d = x + 2; g = x + 3; h = x + 4;

    for (y = 0; y < n; y++) {
      k = s.charCodeAt(y);
      a = p[y];

      if (a < c || b < c) { c = (a > b ? b + 1 : a + 1); }
      else { if (e1 !== k) { c++; } }

      if (c < b || d < b) { b = (c > d ? d + 1 : c + 1); } 
      else { if (e2 !== k) { b++; } }

      if (b < d || g < d) { d = (b > g ? g + 1 : b + 1); } 
      else { if (e3 !== k) { d++; } }

      if (d < g || h < g) { g = (d > h ? h + 1 : d + 1); }
      else { if (e4 !== k) { g++; } }

      p[y] = h = g; g = d; d = b; b = c; c = a;
    }
  }

  for (; x < m;) {
    var e = t.charCodeAt(x);
    c = x;
    d = ++x;
    for (y = 0; y < n; y++) {
      a = p[y];
      if (a < c || d < c) { d = (a > d ? d + 1 : a + 1); } 
      else {
        if (e !== s.charCodeAt(y)) { d = c + 1; }
        else { d = c; }
      }
      p[y] = d;
      c = a;
    }
    h = d;
  }

  return h;
}

Which works, but this spot is going to be a hotspot and be run potentially hundreds of thousands of times a second and I want to optimize it because I don't need a general purpose algorithm, just one that checks if there's a distance of 0 or 1.

I tried writing it and came up with this:

function closeGuess(guess, word) {
  if (Math.abs(word.length - guess.length) > 1) { return false; }

  var errors = 0, guessIndex = 0, wordIndex = 0;

  while (guessIndex < guess.length || wordIndex < word.length) {
    if (errors > 1) { return false; }
    if (guess[guessIndex] !== word[wordIndex]) {
      if (guess.length < word.length) { wordIndex++; }
      else { guessIndex++; }
      errors++;
    } else {
      wordIndex++;
      guessIndex++;
    }
  }

  return true;
}

But after profiling it I found that my code was twice as slow, which surprised me because I think the general purpose algorithm is O(n*m) and I think mine is O(n).

I've been testing the performance difference on this fiddle: https://jsfiddle.net/aubtze2L/3/

Are there any better algorithms I can use or any way I can optimize my code to be faster?

Answer 1

I don't see a more elegant way which is at the same time faster than the good old for-loop:

function lev01(a, b) {
  let la = a.length;
  let lb = b.length;
  let d = 0;
  switch (la - lb) {
    case 0: // mutation
      for (let i = 0; i < la; ++i) {
        if (a.charAt(i) != b.charAt(i) && ++d > 1) {
          return false;
        }
      }
      return true;
    case -1: // insertion
      for (let i = 0; i < la + d; ++i) {
        if (a.charAt(i - d) != b.charAt(i) && ++d > 1) {
          return false;
        }
      }
      return true;
    case +1: // deletion
      for (let i = 0; i < lb + d; ++i) {
        if (a.charAt(i) != b.charAt(i - d) && ++d > 1) {
          return false;
        }
      }
      return true;
  }
  return false;
}

console.log(lev01("abc", "abc"));
console.log(lev01("abc", "abd"));
console.log(lev01("abc", "ab"));
console.log(lev01("abc", "abcd"));
console.log(lev01("abc", "cba"));

Performance comparison (Chrome):

• 80.33ms - lev01 (this answer)
• 234.84ms - lev
• 708.12ms - close

Answer 2

Consider the following cases:

1. If the difference in lengths of the terms is greater than 1, then the Levenshtein distance between them will be greater than 1.
2. If the difference in lengths is exactly 1, then the shortest string must be equal to the longest string, with a single deletion (or insertion).
3. If the strings are the same length then you should consider a modified version of Hamming distance which returns false if two, different characters are found:

Here is a sample implementation:

var areSimilar;

areSimilar = function(guess, word) {
  var charIndex, foundDiff, guessLength, lengthDiff, substring, wordLength, shortest, longest, shortestLength, offset;

  guessLength = guess.length;
  wordLength = word.length;

  lengthDiff = guessLength - wordLength;
  if (lengthDiff < -1 || lengthDiff > 1) {
    return false;
  }

  if (lengthDiff !== 0) {
    if (guessLength < wordLength) {
      shortest = guess;
      longest = word;
      shortestLength = guessLength;
    } else {
        shortest = word;
      longest = guess;
      shortestLength = wordLength;
    }

    offset = 0;
    for (charIndex = 0; charIndex < shortestLength; charIndex += 1) {
        if (shortest[charIndex] !== longest[offset + charIndex]) {
        if (offset > 0) {
            return false; // second error
        }
        offset = 1;
        if (shortest[charIndex] !== longest[offset + charIndex]) {
            return false; // second error
        }
      }
    }

    return true; // only one error
  }

  foundDiff = false;
  for (charIndex = 0; charIndex < guessLength; charIndex += 1) {
    if (guess[charIndex] !== word[charIndex]) {
      if (foundDiff) {
        return false;
      }
      foundDiff = true;
    }
  }
  return true;
};

I've updated your fiddle to include this method. Here are the results on my machine:

close: 154.61
lev: 176.72500000000002
sim: 32.48000000000013

Fiddle: https://jsfiddle.net/dylon/aubtze2L/11/

Answer 3

If you know that you are looking for distance 0 and 1, then the general purpose DP algorithm does not make sense (and by the way the algorithm you showed looks convoluted, take a look at a better explanation here).

To check that the distance is 0, all you need is to check whether 2 strings are the same. Now if the distance is one, it means that either insertion, deletion or substitution should have happened. So generate all possible deletion from the original string and check whether it is equal to second string. So you will get something like this:

for (var i = 0; i < s_1.length; i++) {
  if s_2 == s_1.slice(0, i) + s_1.slice(i + 1) {
     return true
  }
}

For insertions and substitution you will need to know the alphabet of all characters. You can define it as a big string var alphabet = "abcde....". Now you do a similar thing, but when you introduce substitution or insertion, you also iterate over all elements in your alphabet. I am not planning to write the whole code here.

A couple of additional things. You can make a lot of micro-optimizations here. For example if the length of two strings are different by more than 1, they clearly can't have a distance 1. Another one relates to the frequencies of underlying characters in the string.