欢迎您来到芯片的主页!

Welcome to Chipset's homepage!

不同版本代码差分

比较不同版本代码差异的工具多如牛毛,但基本原理都一样,都需要比较两个不同版本代码文件的差异和相同之处。最终都需要逐行比较内容(有时可能需要忽略空格,Tab字符等),这个算法的基本原理如下:
(假设a, b, c...顺序代表两个源代码文件的不同代码行) 
老版本文件            : a b c d f g h j q z
新版本文件            : a b c d e f g i j k r x y z
最长公共子序列      : a b c d f g j z
added + omitted:              e   h i q k r x y
old - csq            :                   -   -
new - csq          :              +    +   + + + +
omitted             :                   h   q
added               :              e      i    k r x y

注意最长公共子序列可不一定是最长的公共子窜,最长公共子窜通常是最长公共子序列的子集而已。假设第一个文件长度是M,第二个文件长度是N,那么上述比较算法的时间复杂度是O(M*N)。最原始的求最长公共子序列的算法空间复杂度是O(M*N), 对于大文件而言,显然耗费内存太多。D.S. Hirschberg后来提出了一种减小内存耗费的改进算法,仍然使用最基本的原理,只不过不保留中间计算结果,后来需要的时候再重新计算出来,用时间换空间,他的算法空间复杂度是O(M+N),但时间复杂度的常数因子不可避免的要大一些。求最长公共子序列算法的基本理论在基础维基百科上有详尽的论述,http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
在网上搜索一下D.S. Hirschberg算法,能找到源代码片段,稍微修改下,贴在这里,注意这段程序的效率不太高,实际应用中可能需要进一步优化。

  1 /*
  2   Fill the LCS sequence from the std::vector<bool> of a sequence
  3   pos is an iterator point to the current sequence
  4   lcs is the container which will hold the longest common subsequence
  5 */
  6 template <typename InputIterator, typename SeqCont>
  7 void set_lcs(InputIterator pos, const std::vector<bool>& vb, SeqCont& lcs)
  8 {
  9   for(std::vector<bool>::const_iterator it(vb.begin()); it != vb.end(); ++it, ++pos)
 10     if(*it)
 11       std::back_inserter(lcs) = *pos;
 12 }
 13 
 14 /*
 15   Calculate LCS row std::vector<int32_t> given iterator ranges into two sequences.
 16   On completion, 'result' holds LCS std::vector<int32_t> in the final row.
 17   This is a slow operation!
 18 */
 19 template <typename InputIterator>
 20 void lcs_vect(InputIterator first1, InputIterator last1,
 21                     InputIterator first2, InputIterator last2,
 22                     std::vector<int32_t>& result)
 23 {
 24   // Two rows of workspace.
 25   // Careful! We need the 1st for the leftmost column.
 26   std::vector<int32_t> curr(std::distance(first2, last2) + 10);
 27   std::vector<int32_t> prev(curr);
 28 
 29   for(InputIterator it1 = first1; it1 != last1; ++it1)
 30   {
 31     prev.swap(curr);
 32     std::vector<int32_t>::value_type idx = 1;
 33     for(InputIterator it2 = first2; it2 != last2; ++it2)
 34     {
 35       if(*it1 == *it2) // operator == may be overloaded when necessary
 36         curr[idx] = prev[idx - 1+ 1;
 37       else
 38         curr[idx] = std::max(curr[idx - 1], prev[idx]);
 39       ++idx;
 40     }
 41   }
 42   result.swap(curr);
 43 }
 44 
 45 /*
 46   Recursive LCS calculation.
 47   See Hirschberg for the theory!
 48   This is a divide and conquer algorithm.
 49   In the recursive case, we split the 1st range in two.
 50   Then, by calculating std::vector<int32_t> of LCSes from the start and end
 51   corners of the [first1, last1] x [first2, last2] grid, we determine where
 52   the 2nd range should be split.
 53 
 54   pos is the origin(element 0) of the 1st sequence
 55   first1, last1 is the range of 1st being processed
 56   first2, last2 is the range of 2nd being processed
 57   Parameter vb holds the std::vector<bool> of the 1st sequence in the LCS.
 58 */
 59 template <typename BiIterator>
 60 void calculate_lcs(BiIterator pos, BiIterator first1, BiIterator last1,
 61                           BiIterator first2, BiIterator last2,
 62                           std::vector<bool>& vb)
 63 {
 64   const int32_t m = std::distance(first1, last1);
 65   const int32_t n = std::distance(first2, last2);
 66   if(n < 1 || m < 1)
 67     return// Empty 2nd range. all done
 68   else if(1 == m)
 69   {
 70     // Single item in 1st range.
 71     // If it's in the 2nd range, mark its position in the LCS
 72     int32_t idx = std::distance(pos, first1);
 73     vb[idx] = std::find(first2, last2, *first1) != last2;
 74   }
 75   else
 76   {
 77     // Split the 1st range
 78     BiIterator mid1 = first1;
 79     std::advance(mid1, m >> 1);
 80 
 81     // Find LCS std::vector<int32_t> at mid1, working from both ends of the range
 82     std::vector<int32_t> vec1, vec2;
 83     std::reverse_iterator<BiIterator> high1(last1), midx(mid1),
 84                                                      high2(last2), low2(first2);
 85 
 86     lcs_vect(first1, mid1, first2, last2, vec1);
 87     lcs_vect(high1, midx, high2, low2, vec2);
 88 
 89     // Find the optimal place to split the 2nd range
 90     std::vector<int32_t>::const_reverse_iterator rit = vec2.rbegin();
 91     std::vector<int32_t>::value_type lmax = 0;
 92     BiIterator it2 = first2, mid2 = it2;
 93 
 94     for(std::vector<int32_t>::const_iterator it1 = vec1.begin();
 95         it1 != vec1.end(); ++it1)
 96       {
 97         if(lmax < *it1 + *rit)
 98         {
 99           lmax = *it1 + *rit;
100           mid2 = it2;
101         }
102         if(it2 != last2)
103           ++it2;
104       ++rit;
105     }
106     // Split the range and recurse
107     calculate_lcs(pos, first1, mid1, first2, mid2, vb);
108     calculate_lcs(pos, mid1, last1, mid2, last2, vb);
109   }
110 }

 1 // longest common subsequence between the two files (suppose have already been stored in vectors)
 2 template <typename T>
 3 class longest_common_subsequence
 4 {
 5 public:
 6   typedef typename std::vector<T>::size_type size_type;
 7 
 8 public:
 9   longest_common_subsequence(const std::vector<T>& v1, const std::vector<T>& v2) : m_lcs()
10   {
11     std::vector<bool> vb(v1.size(), false);
12     calculate_lcs(v1.begin(), v1.begin(), v1.end(), v2.begin(), v2.end(), vb);
13     set_lcs(v1.begin(), vb, m_lcs);
14   }
15 
16   virtual ~longest_common_subsequence()
17   {
18     if(!m_lcs.empty())
19     {
20       std::vector<T> tmp;
21       m_lcs.swap(tmp);
22     }
23   }
24 
25   std::vector<T>& lcs() { return m_lcs; } // longest common subsequence list
26 
27   const std::vector<T>& lcs() const { return m_lcs; }
28 
29   bool empty() const { return m_lcs.empty(); }
30 
31   size_type size() const { return m_lcs.size(); }
32 
33   void swap(longest_common_subsequence& sq) { m_lcs.swap(sq.m_lcs); }
34 
35 private:
36 
37   std::vector<T> m_lcs;
38 };
39 
40 // longest common subsequence between the two string literals
41 template <>
42 class longest_common_subsequence<char>
43 {
44 public:
45   typedef typename std::string::size_type size_type;
46 
47 public:
48   longest_common_subsequence(const std::string& str1, const std::string& str2) : m_lcs()
49   {
50     std::vector<bool> vb(str1.size(), false);
51     calculate_lcs(str1.begin(), str1.begin(), str1.end(), str2.begin(), str2.end(), vb);
52     set_lcs(str1.begin(), vb, m_lcs);
53   }
54 
55   virtual ~longest_common_subsequence()
56   {
57     if(!m_lcs.empty())
58     {
59       std::string tmp;
60       m_lcs.swap(tmp);
61     }
62   }
63 
64   std::string& lcs() { return m_lcs; } // longest common subsequence list
65 
66   const std::string& lcs() const { return m_lcs; }
67 
68   bool empty() const { return m_lcs.empty(); }
69 
70   size_type size() const { return m_lcs.size(); }
71 
72   void swap(longest_common_subsequence& sq) { m_lcs.swap(sq.m_lcs); }
73 
74 private:
75 
76   std::string m_lcs;
77 };

求出了最长公共子序列然后跟原始的序列比较一下就知道变更了哪些行,用简单的加减法就搞定了。
  1 /* See below for some notion
  2 old: a b c d f g h j q z
  3 new: a b c d e f g i j k r x y z
  4 lcs: a b c d f g j z
  5 add + omitted: e h i q k r x y
  6 old - csq    :   -   -
  7 new - csq    : +   +   + + + +
  8 omitted      :   h   q
  9 added        : e   i   k r x y
 10 */
 11 
 12 class added_omitted_lines
 13 {
 14 public:
 15 
 16   added_omitted_lines(const std::list<std::string>& old_source,
 17                                  const std::list<std::string>& new_source) :
 18                                  m_omitted(), m_added()
 19   {
 20     initialize(old_source, new_source);
 21   }
 22 
 23   virtual ~added_omitted_lines()
 24   {
 25     purge_omitted();
 26     purge_added();
 27   }
 28 
 29   // omitted code line numbers
 30   const std::vector<int32_t>& omitted_line_nos() const { return m_omitted; }
 31   // added code line numbers
 32   const std::vector<int32_t>& added_line_nos() const { return m_added; }
 33 
 34   std::vector<int32_t>& omitted_line_nos() { return m_omitted; }
 35 
 36   std::vector<int32_t>& added_line_nos() { return m_added; }
 37 
 38 private:
 39 
 40   void purge_omitted()
 41   {
 42     if(!m_omitted.empty())
 43     {
 44       std::vector<int32_t> tmp;
 45       m_omitted.swap(tmp);
 46     }
 47   }
 48 
 49   void purge_added()
 50   {
 51     if(!m_added.empty())
 52     {
 53       std::vector<int32_t> tmp;
 54       m_added.swap(tmp);
 55     }
 56   }
 57 
 58   // Calculate an LCS of(v1, v2), the result will be in result.
 59   void extract_lcs(const std::vector<std::string>& v1,
 60                           const std::vector<std::string>& v2,
 61                           std::vector<std::string>& result) const
 62   {
 63     longest_common_subsequence<std::string> cs(v1, v2);
 64     std::vector<std::string>& vs = cs.lcs();
 65     result.swap(vs);
 66   }
 67 
 68   void changed_line_nos(const std::vector<std::string>& source,
 69                                     const std::vector<std::string>& lcsq,
 70                                     std::vector<int32_t>& line_no) const
 71   {
 72     std::vector<std::string>::const_iterator it1(source.begin());
 73     std::vector<std::string>::const_iterator it2(lcsq.begin());
 74     std::vector<std::string>::size_type cnt = 0;
 75     while(it1 != source.end() && it2 != lcsq.end())
 76     {
 77       if(*it1 == *it2)
 78       {
 79         ++it1;
 80         ++it2;
 81         ++cnt;
 82       }
 83       else if("\n" == *it1)
 84       {
 85         ++it1;
 86         ++cnt;
 87       }
 88       else if("\n" == *it2)
 89         ++it2;
 90       else
 91       {
 92         ++it1;
 93         ++cnt;
 94         line_no.push_back(cnt);
 95       }
 96     }
 97     while(it1 != source.end())
 98     {
 99       if("\n" != *it1)
100         line_no.push_back(cnt + 1U);
101       ++it1;
102       ++cnt;
103     }
104   }
105 
106   /* skip all spaces and tabs for all code lines */
107   std::vector<std::string> skip_space(const std::list<std::string>& v) const
108   {
109     std::vector<std::string> tmp;
110     tmp.reserve(v.size());
111     for(std::list<std::string>::const_iterator it(v.begin()); it != v.end(); ++it)
112       tmp.push_back(skip_space(*it)); /* spaces and tabs will be ignored, no implementation hereby! */
113
     return tmp;
114   }
115 
116 private:
117 
118   void initialize(const std::list<std::string>& old_source,
119                       const std::list<std::string>& new_source)
120   {
121     std::vector<std::string> old_file(skip_space(old_source));
122     std::vector<std::string> new_file(skip_space(new_source));
123     std::vector<std::string> lcs;
124     extract_lcs(old_file, new_file, lcs);
125     changed_line_nos(old_file, lcs, m_omitted);
126     changed_line_nos(new_file, lcs, m_added);
127   }
128 
129   std::vector<int32_t> m_omitted; // omitted code corresponding line numbers
130   std::vector<int32_t> m_added;   // added code corresponding line numbers
131 };

这样就得到了对比两个文件所添加的行号和删除的行号。

posted on 2013-05-25 18:57 Chipset 阅读(1841) 评论(0)  编辑 收藏 引用 所属分类: 算法和数据结构


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理