比较庞大的ASCII文件

本文关键字：ASCII 文件 比较 | 更新日期: 2023-09-27 18:24:00

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

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

我使用FC生成比较文件，然后在我们这边的perl中对其进行解析，以提取已删除/更新的记录和已添加的记录。

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

我试过使用diffutils，但它抱怨文件太大。

我还使用了一些c#代码来自己实现补丁过程。这对小文件很有效，但在处理大文件时效率非常低（在2.8 GB的提取版上进行了测试）

有什么好的命令行实用程序或c#库可以用来创建这个补丁文件吗？除此之外，有没有一种算法可以让我自己实现呢？请记住，记录可能会被更新、添加和删除（我知道，客户端删除记录，而不是将其标记为非活动记录，这也让我很恼火。这超出了我的控制范围。）

编辑以保持清晰：

我需要比较来自两个不同时间的两个独立的数据库摘录。通常情况下，这两个会间隔一天左右。

给定以下文件：（这些文件显然会更长、更宽）

旧.txt

a
b
c
d
e
1
f
2
5

新建.txt

a
3
b
c
4
d
e
1
f
g

预期输出为：

3 added
4 added
2 removed
g added
5 removed

比较庞大的ASCII文件

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

限制：

  1. 该算法不会将补丁线保持在原始文件中的相同顺序；如果这很关键，您可以使用Dictionary<字符串，int>其中键是行并且值是原始行号，而不是使用HashSet<字符串>以跟踪添加和删除的行
  2. 目标（"新"）文件必须与源（"旧"）文件有些相似。具体而言，源和目标中所有未更改的行必须按相同的顺序排列。如果不满足这个条件，算法将表现不佳
  3. 每条线相对于其附近的线必须是唯一的，其中"近"表示在源和目标之间不变的最近的线之间。如果不满足此条件，则算法将错过更改
  4. 此实现不考虑修改的行。我认为您可以添加该功能，方法是将==比较替换为用于检测两行是否为"同一"行的任何操作，然后在内容发生更改的情况下将它们写入补丁

该算法使用一对"添加的"answers"删除的"缓冲区来跟踪在文件中可能添加和删除的行。当文件之间的行不匹配时，它们会被临时标记为"已添加"或"已删除"。当在其中一个文件中找到临时标记的行时（如果在目标文件中找到"已删除"的行，或在源文件中找到了"已添加"的行），这是一个信号，表明其他缓冲区中的所有行都属于该行，因此将另一个缓冲区刷新到修补文件中，则读取器将在找到匹配行的文件中前进一行。

例如：

添加的源目标已删除A---------A__B---------X+X+BC---------B齐平X-BD-''''''-C__E-''''''--E+E+DF''--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);           
        }
    }
}

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

好吧，你正在比较两个文本文件，每个文件都有不一定按任何顺序排列的条目，我希望一个条目具有特定的格式，如果我理解正确，你真正拥有的应该是：*表示条目的开始@表示条目结束所以OLD.TXT*a@*b@*c@等等。。。粗略的"算法"是：1） 复制NEW，称之为ADDED2） 从OLD获取条目3.0）扫描该条目的ADDED。如果存在，请将条目保存在名为STILLEXISTS的文件中，然后从ADDED文件中删除该条目3.1）如果条目不在ADDED中，则保存在名为DELETED的文件中，并从OLD中获取下一个条目4） 当这一切结束时，你将有3个文件，每个文件都有添加、删除的条目和一个额外的"仍然存在"文件，所有这些都在一个过程中；）希望我理解得对，这能对你有所帮助。

相关文章：