2013-10-04 135 views
0

我想在Javascript中構建一個文件比較腳本,它需要兩個版本的文件並輸出類似Github的東西來顯示添加和刪除。儘管如此,我仍然遇到了算法的邏輯問題。以下是我過程中的僞代碼:文件比較腳本的邏輯

var j = 0; 
// check current file line by line 
for(i=0; i < currentFileArr.length; i++){ 

    // see if the current line is different 
    if(currentFileArr[i] !== previousFileArr[j]){ 

     if(previousFile.contains(currentFileArr[i])){ 
      // line is a deletion. find next line that wasn't deleted 
      while(currentFileArr[i] !== previousFileArr[j]){ 
       j++; 
      } 
     } else { 
      // line is an addition 
     } 
    } else { // lines are the same 
     j++; 
    } 
} 

主要問題是對於不是唯一的行。就像只有一個花括號的新線條或線條一樣。

+3

或者如果我添加重複行?或刪除重複的行?或重新縮進整個代碼而不改變任何東西?對於一個簡單的項目來說,這是一座橋樑我不久前嘗試了一些非常接近你的東西......不要重新發明輪子;花時間定製https://code.google.com/p/google-diff-match-patch/以適應您的項目需求。如果你必須堅持你的代碼,至少在比較前修剪()行以忽略空白和縮進變化... – dandavis

回答

1

您需要考慮文件中的每個唯一行作爲metachar,即某些擴展字母表的「字符」。通過這種方式,你的兩個文件都會變成「字符串」。

最有效的方法 - 創建散列表,包含唯一字符串,並在表中使用索引作爲元字符。

此後,您可以通過Levenshtein算法搜索這些字符串之間的最小編輯序列 :

http://www.let.rug.nl/kleiweg/lev/levenshtein.html

http://en.wikipedia.org/wiki/Levenshtein_distance

http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance