phát hiện sự khác biệt giữa hai chuỗi với Javascript

Question

Với Javascript, tôi muốn kiểm tra xem có bao nhiêu khác biệt giữa hai chuỗi.

Cái gì như:

var oldName = "Alec"; 
var newName = "Alexander"; 
var differences = getDifference(oldName, newName) // differences = 6 

• Bất kỳ chữ thêm vào tên nên được tính là một sự thay đổi mỗi lá thư.
• Thay đổi một chữ cái nên được tính là thay đổi cho mỗi chữ cái. Xoay hai chữ số
• chữ nên được tính là hai thay đổi khi bạn thực sự thay đổi từng chữ số
  leter.
• Tuy nhiên, việc chuyển một chữ cái và chèn một chữ khác chỉ được tính là một thay đổi.

Ví dụ:

Thay đổi "Alex" thành "Alexander" sẽ là 5 thay đổi như 5 chữ đã được thêm vào

Thay đổi "Alex" thành "Allex" sẽ chỉ là một sự thay đổi như bạn đã thêm "l" và chuyển phần còn lại nhưng không thay đổi chúng

Thay đổi "Alexander" thành "Allesander" sẽ là 2 thay đổi (thêm "l" và thay đổi "x" thành "s").

tôi có thể chia mỗi tên vào một mảng của các chữ cái và so sánh chúng dễ dàng đủ như trong jsFiddle này với các chức năng dưới đây:

function compareNames(){ 
    var oldName = $('#old').val().split(""); 
    var newName = $('#new').val().split(""); 
    var changeCount = 0; 
    var testLength = 0; 
    if(oldName.length > newName.length){ 
     testLength=oldName.length;  
    } 
    else testLength=newName.length; 
    for(var i=0;i<testLength;i++){ 
     if(oldName[i]!=newName[i]) { 
      changeCount++;   
     } 
    } 
    alert(changeCount); 
} 

Nhưng làm thế nào tôi có thể giải thích cho sự chuyển dịch của các chữ cái không đếm như một thay đổi?

---

Cập nhật: Đây là cách tôi đã nhận nó làm việc

khoảng cách levenshtein là chính xác những gì tôi cần. Cảm ơn Peter!

Working jsFiddle

$(function() { 
 
    $('#compare').click(function() { 
 
     var oldName = $('.compare:eq(0)').val(); 
 
     var newName = $('.compare:eq(1)').val(); 
 
     var count = levDist(oldName, newName); 
 
     $('#display').html('There are ' + count + ' differences present'); 
 
    }); 
 
}); 
 

 
function levDist(s, t) { 
 
    var d = []; //2d matrix 
 

 
    // Step 1 
 
    var n = s.length; 
 
    var m = t.length; 
 

 
    if (n == 0) return m; 
 
    if (m == 0) return n; 
 

 
    //Create an array of arrays in javascript (a descending loop is quicker) 
 
    for (var i = n; i >= 0; i--) d[i] = []; 
 

 
    // Step 2 
 
    for (var i = n; i >= 0; i--) d[i][0] = i; 
 
    for (var j = m; j >= 0; j--) d[0][j] = j; 
 

 
    // Step 3 
 
    for (var i = 1; i <= n; i++) { 
 
     var s_i = s.charAt(i - 1); 
 

 
     // Step 4 
 
     for (var j = 1; j <= m; j++) { 
 

 
      //Check the jagged ld total so far 
 
      if (i == j && d[i][j] > 4) return n; 
 

 
      var t_j = t.charAt(j - 1); 
 
      var cost = (s_i == t_j) ? 0 : 1; // Step 5 
 

 
      //Calculate the minimum 
 
      var mi = d[i - 1][j] + 1; 
 
      var b = d[i][j - 1] + 1; 
 
      var c = d[i - 1][j - 1] + cost; 
 

 
      if (b < mi) mi = b; 
 
      if (c < mi) mi = c; 
 

 
      d[i][j] = mi; // Step 6 
 

 
      //Damerau transposition 
 
      if (i > 1 && j > 1 && s_i == t.charAt(j - 2) && s.charAt(i - 2) == t_j) { 
 
       d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost); 
 
      } 
 
     } 
 
    } 
 
    // Step 7 
 
    return d[n][m]; 
 
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"></script> 
 
<input type="button" id="compare" value="Compare" /><br><br> 
 
<input type="text" id="old" class="compare" value="Alec" /> 
 
<input type="text" id="new" class="compare" value="Alexander" /> 
 
<br> 
 
<br> 
 
<span id="display"></span>

tín dụng đối với James Westgate cho hàm:

Jame's post showing this function

Answer 1

Tôi không có một thực hiện Javascript trên tay cho mỗi gia nhập, nhưng bạn đang làm gì đó để tồn tại các thuật toán được thiết lập tốt. Cụ thể, tôi tin rằng bạn đang tìm kiếm "khoảng cách Levenshtein" giữa hai chuỗi - tức là số lần chèn, thay thế và xóa (giả sử bạn đang xử lý xóa là thay đổi).

The wikipedia page for Levenshtein distance có nhiều triển khai mã giả khác nhau mà từ đó bạn có thể bắt đầu và tham chiếu cũng có thể giúp bạn.

Answer 2

Alternative implemenation:

/** 
* Computes the Levenshtein edit distance between two strings. 
* @param {string} a 
* @param {string} b 
* @return {number} The edit distance between the two strings. 
*/ 
goog.string.editDistance = function(a, b) { 
    var v0 = []; 
    var v1 = []; 

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

    if (!a.length || !b.length) { 
    return Math.max(a.length, b.length); 
    } 

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

    for (var i = 0; i < a.length; i++) { 
    v1[0] = i + 1; 

    for (var j = 0; j < b.length; j++) { 
     var cost = Number(a[i] != b[j]); 
     // Cost for the substring is the minimum of adding one character, removing 
     // one character, or a swap. 
     v1[j + 1] = Math.min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost); 
    } 

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

    return v1[b.length]; 
};