允许输入错误

Question

我想进行测验，用户应输入正确的答案。 假设答案与90％匹配，则答案是正确的。例如，如果用户键入

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

我搜索了Javascript函数来确定答案的准确程度，我发现了一些PHP，Ruby等有趣的函数，但我需要JavaScript。

有没有人有这种算法的经验？ 谢谢，如果你回答:)

Answer 1

您正在寻找的edit distance（aka Levenshtein距离）。在该方案下，所述距离两者之间的字符串是插入，缺失，或取代使串匹配所需的数量。例如，如果正确的回答是“橘子”，则：

• “桔子”具有为0的距离（它们是相同的字）
• “橙色”具有1的距离（删除s）
• “roranger” 具有2的距离（插入r，替换s -> r）
• “海绵” 具有3的距离（替代o -> s，替换r -> p，替换o -> a）
• “” 具有7的距离（ inser吨oranges每一个字母）

在Javascript中一个简单的算法，它看起来像这样（改编和this 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”（拼写错误）
• “苹果”（复数，但你想要的单数）
• “富士苹果”（太具体的）
• “水果”（太宽）

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

Answer 2

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

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

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

Britney Spers和Britney Spears之间的编辑距离将是一个：插入'a'。