65.9K
CodeProject 正在变化。 阅读更多。
Home

V Diff - 具有可视化输出的文件比较器

shankarp
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.96/5 (51投票s)

2003年2月22日

9分钟阅读

viewsIcon

301366

downloadIcon

9176

一个简单的程序，使用LCS算法比较两个文件。

HTML output produced by VDiff

引言

此程序比较两个文本文件，并以纯HTML格式输出各种颜色的差异分析。

背景

比较两个文件（或者更确切地说，同一个文件的两个版本）是程序员经常遇到的问题。还记得ClearCase和其他版本控制系统显示你对代码所做的修改的方式吗？如果你的应用程序能为用户提供这样的功能，那该多好啊。每个平台下都有著名的工具可以解决这个问题，“WinDiff”在Windows上，“diff”在UNIX平台上。

这些程序的源代码也是免费提供的，但它们是

  1. 不简单（因为它们经过了密集的优化周期）
  2. 文档不完善（因为没有充分的理由）
  3. 难以理解；它们从不解释底层算法。
  4. 它们不是为了集成到你的应用程序而设计的。

VDiff简单易懂，并且是用纯C++编写的，因此几乎可以在任何平台上编译（已在VC++ 6.0和g++ 2.95上测试过）。此程序的输出在IE和Netscape（滚动功能稍有妥协）下运行良好，并且易于集成到您自己的应用程序中。另一方面，它不像其他著名工具那样快，但我相信未来的版本在速度上会与之媲美。

VDiff使用最长公共子序列（LCS）作为区分两个文件的算法。LCS是一个在各个领域广泛使用的算法（例如在基因工程中比较DNA序列）。给定两个实体序列数组，该算法将找到两个数组中都存在的实体序列的最长公共序列。

在我们的问题中，实体是一行代码。这两个文件是实体数组。该算法在此情况下产生的LCSequence是一系列未更改的行：以此为参考，我们可以生成添加/删除/更改行的图片。

我强烈建议您在编写代码之前，参考以下有关LCS的资料。

Dan Hirsberg是LCS的主要贡献者之一。您可以在此处找到他的作品。

使用代码

CCmpMngr是提供整个功能访问的接口类。一个例子胜过千言万语，所以请看下面的代码片段。这是将其集成到您的代码中的简单方法。

int main(int argCount, char **argArray)
{
    if (argCount < 3)
    {
        cout<<"Usage 'cmp file1 file2 [output dir]' "<<"\n";
        return 0;
    }
    else
    {
        CCmpMngr cMgr;
        std::string file1,file2,oDir;
        
        cMgr.baseFile = std::string(argArray[1]);
        cMgr.compFile = std::string(argArray[2]);
        cMgr.compare();
        if (argCount > 3) // Visual diffrence is needed
        {
            oDir = std::string(argArray[3]);
           if (oDir[oDir.length()-1] != '\\') oDir.append(std::string("\\"));
            cMgr.print_diff_in_HTML(oDir);
        }
        cout<<"Added Lines = "<<cMgr.nAddedLines<<"\n";
        cout<<"Deleted Lines = "<<cMgr.nDeletedLines<<"\n";
        cout<<"Changed Lines = "<<cMgr.nChangedLines<<"\n";
    }
    return 1;
}

在上面的代码中，要比较的文件是从命令行参数获取的。请注意CCmpMngr类，它有两个成员baseFile和compfile：它们应该被赋予一个有效的包含完整路径的文件名。一旦完成，调用Compare()方法，它将执行实际的比较。比较后，差异统计信息可以通过成员nAddedLines、nDeletedLines和nChangedLines获得。现在最有趣的部分是，以各种颜色进行差异的可视化呈现。这是由print_diff_in_HTML(oDir)方法生成的。传递的变量是您希望生成三个HTML文件（稍后解释）的首选路径名。

比较是如何实现的

