Обнаруживать различия между двумя строками с помощью Javascript

С Javascript я хочу проверить, сколько разностей между двумя строками.

Что-то вроде:

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

Любые буквы, добавленные к имени, должны считаться одним изменением для каждой буквы.
Изменение буквы должно считаться изменением на письмо. Преобразование двух
письма должны считаться двумя изменениями, так как вы действительно меняете каждый leter.
Однако перемещение буквы и вставка другого должно учитываться только как одно изменение.

Например:

Изменение "Alex" на "Alexander" будет 5 изменений по мере добавления 5 букв

Изменение "Alex" на "Allex" будет только одним изменением, поскольку вы добавили "l" и переместили остальные, но не изменили их.

Изменение "Александра" на "Алессандер" было бы 2 изменения (добавив "l" и изменив "x" на "s" ).

Я могу разделить каждое имя на массив букв и сравнить их достаточно легко, как в этом jsFiddle с помощью следующей функции:

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);
}

Но как я могу объяснить смещение букв, не считая изменений?

Обновление: здесь, как я получил его

Расстояние Левенштейна было именно тем, что мне нужно. Спасибо Петру!

Работает 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>

Ответ 1

У меня нет реализации Javascript как таковой, но вы делаете что-то, для чего существуют общепринятые алгоритмы. В частности, я считаю, что вы ищете "расстояние Левенштейна" между двумя строками - то есть количество вставок, замещений и удалений (при условии, что вы обрабатываете удаление в качестве изменения).

Страница википедии для расстояния Левенштейна имеет различные реализации псевдокода, из которых вы можете начать, и ссылки, которые также могут помочь вам.

Ответ 2

Альтернативная реализация:

/**
 * 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];
};

Ответ 3

Нет, мне нужно выделить изменения или различия между двумя строками, такими как s = ram и se = ram1, теперь 1 будет выделен при нажатии кнопки.