比较HUGE ASCII文件

Question

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

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

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

只要文本行不超过128个字符,FC对我来说就完美无缺.当发生这种情况时,输出将被放到比较文件的下一行,因此显示为添加/删除的记录.我知道我可以预先处理文件,但这会增加大量的时间,可能会破坏目的.

我尝试过使用diffutils,但它抱怨大文件.

我还玩了一些c#代码来自己实现补丁过程.这适用于小文件,但在处理大文件时非常低效(在2.8 GB的提取上测试)

是否有任何好的命令行实用程序或c#库可用于创建此修补程序文件？除此之外,我是否可以使用一种算法来实现这一点？请记住,记录可能会被更新,添加和删除(我知道,它也让我感到客户端DELETE记录,而不是将它们标记为非活动状态.这是我无法控制的.)

为清晰起见编辑:

我需要比较两个不同时间的两个单独的数据库提取.通常这些将相隔约一天.

鉴于以下文件:(这些显然会更长,更宽)

---

Old.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<string,int> 的操作，其中键是行，值是原始行号，而不是使用 HashSet<string> 来跟踪添加和删除的行。
2. 目标（“新”）文件必须与源（“旧”）文件有些相似。具体来说，所有未更改的行在源和目标中的顺序必须相同。如果不满足此条件，算法将表现得很糟糕。
3. 每条线相对于其附近的线而言必须是唯一的，其中“附近”是指在源和目标之间不变的最近线之间。如果不满足此条件，算法将错过更改。
4. 此实现不考虑修改的行。我认为您可以通过将 == 比较替换为用于检测两行是“同一”行的任何操作来添加该功能，然后如果它们是内容更改的“同一”行，则将它们写入补丁。

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

例如：

 
源 目标 添加 删除
一个------一个_ _
B-----X+X+B
C--------B 齐平 X -B
D--\ \-C _ _
E-\ \---E +E +D
F \----F -E 齐平 D

这是代码：

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);           
        }
    }
}

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