LCS算法相当简单易懂。假设我们有两个文本文件。首先将这两个文件逐行读取。由于比较文本行非常耗时，因此通过非常简单的哈希将其转换为整数值。这是通过hash(filemap& f, hashed_filemap& hf)完成的。现在我们剩下两个数组bHm和cHm（bHm = 基本哈希映射，cHm = 比较哈希映射）。对于bHm的每个成员，我们应该从cHm中找到一个“最佳”匹配。或者您可以声明没有匹配。现在想象一下比较两个'.CPP'文件。您在第3行，它是一个单字符行“{”。您会在第二个文件中至少找到一百个匹配项。从可能的匹配项中选择最佳匹配的标准是……嗯……嗯……嗯……好吧，这是一个你自己的决定。如果你在那个点做出一个决定，它能找到一个长公共序列，那么这是一个好的决定；然而，如果它能找到最长的公共序列，那么它就成为最好的决定，从而成为最佳匹配。

由于计算机很愚蠢，没有常识，选择最佳决定的唯一方法是做出所有决定，比较结果并决定最佳。为了找到bHm中某个成员的最佳匹配（决定），我们必须遍历cHm中的每个元素（决定）。

for (i = 0; i <= m; i++) // For each line in the first file....
{        
    for (j = 0; j <= n; j++) // ....Find the best match in second file
    {
    }
}

现在想象一下，你已经为所有元素完成了这件事，并且现在到了最后一个元素。决策的制定相当简单，因为cHm中除了最后几个之外的所有元素都已经被声明为bHm中某个元素的最佳匹配，而你还剩下了一两个未匹配的元素，而且很可能根本不用考虑最佳匹配，因为只有一个会匹配。即使你还剩下3行，并且所有3个都完美匹配，你也可以盲目地选择任何一个，因为这个决定不会影响bHm中剩余的元素（=零）的匹配。

请注意此处的最后一句。你在“x”点做出的决定会影响后续元素的匹配；另一方面，你需要剩余元素的匹配数据才能决定最佳匹配。为了避免这种相互依赖，我们可以从没有后续元素（因此不需要数据）的最后一个元素开始。

for (i = m; i >= 0; i--) // For each line in the first file....
{
    for (j = n; j >= 0; j--) // ....Find the best match in second file
    {
    }
}

在循环内部，我们准备一个矩阵，其中行和列分别代表第一个和第二个序列中的元素。该矩阵由每个匹配项的最长公共子序列的长度组成。请注意，对于每个匹配项，可用最佳LCS的长度会增加一，否则最佳LCS保持不变。

if (bHm[i].second == cHm[j].second) // match
{
    LCSMatrix(i,j) = 1 + LCSMatrix(i+1, j+1); // Increment
}
else 
{
    // retain the best among available LCS
    LCSMatrix(i,j) = max(LCSMatrix(i+1, j), LCSMatrix(i, j+1));
}

请注意，如果您正在比较大文件（例如，您正在比较每个包含30000行的文件，那么您需要3.3GB内存），则LCSMatrix矩阵会消耗大量内存。考虑到我们在给定点只需要LCSMatrix(i+1, j)和LCSMatrix(i, j)，我们可以使用两个一维数组来管理，一个用于（i）'th行，另一个用于（i+1）'th行，并将代码修改为如下所示。顺便说一句，如果你不理解这个算法，别担心，有一个更好的解释，带有漂亮的图示，来自http://www.ics.uci.edu/~eppstein/161/960229.html。

bool CCmpMngr::compare_hashed_files_LCS(hashed_filemap &bHm,
      hashed_filemap& cHm,match& dHm)
{    
    int i,j,k,m,n;    
    m = bHm.size(); n= cHm.size(); // length of two sequences to be compared
    LCSBitMatrix.resizeTo(m+2,n+2); // fix the size of bit matrix.
    std::vector ci,ci1;

    ci.resize(n+2,0);ci1.resize(n+2,0); // resize for ample space
    for (i=0;i<=n;i++) {ci[i]=0;ci1[i]=0;} // initialize arrays

    // Prepare LCS matrix
    for (i = m; i >= 0; i--) // For each line in the first file....
    {        
        // Make a copy for comparison, We r going to initialize
        for (k=0;k<=n;k++) {ci1[k]=ci[k];} 
        
        for (k=0;k<=n;k++) {ci[k]=0;} // initialize 
        for (j = n; j >= 0; j--) // ....Find the best match in second file
        {                
            if (bHm[i].second == cHm[j].second)
            {                    
                ci[j] = 1 + ci1[j+1];
            }
            else 
            {
                if (ci1[j] > ci[j+1]) // Equivalent to above line
                {
                    // to remember the condition result even beyond loop
                    LCSBitMatrix.put(i,j,true); 

                    // to continue looping according to condition result 
                    ci[j] = ci1[j]; 
                }
                else
                {
                    // to remember the condition result even beyond loop
                    LCSBitMatrix.put(i,j,false); 

                    // to continue looping according to condition result
                    ci[j] = ci[j+1]; 
                }
            }                                                
            /* Same above done with huuuuge 2D array named LCSMatrix.
            if (bHm[i].second == cHm[j].second)
            {
                LCSMatrix(i,j) = 1 + LCSMatrix(i+1, j+1);
            }
            else 
            {
                LCSMatrix(i,j) = max(LCSMatrix(i+1, j), LCSMatrix(i, j+1));
            }
            */
        }
    }
}

一旦矩阵用每个点的LCS长度填充完毕，我们就可以通过以下方式遍历它来生成最长公共子序列；从左上角元素开始，如果元素匹配，则在行和列中各前进一格，并将元素添加到LCS匹配列表中。如果元素不匹配，则根据哪个方向有最长的LCS路径，在列或行中前进一格。

    dHm.empty();
    i = 0;j = 0;
    // Following link walks through the bitmatrix we created by the loop above
    // and produces a LCS, A LCS here is a vector of pairs.  A pair has two line
    // numbers each from different file which is perfect match.
    // If the pair has <12,17>.., Then it means
    // The 12th line in the File1 has became 17th line in File2, User might have
    // simply added 5 lines in between or added 8 lines and deleted 3 lines.. Etc
    while (i < m && j < n)
    {
        if (bHm[i].second == cHm[j].second)
        {
            dHm.push_back(match_pair (i,j)); // A pair match added to LCS.
            i++; j++;
       }
       else 
        {
            // In case we were using that Huuuuge 2D array, The condition would
            // will be like below             
            // if (LCSMatrix(i+1,j) >= LCSMatrix(i,j+1)) 
            if (LCSBitMatrix.get(i,j) == true) 
                i++;
            else
                j++;
        }
    }

    print_diff_in_HTML(std::string(""));
    return true;
}

