獲取兩個數組/字符串之間的差異（添加和刪除）

我有一個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

獲取兩個數組/字符串之間的差異（添加和刪除）

回答

相關問題