Diff算法C++

Question

Diff算法C++

3

我正在尝试用C++编写一个程序，能够对比两个 .txt 文件。

struct line
{
    string text;
    size_t num;
    int status;
};

void compareFiles(vector<line> &buffer_1, vector<line> &buffer_2, size_t index_1, size_t index_2)
{
    while(index_1 < buffer_1.size())
    {
         while(index_2 < buffer_2.size())
         {  
             X = buffer_1[index_1].text;
             Y = buffer_2[index_2].text;
             if(X == Y)
             {
                 ++index_1;
                 ++index_2;
             }
             else
             {
                 LCS();
                 string lcs = printLCS(X.length(), Y.length());

                 /*
                 * Here's my problem
                 */

             }
         }
     }
 }

如您所见，我有两个缓冲区（行向量）以前加载了文件内容。我还拥有完全可用的LCS算法（已经测试）。LCS在全局定义的字符串X和Y上运行。

所以，我真正需要做的是逐行比较缓冲区与LCS，但我没有找到一种方法来实现它。

请问您能帮助我吗？

- João Santos

我建议您取消嵌套两个 while() 循环 -- 当 buffer_2 中的行用尽时会发生什么？index_1 将永远不会增加，最外层的 while 循环将永远不会终止。while (index_1 < buffer_1.size() || index_2 < buffer_2.size()) { ... } 可以让您完全运行两个输入。(也许一个输入只是在末尾附加了一个换行符而已...) - sarnold

2个回答

0

首先，我会重写 LCS() 函数，使其接受两行作为参数并返回最长公共序列。我想象函数签名如下：std::string LCS(const line& lhs, const line& rhs)。然后，我会修改你的 while 循环如下。

for(int i = 0; i < buffer_1.size(); ++i)
{
    for(int j = 0; j < buffer_2.size(); ++j)
    {  
        std::string lcs = LCS(buffer_1[i].text, buffer_2[j].text);
        std::cout << "LCS[" << i << "][" << j << "]: " << lcs << std::endl;
    }
}

这将会找到并打印出buffer_1和buffer_2中每一行组合的最长公共序列。这是您想要做的吗？我是否正确理解了您的问题？

- Chris Frederick

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Zach Rattner · Accepted Answer

当有疑问时，我通常会请教已经做过的人。古老可靠的diff程序存在已久，并可以满足你的需求。此外，它是开源的，所以请转到ftp://mirrors.kernel.org/gnu/diffutils/diffutils-3.0.tar.gz查看。

解压缩存档后，打开src/analyze.c文件。函数diff_2_files从第472行开始。实际比较的代码在512-537行之间运行。以下是这些代码：

for (;; cmp->file[0].buffered = cmp->file[1].buffered = 0)
{
    /* Read a buffer's worth from both files.  */
    for (f = 0; f < 2; f++)
        if (0 <= cmp->file[f].desc)
            file_block_read (&cmp->file[f],
                buffer_size - cmp->file[f].buffered);

    /* If the buffers differ, the files differ.  */
    if (cmp->file[0].buffered != cmp->file[1].buffered
            || memcmp (cmp->file[0].buffer,
                    cmp->file[1].buffer,
                    cmp->file[0].buffered))
    {
        changes = 1;
        break;
    }

    /* If we reach end of file, the files are the same.  */
    if (cmp->file[0].buffered != buffer_size)
    {
        changes = 0;
        break;
    }
}

这里的想法是加载两个相同大小的缓冲区，然后将每个文件加载到一个缓冲区中。使用 memcmp 每次比较一个缓冲区，看看是否有任何一个缓冲区与另一个不同。如果任何一个缓冲区比较不相等，则两个文件不同。还要注意的是，您永远不需要一次读取超过两个缓冲区的数据，因此这种方法也适用于大型文件。