如何生成HTML输出

现在我们有了一个匹配对的数组。我们可以识别添加/删除/更改的行。又是一个例子胜过千言万语，所以让我们从一个样本对数组开始

  1. (1,1)
  2. (2,2)
  3. (3,3)
  4. (4,6)
  5. (5,7)
  6. (6,8)
  7. (9,10)
  8. (10,11)
  9. (11,12)
  10. (12,13)
  11. (15,16)

请注意，从第3对和第4对（第二文件中新添加的第4行和第5行）可以看出添加行的指示；从第6对和第7对（第一文件中删除的第7行和第8行）可以看出删除行的指示；从第10对和第11对（第一文件中的第13行和第14行，以及第二文件中的第14行和第15行）可以看出更改行的指示。

然后，此信息由print_diff_in_HTML()方法编码为HTML。HTML输出由3个不同的框架组成：一个框架显示正在比较的两个文件，一个主框架。包含在两个子框架中的以下脚本启用了两者之间的同步滚动；

function myScroll()
{
    if (document.layers) {//for netscape
        x  = window.pageXOffset;
        y  = window.pageYOffset;
    }
    else if (document.all) {//for IE
        x = document.body.scrollLeft;
        y = document.body.scrollTop;
    }
    parent.left.scrollTo(x,y); 
}

关注点

除了文件比较之外，此程序还使用了一种罕见的数据结构：位矩阵。编写一个充当位矩阵的新类的原因是，在各种内存打包方案下，bool数据类型在各种平台上实现方式的不确定性。

CBitMatrix类是基于Marshall Cline维护的官方C++ FAQ的示例代码构建的。我对代码感到困惑（当重载函数仅在返回类型和'const'性方面有所不同时会发生什么），并给他发了邮件。他对我的提问的回答以及他对回答“无名小卒”问题的专业精神让我感到惊讶。

我将重现这封邮件，因为它对您会有所帮助。它还回答了为什么CBitMatrix没有一个简单的接口来放置和获取成员的问题。

-----来自Marshall Cline的邮件-----
主题：RE: C++ FAQ Lite[13.8] 的建设性反馈（矩阵样本有bug...？）
日期：2002年10月7日，星期一，13:01:46 -0500
发件人：“Marshall Cline”

感谢来信。

不幸的是，代码 *完全* 按照其意图工作。非const版本 *应该* 在您说的两个地方被调用。特别是，如果您有一个类X中有两个方法，它们在const性上不同，例如：

  class Foo {
  public:
    void f();
    void f() const;
  };

然后，编译器被 *要求* 当且仅当Foo对象是非const时才调用非const版本。返回类型无关紧要，并且在“重载解析”过程中通常不予考虑。

Marshall

-----原始消息-----
发件人：shankar pratap
发送时间：2002年10月7日，星期一，上午9:45
主题：C++ FAQ Lite[13.8] 的建设性反馈（矩阵样本有bug...？）

尊敬的Marshall Cline先生

主题中提到的代码片段并未按照预期工作。

函数
------------
1） int& operator() (unsigned int row, unsigned int col);
2） int operator() (unsigned int row, unsigned int col) const;

意图
---------
Matrix m(10,10);
m(5,8) = 106.15; // 应该调用函数1），它返回int&
std::cout << m(5,8); // 应该调用函数2）

但在两种情况下都调用了函数1）。

我尝试过的编译器是：
1） g++
2） MSVC++ 6.0。

此致
Shankar Pratap

暂时就这些。编码愉快！

历史

  • 2003年2月11日
  • 2003年2月24日
    1. 引入了带进度条的简单GUI。
    2. HTML输出不再删除空白符。
© . All rights reserved.