c# - 在多个大文本文件中搜索多个字符串的最快方法

Question

为了在相当大的文本文件(最多 1GB 的文本文件)中查找字符串列表，可以实现最快的技术/算法是什么。对于初学者，我使用 C# 并能够实现逻辑(只需将文件与字符串列表匹配，每次逐个字符串。这意味着文件将被读取 n 次strings to match with"times), 但由于我正在处理大量文件，因此需要永远运行它们并获得匹配项。我愿意接受任何建议，即使它不是 C#。

更详细地说，我有一个包含许多数字的文本文件 (A)，而且我有很多大文件 (B)。我试图获取 (A) 中的每个元素，并逐行查看 (B) 中是否有匹配项。如果匹配，我将整行写入一个文本文件。我这样做的方式非常传统，完成单个文件需要花费大量时间，而我有数百个文件，大小高达 1GB。

Answer 1

执行此操作的标准方法是实现 Aho-Corasick algorithm .它读取文件一次并查找所有出现的所有字符串。参见 https://www.informit.com/guides/content.aspx?g=dotnet&seqNum=869获取提供实现和一些示例的文章。

更多信息后更新

假设文件 A 中的数字列表足够小以适合内存，这就是您要做的，使用上面链接的文章中的实现:

// Construct the automaton
AhoCorasickStringSearcher matcher = new AhoCorasickStringSearcher();
foreach (var searchWord in File.ReadLines(File_a)
{
    matcher.AddItem(searchWord);
}
matcher.CreateFailureFunction();

// And then do the search on each file
foreach (var fileName in listOfFiles)
{
    foreach (var line in File.ReadLines(filename))
    {
        var matches = matcher.Search(line);
        foreach (m in matches)
        {
            // output match
        }
    }
}

请注意，它只会遍历每个文件一次，并且永远不必在任何时候将超过一行的文件加载到内存中。这里的限制因素是构建自动机所需的内存。

我用它来搜索总计超过 100 GB 的文件，大约有 1500 万个不同的字符串。构建自动机需要几分钟时间，但随后搜索速度非常快。该算法的一个非常好的特性是它的复杂度为 O(n + m)，其中 n 是输入文件的大小，m 是匹配项的数量。它搜索的字符串数量无关紧要。它可以像搜索一两个字符串一样快速地搜索一百万个不同的字符串。

100 GB 将带您……阅读大约 40 分钟的内容。如果需要一个小时才能在 100 GB 的数据中找到所有出现的 1500 万个不同的字符串，我会感到非常惊讶。

匹配整个单词

如果您要搜索整个单词，另一种选择是放弃 Aho-Corasick 算法。相反，将您要查找的所有数字加载到 HashSet<string> 中。 .然后读取每一行并使用正则表达式查找该行中的所有数字并检查它们是否存在于哈希集中。例如:

Regex re = new Regex("\w+");
foreach (var line in File.ReadLines(filename))
{
    var matches = re.Matchs(line);
    foreach (var m in matches)
    {
        if (hashSetOfValues.Contains(m))
        {
            // output match
        }
    }
}

这可能会比 Aho-Corasick 算法慢一些，但它仍然只通过一次数据。当然，这假设您有足够的内存来将所有这些数字保存在一个哈希集中。

正如我在评论中提到的，整个单词还有其他选项。

如果您知道要查找的词总是由空格分隔，另一种选择是在添加到自动机的词的开头和结尾添加空格。或者，通过对实现本身进行一些修改，您可以强制匹配器的 Search方法只返回整个单词中出现的匹配项。这可以更轻松地处理行首和行尾的匹配项，以及其他非单词字符。