2 
function levenshtein(a, b) {
  var i,j,cost,d=[];

  if (a.length == 0) {return b.length;}
  if (b.length == 0) {return a.length;}

  for ( i = 0; i <= a.length; i++) {
    d[i] = new Array();
    d[ i ][0] = i;
  }

  for ( j = 0; j <= b.length; j++) {
    d[ 0 ][j] = j;
  }

  for ( i = 1; i <= a.length; i++) {
    for ( j = 1; j <= b.length; j++) {
      if (a.charAt(i - 1) == b.charAt(j - 1)) {
        cost = 0;
      } else {
        cost = 1;
      }

      d[ i ][j] = Math.min(d[ i - 1 ][j] + 1, d[ i ][j - 1] + 1, d[ i - 1 ][j - 1] + cost);

      if (i > 1 && j > 1 && a.charAt(i - 1) == b.charAt(j - 2) && a.charAt(i - 2) == b.charAt(j - 1)) {
        d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost)
      }
    }
  }

  return d[ a.length ][b.length];
}

function suggests(suggWord) {
  var sArray = [];
  for(var z = words.length;--z;) {
    if(levenshtein(words[z],suggWord) < 2) { 
      sArray.push(words[z]);
    }   
  }
}

你好。

我正在使用 Damerau-Levenshtein 算法的上述实现。它在普通 PC 浏览器上足够快，但在平板电脑上需要约 2/3 秒。

基本上，我将发送到建议函数的单词与字典中的每个单词进行比较，如果距离小于 2，则将其添加到我的数组中。

dic 是一个大小约为 600,000 (699KB) 的单词数组，其目的是为我的 Javascript 拼写检查器提供建议单词功能。

关于如何加快速度的任何建议？或者另一种方式来做到这一点？

4

4 回答 4

4

如果您只寻找小于某个阈值的距离，您可以做的一件事是首先比较长度。例如，如果您只希望距离小于 2，那么两个字符串长度之差的绝对值也必须小于 2。这样做通常可以让您避免进行更昂贵的 Levenshtein 计算。

这背后的原因是，长度相差 2 的两个字符串将需要至少两次插入（因此产生的最小距离为 2）。

您可以按如下方式修改您的代码：

function suggests(suggWord) {
  var sArray = [];
  for(var z = words.length;--z;) {
    if(Math.abs(suggWord.length - words[z].length) < 2) {
      if (levenshtein(words[z],suggWord) < 2) { 
        sArray.push(words[z]);
      }
    }   
  }
}

我不怎么做javascript，但我认为这就是你可以做到的。

部分问题是您有大量的字典单词，并且至少对这些单词中的每一个都进行了一些处理。一个想法是为每个不同的单词长度设置一个单独的数组，并将您的字典单词组织到其中而不是一个大数组中（或者，如果您必须有一个大数组，用于 alpha 查找或其他什么，那么使用索引数组进入那个大数组）。然后，如果您有一个 5 个字符长的 suggWord，您只需查看 4、5 和 6 个字母单词的数组。然后，您可以在我上面的代码中删除 Match.Abs​​(length-length) 测试，因为您知道您只查看长度可以匹配的单词。这使您不必对大量字典单词进行任何处理。

Levenshtein 相对昂贵，对于较长的单词更是如此。如果仅仅是 Levenshtein 太昂贵而无法多次执行的情况，尤其是对于较长的单词，您可以利用阈值的另一个副作用，即仅考虑完全匹配或距离为 1 的单词（一次插入、删除、替换或转座）。鉴于该要求，您可以通过检查它们的第一个字符匹配或最后一个字符匹配（除非任一单词的长度为 1 或 2，在这种情况下，Levenshtein 应该很便宜）来进一步过滤 Levenshtein 计算的候选者。事实上，您可以检查前 n 个字符或后 n 个字符的匹配，其中 n = (suggWord.length-1)/2。如果他们没有通过那个测试，你可以假设他们会' 通过 Levenshtein 匹配。为此，您需要按字母顺序排列的字典单词的主要数组，以及该数组的索引数组，但按字母顺序按字母顺序排列。然后你可以对这两个数组进行二进制搜索，并且只需要对它们的开始或结束的 n 个字符与 suggWord 开始或结束匹配的单词的小子集进行 Levenshtein 计算，并且长度不同最多一个字符。

于 2012-07-09T15:44:09.537 回答
3

