javascript - 使用 JavaScript 对用户响应进行评分(比较两个数组)

Question

我正在编写一个脚本，通过比较两个数组来对用户响应进行评分。 (这是一个测验，看看他们对信息的逐字了解程度。)我已经有了一些我需要的代码，比如将用户响应设为小写并将其拆分。我所需要的只是找出差异/错误的数量。例如:

var correctanswer = ["The","quick","brown","fox","jumped","over","the","lazy","dog"];
var useranswer = ["The","brown","fox","jumped","up","and","over","the","really","lazy","cat"];
alert(counterrors(correctanswer, useranswer));

在这个特定的例子中，运行我正在寻找的函数会返回用户犯了 5 个错误(他们省略“快速”，添加“向上”， “和”，和“真的”，并且将“狗”改为“猫”)。如您所见，这两个数组的长度可能不同。

有人知道如何处理这个问题吗？我在想这可能是一个像这样的循环:

for (x in correctanswer) {
    // compare correctanswer[x] to useranswer[x]... not sure how exactly. Seems tricky...
}

感谢您的关注!我看过 John Resig 的差异解决方案 ( http://ejohn.org/projects/javascript-diff-algorithm/ ) 和其他类似的东西，甚至还有一些数组比较，但似乎没有任何效果，因为我发现的那些返回了所有差异，而我想看看有多少差异。再次感谢您的浏览，如有任何问题，请告诉我。

更新:非常感谢 Magnar 的回答!它运行良好。

Answer 1

你要找的是 The Levenshtein Distance两个数组的。

它是一种算法，用于计算将一个序列转换为另一个序列所需的添加、删除 和替换 的数量。

Wikipedia page I linked有一个伪代码实现。我已经为你做了一个 JavaScript 的逐行翻译:

var correctanswer = ["The","quick","brown","fox","jumped","over","the","lazy","dog"];
var useranswer =    ["The","brown","fox","jumped","up","and","over","the","really","lazy","cat"];

console.log(calculate_levenshtein_distance(correctanswer, useranswer));

function calculate_levenshtein_distance(s, t) {
  var m = s.length + 1, n = t.length + 1;
  var i, j;

  // for all i and j, d[i,j] will hold the Levenshtein distance between
  // the first i words of s and the first j words of t;
  // note that d has (m+1)x(n+1) values
  var d = [];

  for (i = 0; i < m; i++) {
    d[i] = [i]; // the distance of any first array to an empty second array
  }
  for (j = 0; j < n; j++) {
    d[0][j] = j; // the distance of any second array to an empty first array
  }

  for (j = 1; j < n; j++) {
    for (i = 1; i < m; i++) {
      if (s[i - 1] === t[j - 1]) {
        d[i][j] = d[i-1][j-1];           // no operation required
      } else {
        d[i][j] = Math.min(
                    d[i - 1][j] + 1,     // a deletion
                    d[i][j - 1] + 1,     // an insertion
                    d[i - 1][j - 1] + 1  // a substitution
                  );
      }
    }
  }

  return d[m - 1][n - 1];
}

这会将 5 记录到控制台。正如您将看到的，这就是阵列之间的正确距离。学生没有添加 lazy。所以它是 1 个删除，3 个添加和 1 个替换。