在大文本文件中搜索字符串的最快方法

Question

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

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

珍惜你的时间

Answer 1

执行此操作的标准方法是实现Aho-Corasick 算法。它读取文件一次并查找您提供的所有字符串的所有匹配项。有关提供实现和一些示例的文章，请参阅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方法仅返回出现在整个单词中的匹配项。这可以更轻松地处理行首和行尾的匹配以及其他非单词字符。