使用Javascript,我想检查两个字符串之间有多少区别。

就像是:

var oldName = "Alec";
var newName = "Alexander";
var differences = getDifference(oldName, newName) // differences = 6
  • 添加到名称中的任何字母都应算作一个字母更改一次。
  • 更改字母应视为每个字母的更改。交换两个
  • 字母应该算作两次更改,因为您每次实际更改时
    来信。
  • 但是,转移一个字母并插入另一个字母仅应视为一次更改。

  • 例如:

    将“Alex”更改为“Alexander”将进行5次更改,因为添加了5个字母

    将“Alex”更改为“Allex”仅是一种更改,因为您添加了“l”并将其余部分移开但没有更改

    将“Alexander”更改为“Allesander”将进行2次更改(将“l”添加到“s”中,然后将“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);
    }
    

    但是,如何解释不算作更改的字母的移动?

    更新:这是我如何使其工作

    Levenshtein距离正是我所需要的。多亏了彼得!

    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>


    归功于James Westgate的职能:

    Jame's post showing this function

    最佳答案

    我本身没有Java脚本实现,但是您正在做一些已有完善算法的事情。具体来说,我相信您正在寻找两个字符串之间的“Levenshtein距离”,即插入,替换和删除的次数(假设您将删除视为更改)。

    The wikipedia page for Levenshtein distance有多种伪代码实现,您可以从中开始,而引用也可能对您有所帮助。

    关于javascript - 使用Javascript检测两个字符串之间的差异,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/18050932/

    10-12 20:02