如何优化 levenshtein 距离以检查距离为 1？

Question

我正在开发一款游戏，我只需要检查两个单词之间的距离是否为 0 或 1，如果是，则 return 为真。我找到了一个通用的编辑距离算法：

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

有效，但这个点将成为一个热点，并且可能每秒运行数十万次，我想对其进行优化，因为我不需要通用算法，只是一个检查距离是否为 0 或 1。

我试着写了它并想到了这个：

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

但是在分析之后我发现我的代码慢了一倍，这让我很惊讶，因为我认为通用算法是 O(n*m) 而我认为我的是 O(n)。

我一直在测试这个 fiddle 的性能差异：https://jsfiddle.net/aubtze2L/3/

有没有更好的算法可以使用，或者有什么方法可以优化我的代码以使其更快？

Answer 1

如果你知道你正在寻找距离 0 和 1，那么通用 DP 算法就没有意义（顺便说一下，你展示的算法看起来很复杂，看看更好的解释 here).

要检查距离是否为0，你只需要检查2个字符串是否相同。现在，如果距离为一，则意味着插入、删除或替换都应该发生。因此从原始字符串生成所有可能的删除并检查它是否等于第二个字符串。所以你会得到这样的东西：

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

对于插入和替换，您需要知道所有字符的字母表。您可以将其定义为一个大字符串 var alphabet = "abcde...."。现在你做类似的事情，但是当你引入替换或插入时，你也会迭代字母表中的所有元素。我不打算在这里写完整的代码。

一些额外的事情。你可以在这里做很多微优化。例如，如果两个字符串的长度相差超过 1，则它们显然不能有距离 1。另一个与字符串中底层字符的频率有关。

Answer 2

考虑以下情况：

如果项的长度差大于1，则它们之间的 Levenshtein 距离将大于 1.
如果长度差恰好为 1，则最短字符串必须等于最长字符串，并删除（或插入）一次。
如果字符串长度相同，那么你应该考虑汉明距离的修改版本 returns false 如果找到两个不同的字符：

这是一个示例实现：

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

我已经更新了您的 fiddle 以包含此方法。这是我机器上的结果：

close: 154.61
lev: 176.72500000000002
sim: 32.48000000000013

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

Answer 3

我没有看到比旧的 for 循环更快的更优雅的方法：

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

性能比较(Chrome):

80.33ms - lev01（这个答案）
234.84 毫秒 - lev
708.12 毫秒 - 关闭

如何优化 levenshtein 距离以检查距离为 1？

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

javascript

algorithm

optimization

time-complexity

levenshtein-distance