javascript - 允许打字错误

Question

我想做一个测验，用户应该输入正确的答案。如果答案匹配 90%，则假设答案是正确的。例如，如果用户键入

Britney Spers而不是Britney Spears，答案应该是正确的。

我搜索了 Javascript 函数以确定答案的准确性，我发现了一些用于 PHP、Ruby 等的有趣函数，但我需要它在 JavaScript 中。

有没有人使用过这种算法？谢谢你的回答:)

Answer 1

您正在寻找一种编辑距离算法。基本上，您想查看从一个字符串到另一个字符串需要进行多少字符更改（添加/删除/替换）。当然，现在你必须有一个目标字符串字典才能找到到的距离。

http://en.wikipedia.org/wiki/Edit_distance

更具体地说：http ://en.wikipedia.org/wiki/Levenshtein_distance

Britney Spers和之间的编辑距离Britney Spears将为一： insert 'a'。

Answer 2

您正在寻找编辑距离（又名 Levenshtein 距离）。在这种方案下，两个字符串之间的距离是使字符串匹配所需的插入、删除或替换的次数。例如，如果正确答案是“橙子”，那么：

• "oranges" 的距离为 0（它们是同一个词）
• “橙色”的距离为 1（删除s）
• “roranger”的距离为 2（插入r，替代s -> r）
• "sponges" 的距离为 3 (substitute o -> s，substitute r -> p，substitute o -> a)
• "" 的距离为 7（插入每个字母oranges）

Javascript 中的简单算法如下所示（改编自此 gist并修改）：

function(a, b){
  // Return the number of characters in the other
  // string if either string is blank.
  if(a.length == 0) return b.length; 
  if(b.length == 0) return a.length; 

  // Otherwise, let's make a matrix to represent the possible choices
  // we can take.
  var matrix = [];


  var i;
  for(i = 0; i <= b.length; i++){
    matrix[i] = [i];
  }

  var j;
  for(j = 0; j <= a.length; j++){
    matrix[0][j] = j;
  }

  for(i = 1; i <= b.length; i++){
    for(j = 1; j <= a.length; j++){
      if(b.charAt(i-1) == a.charAt(j-1)){
        matrix[i][j] = matrix[i-1][j-1];
      } else {
        matrix[i][j] = Math.min(matrix[i-1][j-1] + 1, // substitution
                                Math.min(matrix[i][j-1] + 1, // insertion
                                         matrix[i-1][j] + 1)); // deletion
      }
    }
  }

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

您的问题的一个问题是您所写的关于您要查找的内容的示例（例如“匹配 90%”或“答案的准确性”）不是明确定义的指标。

答案有很多可能是错误的。例如，假设正确答案是“苹果”。哪些应该被接受？

• “APPLE”（大写错误）
• “ppple”（拼写错误）
• “apples”（复数，但你想要单数）
• “富士苹果”（太具体了）
• “水果”（太宽泛）

等等。决定哪些应该被接受超出了简单的编辑距离算法的能力，并且需要更重的工作，比如 NLP。