c# - 比较巨大的 ASCII 文件

Question

我在一家公司工作，该公司在各种数据库上进行 ETL 工作。我的任务是为客户端计算机上的两个完整历史数据集创建一个补丁，然后将其发送到我们的服务器。此补丁需要编程，以便可以从我们的软件中调用。

数据集是简单的文本文件。我们在客户的系统上运行提取软件来执行提取。提取文件大小不等，最大可达 3GB+。我已经使用 Microsoft 的 FC.exe 实现了一个解决方案，但它有局限性。

我正在使用 FC 生成比较文件，然后在我们这边用 perl 解析它以提取已删除/更新的记录，以及已添加的记录。

只要文本行不超过 128 个字符，FC 就非常适合我。当发生这种情况时，输出将放在比较文件的下一行，因此显示为添加/删除的记录。我知道我可能会预处理文件，但这会增加大量时间，可能达不到目的。

我试过使用 diffutils，但它提示文件太大。

我还玩弄了一些 c# 代码来自己实现补丁过程。这适用于小文件，但在处理大文件时效率极低(在 2.8 GB 提取物上测试过)

是否有任何好的命令行实用程序或 C# 库可用于创建此补丁文件？除此之外，是否有我可以用来自己实现的算法？请记住，记录可能会被更新、添加和删除(我知道，客户删除记录而不是将它们标记为不活动也让我很恼火。这是我无法控制的。)

为清楚起见编辑:

我需要比较来自两个不同时间的两个单独的数据库摘录。通常这些间隔大约一天。

给定以下文件:(这些文件显然会更长更宽)

---

旧.txt

a
b
c
d
e
1
f
2
5

New.txt

a
3
b
c
4
d
e
1
f
g

预期的输出是:

3 added
4 added
2 removed
g added
5 removed

Answer 1

这是一个非常有效的解决方案 - 我认为它大致为 O(n)，但它取决于添加和删除的分布。内存消耗很低，但也取决于连续添加和删除的次数。

限制:

1. 此算法不会按照原始文件中的相同顺序保留补丁行；如果这很重要，您可以使用 Dictionary 之类的操作，其中键是行，值是原始行号，而不是使用 HashSet 来跟踪添加和删除的行。
2. 目标("new")文件必须与源(“旧”)文件有些相似。具体来说，所有未更改的行在源和目标中的顺序必须相同。如果不满足此条件，算法将表现不佳。
3. 每条线相对于它附近的线必须是唯一的，其中“附近”是指在源和目标之间没有变化的最近线之间。如果不满足此条件，算法将错过更改。
4. 此实现不考虑修改的行。我认为您可以通过将 == 比较替换为您用于检测两行是“相同”行的任何操作来添加该功能，然后如果它们是内容更改的“相同”行，则将它们写到补丁中。<

该算法使用一对“添加”和“删除”缓冲区来跟踪在文件中运行时可能添加和删除的行。当行在文件之间不匹配时，它们被暂时标记为“添加”或“删除”。当在其中一个文件中找到一个暂时标记的行时(如果在目标文件中找到“删除”行，或者在源文件中找到“添加”行)，这是一个信号，表明所有行在其他 缓冲区确实属于那里，因此其他缓冲区被刷新到补丁文件，然后读者在找到匹配行的文件中前进一行。

例如:

 Source  Target Added   RemovedA-------A      _       _B-------X      +X      +BC-------B      Flush X -BD--\  \-C      _       _E-\ \---E      +E      +DF  \----F      -E      Flush D

Here's the code:

public void Diff(
    string sourcePath,
    string targetPath,
    string patchPath,
    string addedSuffix,
    string removedSuffix)

{
    using(var sourceReader = new StreamReader(sourcePath))
    using(var targetReader = new StreamReader(targetPath))
    using(var patchWriter = new StreamWriter(patchPath, append:false))
    {   
        var sourceLine = sourceReader.ReadLine();
        var targetLine = targetReader.ReadLine();

        var added = new HashSet<string>();
        var removed = new HashSet<string>();

        do{
            if(sourceLine == targetLine)
            {   
                sourceLine = sourceReader.ReadLine();
                targetLine = targetReader.ReadLine();
            }
            else
            {
                if(removed.Contains(targetLine))
                {
                    // Found targetLine in tentatively removed lines, so it wasn't actually removed.
                    removed.Remove(targetLine);
                    // Since we found something we thought had been removed, we know that all tentatively added lines actually are new.
                    Flush(patchWriter, added, addedSuffix);             
                    added.Clear();

                    targetLine = targetReader.ReadLine();               
                } 
                else if(added.Contains(sourceLine))
                {
                    // Found sourceLine in tentatively added lines, so it wasn't actually added.
                    added.Remove(sourceLine);
                    // We found something we thought had been added, so all candidates for removal should actually be removed.
                    Flush(patchWriter,removed, removedSuffix);
                    removed.Clear();

                    sourceLine = sourceReader.ReadLine();               
                }
                else
                {
                    // Source and target don't match, so we assume that the source was removed and the target was added.
                    // If we're wrong, we'll clean it up when we come across the line later on.
                    removed.Add(sourceLine);
                    added.Add(targetLine);
                    sourceLine = sourceReader.ReadLine();               
                    targetLine = targetReader.ReadLine();               
                }       
            }   
        } while(sourceLine != null || targetLine != null); 

        Flush(patchWriter, added, addedSuffix);
        Flush(patchWriter, removed, removedSuffix);
    }
}

public void Flush(StreamWriter writer, IEnumerable<string> lines, string suffix)
{
    foreach (var line in lines.Where (l => l != null))
    {
        writer.WriteLine("{0} {1}", line.Trim(), suffix);
    }
}

这是我用来生成测试文件的一些代码:

var path = /* path */;
var sourcePath = Path.Combine(path, "source.txt");
var targetPath = Path.Combine(path, "target.txt");
var expectedPath = Path.Combine(path, "expected.txt");
var rnd = new Random(10);

using(var sourceWriter = new StreamWriter(sourcePath))
using(var targetWriter = new StreamWriter(targetPath))
using(var expectedWriter = new StreamWriter(expectedPath))
{
    var limit = 10.0 * 100000;
    for (int i = 0; i < limit; i++)
    {
        if(i % 10000 == 0) Console.Write("{0:P0} ...", i / limit);
        var guid = Guid.NewGuid().ToString();
        var r = rnd.Next(0,10);
        var removed = 3;
        var added = 6;
        if(r >= 0 && r < removed)
        {
            sourceWriter.WriteLine(guid);
            expectedWriter.WriteLine(guid + " 0");
        }
        else if(r >= removed && r < added)
        {
            targetWriter.WriteLine(guid);
            expectedWriter.WriteLine(guid + " 1");
        }
        else if(r >= added)
        {   
            sourceWriter.WriteLine(guid);
            targetWriter.WriteLine(guid);           
        }
    }
}

看到任何错误或问题了吗？这是您要找的吗？