我不得不优化相同的算法。对我来说最有效的是缓存 d 数组。你在 levenshtein 函数之外用大尺寸（你期望的字符串的最大长度）创建它，所以每次调用函数时都不必重新初始化它.

就我而言，在 Ruby 中，它在性能上产生了巨大的差异。但当然这取决于你的words数组的大小......

function levenshtein(a, b, d) {

var i,j,cost;

if (a.length == 0) {return b.length;}
if (b.length == 0) {return a.length;}

for ( i = 1; i <= a.length; i++) {

    for ( j = 1; j <= b.length; j++) {

        if (a.charAt(i - 1) == b.charAt(j - 1)) {

            cost = 0;

        } else {

            cost = 1;

        }

        d[ i ][j] = Math.min(d[ i - 1 ][j] + 1, d[ i ][j - 1] + 1, d[ i - 1 ][j - 1] + cost);

        if (i > 1 && j > 1 && a.charAt(i - 1) == b.charAt(j - 2) && a.charAt(i - 2) == b.charAt(j - 1)) {

            d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost)

        }

    }

}

return d[ a.length ][b.length];

}

function suggests(suggWord)
{
d = [];
for ( i = 0; i <= 999; i++) {

    d[i] = new Array();

    d[ i ][0] = i;

}
for ( j = 0; j <= 999; j++) {

    d[ 0 ][j] = j;

}


var sArray = [];
for(var z = words.length;--z;)
{
        if(levenshtein(words[z],suggWord, d) < 2)
        {sArray.push(words[z]);}    
}
}
于 2012-07-09T15:41:31.907 回答
2

您可以在代码中做一些简单的事情来从根本上提高执行速度。我完全重写了您的代码以提高性能、符合 JIT 解释的静态类型以及符合 JSLint：

var levenshtein = function (a, b) {
        "use strict";
        var i = 0,
            j = 0,
            cost = 1,
            d = [],
            x = a.length,
            y = b.length,
            ai = "",
            bj = "",
            xx = x + 1,
            yy = y + 1;
        if (x === 0) {
            return y;
        }
        if (y === 0) {
            return x;
        }
        for (i = 0; i < xx; i += 1) {
            d[i] = [];
            d[i][0] = i;
        }
        for (j = 0; j < yy; j += 1) {
            d[0][j] = j;
        }
        for (i = 1; i < xx; i += 1) {
            for (j = 1; j < yy; j += 1) {
                ai = a.charAt(i - 1);
                bj = b.charAt(j - 1);
                if (ai === bj) {
                    cost = 0;
                } else {
                    cost = 1;
                }
                d[i][j] = Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost);
                if (i > 1 && j > 1 && ai === b.charAt(j - 2) && a.charAt(i - 2) === bj) {
                    d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
                }
            }
        }
        return d[x][y];
    };

在多维查找的每个间隔查找数组的长度是非常昂贵的。我还使用http://prettydiff.com/美化了您的代码，这样我就可以在一半的时间内阅读它。我还删除了数组中的一些冗余查找。如果这对您来说执行得更快，请告诉我。

于 2012-07-09T16:39:30.180 回答
2

您应该将所有单词存储在trie中。与存储单词的字典相比，这是节省空间的。匹配单词的算法是遍历 trie（标记单词的结尾）并找到单词。

编辑

就像我在评论中提到的那样。对于 0 或 1 的 Levenshtein 距离，您不需要遍历所有单词。如果两个词相等，则它们的 Levenshtein 距离为 0。现在问题归结为预测给定单词的 Levenshtein 距离为 1 的所有单词。举个例子：

大批

对于上述单词，如果您想找到 1 的 Levenshtein 距离，示例将是

  • parray, aprray, arpray, arrpay, arrayp (插入一个字符)

这里 p 可以用任何其他字母代替。

同样对于这些单词，Levenshtein 距离为 1

ray, aray, arry (删除一个字符)

最后是这些话：

pray、apray、arpay、arrpy 和 arrap （字符替换）

同样，p 可以替换为任何其他字母。

因此，如果您只查找这些特定组合而不是所有单词，您将得到您的解决方案。如果您知道 Levenshtein 算法的工作原理，我们已经对其进行了逆向工程。

最后一个例子是你的用例：

如果pary是您作为输入获得的单词，则应将其更正以从字典中分离出来。因此，对于pary，您不需要查看以ab开头的单词，例如，因为对于任何以ab开头的单词，Levenshtein 距离将大于 1。

于 2012-07-09T15:47:38.140 回答