允許輸入錯誤

我想進行測驗，用戶應輸入正確的答案。假設答案與90％匹配，則答案是正確的。例如，如果用戶鍵入允許輸入錯誤

Britney Spers而不是Britney Spears，答案應該是正確的。

我搜索了Javascript函數來確定答案的準確程度，我發現了一些PHP，Ruby等有趣的函數，但我需要JavaScript。

有沒有人有這種算法的經驗？謝謝，如果你回答:)

來源

2012-04-22 Jonny Burger

您正在尋找的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％」或「答案的準確性」）不是明確定義的指標。

有很多答案可能是錯誤的方法。例如，讓我們說正確的答案是「蘋果」。哪些應該被接受？