获取两个数组/字符串之间的差异（添加和删除）

我有一个array，它被用户输入（键盘）更新。我想跟踪哪些条目改变以获得更好的现场表演。获取两个数组/字符串之间的差异（添加和删除）

下面的例子：

// ascii values for 'Stuckoverflow' 
var previousBlocks = [ 
    83, 116, 117, 99, 107, 111, 118, 
    101, 114, 102, 108, 111, 119 
]; 

// ascii values for 'Stackedoverflow2014' 
var blocks = [ 
    83, 116, 97, 99, 107, 101, 100, 111, 118, 
    101, 114, 102, 108, 111, 119, 
    50, 48, 49, 52 
];

我想已经添加或删除previousBlocks到blocks条目的位置。较大的不变部分应保持完整。（在这种情况下“溢出”）

var result = { 
    deletions: [2], 
    additions: [2, 5, 6, 13, 14, 15, 16] 
};

易读，差异可以表示这样的：

St[-u][+a]ck[+e][+d]overflow[+2][+0][+1][+4]

来源

2014-10-06 ffraenz

请参阅“编辑距离”和/或“动态编程”。例如。 http://cs.brynmawr.edu/Courses/cs330/spring2012/SpellingCheckers.pdf，http：//bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Lec6-EditDistance.pdf，http：// alikhuram .wordpress.com/2013/4月27日/动态规划 - 编辑距离/ – user2864740 2014-10-06 00:50:10

由于array获取由用户操作（键入），改变被聚类。该解决方案计算一个范围的变化并确定替换块。这是一个非常简单的解决方案，但它的工作。

var start = 0; 
var end = 0; 
var length = Math.min(previousBlocks.length, length); 

// compare from left to right 
while (
    start < length 
    && previousBlocks[start] 
     == blocks[start] 
) { 
    start ++; 
} 

// compare from right to left 
while (
    end < length - start 
    && previousBlocks[previousBlocks.length - end - 1] 
     === blocks[blocks.length - end - 1] 
) { 
    end ++; 
} 

// collect the blocks that have been added 
var rangeBlocks = []; 
for (var i = start; i < blocks.length - end; i ++) 
{ 
    rangeBlocks.push(blocks[i]); 
} 

return { 
    // unchanged amount of blocks on the left 
    startOffset: start, 

    // unchanged amount of blocks on the right 
    endOffset: end, 

    // exchange/replace the changed part by these blocks 
    blocks: rangeBlocks 
};

来源

2014-10-24 12:38:09 ffraenz

获取两个数组/字符串之间的差异（添加和删除）

回答

相关问题