在所有文件中进行最快的字符串搜索的C#方法

Question

问题（请查看编辑以了解更多信息）

我有一个大约包含1500个字符串的列表，对于这些字符串中的每一个，我都需要检查目录（包括子目录）中是否有任何文件包含该字符串（总共约有4000个文件）。

代码

我现在有以下两个变量：

原始代码

foreach(var str in stringList)
{
    allFiles.Any(f => File.ReadAllText(f).Contains(str));
}

第二种方法（使用ReadLines而不是ReadAllText，正如VladL在这个问题中建议的那样）

foreach(var string in stringList)
{
    allFiles.SelectMany(File.ReadLines).Any(line => line.Contains(str));
}

我只测试了原始版本的完整程序执行时间，用了21分钟才完成。然后我测试了单个语句（检查是否包含1个字符串在任何文件中），搜索一个我知道它不包含的字符串来检查最坏情况，这是我的计时结果（每次执行3次）:

原版: 1285, 1369, 1336 毫秒

第二种变体: 2718, 2804, 2831 毫秒

我还尝试将原始语句中的ReadAllText替换为ReadAllLines（仅更改此处），但没有改变性能。

问题

有没有更快的方式来检查一个字符串是否包含在任何文件中（大量的大文件）？

编辑

我承认我没有表达清楚，我有一个csv文件列表，然后遍历这些文件并遍历每个文件的每一行（忽略第一行）。对于每一行，我将其与某些字段组合成一个字符串，然后查找是否有任何文件包含该字符串。

foreach(var csvFile in csvFiles)
{
    var lines = File.ReadAllLines(csvFile);
    foreach(var line in lines)
    {
        if (IsHeader(line)) continue;
        var str = ComposeString(line);
        var bool = allFiles.Any(f => File.ReadAllText(f).Contains(str));
        // do stuff with the line and bool
     }
 }

Edit 2

public void ExecuteAhoCorasick()
{
    var table = CreateDataTable();
    var allFiles = GetAllFiles();
    var csvFiles = GetCsvFiles();
    var resList = new List<string>();

    foreach(var csvFile in csvFiles)
    {
        if (file.Contains("ValueList_")) continue;
        var lines = File.ReadAllLines(file);
        foreach (var line in lines)
        {
            if (line == HeaderLine) continue;
            var res = line.Split(';');
            if (res.Length <= 7) continue;
            var resPath = $"{res[0]}.{res[1]}.{res[2]}".Trim('.');
            resList.Add(resPath);

            var row = table.NewRow();
            row[0] = res[0]; // Group
            row[1] = res[1]; // Type
            row[2] = res[2]; // Key
            row[3] = res[3]; // Global
            row[4] = res[4]; // De
            row[5] = res[5]; // Fr
            row[6] = res[6]; // It
            row[7] = res[7]; // En
            row[8] = resPath; // Resource Path
            row[9] = false;
            row[10] = ""; // Comment
            row[11] = file; // File Path

            table.Rows.Add(row);
        }
    }

    var foundRes = new List<string>();

    foreach (var file in allFiles)
    {
        // var chars = File.ReadLines(file).SelectMany(line => line);
        var text = File.ReadAllText(file);

        var trie = new Trie();
        trie.Add(resList);

        foundRes.AddRange(trie.Find(text));
        // foundRes.AddRange(trie.Find(chars));
    }

    // update row[9] to true foreach res in foundRes
}

- Century

---

我首先会改变循环的顺序：对于每一个 文件，检查是否包含任何 字符串。当前每个文件被读取了1500次，即使文件系统可能会缓存一些数据，这显然比只读取每个文件一次并检查所有字符串要慢。 - René Vogt

请提供更多上下文以便我能够准确翻译。 - Century

如果您要将大块的文本与大量字符串进行比较，建议使用Aho-Corasick算法。您可以在此处找到该算法的实现：https://github.com/pdonald/aho-corasick。（注意：应根据其他答案的建议，仅对每个文件检查一次。）如果您决定尝试此方法，请记得在发布版本中进行基准测试，而不是调试构建，否则您将无法公平地比较结果。 - Matthew Watson

（针对您对我的答案的评论）好的，为了解决问题，您只需要在trie.Add()之后添加trie.Build()。另外请注意，您可以将trie的初始化移动到循环之前，这样您只需要在循环中使用trie.Find()本身即可。这也应该会减少开销。（换句话说，将var trie = new Trie(); trie.Add(resList); trie.Build();移到循环之前。） - Matthew Watson

Answer 1

我认为最快的方法是：

1. 将每个文件完全读入内存。这简化了代码。
2. 使用Aho-Corasick算法在每个文件的文本中搜索关键字。

Aho-Corasick的实现可以在这里找到。

我编写了一个简单的程序，使用来自Github的该实现测试了最坏情况下（即文本中没有关键字）的性能，并将Aho-Corasick与Contains()进行了比较。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using ConsoleApp1;

namespace Demo
{
    class Program
    {
        static void Main()
        {
            string[] needles = createNeedles(1500).ToArray();
            string haystack = createHaystack(100000);

            var sw = Stopwatch.StartNew();
            anyViaContains(needles, haystack);
            Console.WriteLine("anyViaContains() took " + sw.Elapsed);

            sw.Restart();
            anyViaAhoCorasick(needles, haystack);
            Console.WriteLine("anyViaAhoCorasick() took " + sw.Elapsed);
        }

        static bool anyViaContains(string[] needles, string haystack)
        {
            return needles.Any(haystack.Contains);
        }

        static bool anyViaAhoCorasick(string[] needles, string haystack)
        {
            var trie = new Trie();
            trie.Add(needles);
            trie.Build();
            return trie.Find(haystack).Any();
        }

        static IEnumerable<string> createNeedles(int n)
        {
            for (int i = 0; i < n; ++i)
                yield return n + "." + n + "." + n;
        }

        static string createHaystack(int n)
        {
            var sb = new StringBuilder();

            for (int i = 0; i < n; ++i)
                sb.AppendLine("Sample Text Sample Text Sample Text Sample Text Sample Text Sample Text Sample Text Sample Text");

            return sb.ToString();
        }
    }
}

一个64位RELEASE版本（在调试器外运行）的测试结果如下：

anyViaContains() 耗时 00:00:09.8216836

anyViaAhoCorasick() 耗时 00:00:00.4002765

对于这个测试案例，使用Aho-Corasick算法似乎比使用 Contains() 快了大约25倍。 然而，这只是一个有点虚假的测试案例，你要根据实际情况进行测试，看它是否真的有帮助。

请注意，当使用Aho-Corasick实现时，您实际上可以避免将整个文件加载到内存中，因为其Find()方法接受一个IEnumerable<char>。

您可以按照以下方式将文件内容转换为IEnumerable<char>:

var chars = File.ReadLines(filename).SelectMany(line => line);

这实际上会删除所有换行符，对于您的应用程序来说可能是可以接受的。如果您想保留换行符，您需要这样放回它们：

IEnumerable<char> newline = Enumerable.Repeat('\n', 1);
var chars = File.ReadLines(filename).SelectMany(line => Enumerable.Concat(line, newline));

值得比较一下将每个文件完全加载到内存中和枚举每个文件中的字符（如上所述）是否有任何区别。对于非常大的文件，避免将它们的全部内容加载到内存中可能很重要。

- Matthew Watson

---

我尝试了这个解决方案，但在执行Find()时，无论是使用IEnumerable<char>还是加载到内存中，都会出现NullReferenceException。 - Century

@Century，对不起，是我自己的问题——在发布代码时不知怎么地删掉了一行。所有 trie.Add() 调用后都需要添加 trie.Build(); 这一行。请参考我更新过的帖子。 - Matthew Watson

好的。现在它正常运行了，我会告诉你加载到内存和不加载之间是否有任何差异，一旦我有结果。 - Century

除去开销（将 trie.add() 和 trie.build() 移到循环外），在内存中大约需要12.3秒，在使用 IEnumerable<char> 大约需要15.1秒。 - Century

@Century（以防万一）确保您计时的是已发布的构建；调试构建将显着变慢。 - Matthew Watson

我使用了一个发布版本，并对三次运行取平均值。现在整个程序完成所需的时间约为16秒，而不是几分钟。谢谢！ - Century

Answer 2

文件中是否包含任何字符串？

private static bool ContainsLine(string file, List<string> wordsToFind) {
  return File
    .ReadLines(file)
    .Any(line => wordsToFind.Any(word => line.Contains(word))); 
}

我们是否有包含任何字符串的文件？

bool result = allFiles
  .AsParallel() // worth trying: we have a lot of files to be proceed
  .Any(file => ContainsLine(file, stringList));

编辑：对于像这样需要测试多个文件的问题，通常值得尝试使用.AsParallel()，但是如果AsParallel()没有带来任何收益，只需将其注释掉即可：

bool result = allFiles
  //.AsParallel() // comment out in case of no gain
  .Any(file => ContainsLine(file, stringList));

- Dmitry Bychenko

---

@Century 很有趣，看看这个答案的基准测试结果会是怎样的。 - fubo

我不确定 AsParallel() 在这里是否有任何积极的影响……至少当文件都在同一硬盘上时。而且文件大小也不可预测。 - René Vogt

@RenéVogt AsParallel() 可以帮助解决 SSD 存在低访问时间和高带宽的情况。 - fubo

你需要添加代码来确保不在旋转硬盘上运行AsParallel()版本，否则可能会使其变得更慢。 - Matthew Watson

我编辑了我的问题以进行一些澄清，我没有选择我的措辞。我想我可以在搜索之前检索所有字符串（一次性努力），然后反转搜索（在文件中搜索所有字符串），看看是否有改进。 - Century

好的。我测试了反转搜索，这是我的发现：首先创建字符串列表的开销约为100毫秒，执行您的ContainsLine函数需要9毫秒。如果我将9毫秒乘以我拥有的文件数量，那么大约需要36000毫秒。 - Century

Answer 3

您正在阅读每个字符串的所有文件。

那么反过来怎么样？遍历所有文件一次：

bool exists = 
    allFiles.SelectMany(File.ReadLines).Any(l=> stringList.Any(str=> l.Contains(str));

在编辑后：

正如您在评论中提到的，您应该先累加CSV文件中的所有字符串，然后按建议继续操作：

var stringList =
  csvFiles.SelectMany(f=>File.ReadAllLines(f).Where(l=>!IsHeader(l)).Select(ComposString))
          .ToList();

如果这个单词列表中有一些单词不是唯一的，你可能还想使用.Distinct，以使其更快。但这取决于这个列表的大小，以及有多少单词确实重复出现。

var stringList =
  csvFiles.SelectMany(f=>File.ReadAllLines(f).Where(l=>!IsHeader(l)).Select(ComposString))
          .Distinct()
          .ToList();

- Ofir Winegarten

---

我表达不清楚，抱歉。请检查编辑后的内容。不过，我可以做的是在搜索之前检索所有字符串（一次性努力），然后反转搜索（在文件中搜索所有字符串），看看是否有所改进。 - Century

Answer 4

这在很大程度上取决于您的确切用例。如果您正在尝试匹配可以轻松区分的整个单词，可以构建某种哈希索引（例如Dictionary<string, WhatEver>），以便您可以轻松搜索。无论如何 - 根据大小而定 - 这可能会非常消耗内存。

以下代码将给出如何构建此结构的想法。

class FileReference
{
    // elided 

    string File { get; } // may be set in constructor
    IEnumerable<int> Indices { get; } // will get the contents of _index

    public void Add(int index)
    {
        _indices.Add(index);
    }
}

class ReferenceIndex
{
    Dictionary<string, FileReference> _fileReferences = new Dictionary<string, FileReference>();

    public void Add(string fileName, string index)
    {
        if(!_fileReferences.ContainsKey(fileName))
        {
            _fileReferences.Add(fileName, new FileReference(fileName));
        }
        _fileReferences[fileName].Add(index);
    }

    // elided
}

FileReference 跟踪单个文件中字符串的索引，ReferenceIndex 包含单个字符串的 FileReference。对于哈希的 Dictionary<TKey, TValue>，访问它非常快速。您可以使用这些类来构建一个 Dictionary<string, ReferenceIndex>，以跟踪文件中所有字符串和对这些字符串的文件引用。

Dictionary<string, ReferenceIndex> stringIndex = BuildIndex(fileName);
foreach(var s in searchStrings)
{
    if(stringIndex.ContainsKey(s))
    {
        // do something
    }
}

- Paul Kertscher

Answer 5

我最近遇到了类似于你的问题。将每个可搜索文件表示为以下内容：

public class SearchableFile {
    private readonly HashSet<string> _uniqueLines;
    //private readonly HashSet<string> _uniqueString;

    public string FilePath { get; }

    public SearchableFile(string filePath) {
        _uniqueLines = new HashSet<string>(File.ReadAllLines(filePath));
        //↑You can also split each line if you have many repeating words in each line.
        //_uniqueString = File.ReadAllLines(filePath).SelectMany(singleLine => singleLine.Split(' '));
        FilePath = filePath;
    }

    public bool ContainsCompositeString(string compositeString) {
        return _uniqueLines.Any(singleLine => singleLine.Contains(compositeString));
        //return _uniqueString.Contains(compositeString);
    }
}

然后您可以直接使用它：

    private static void Main(string[] args) {
        var filePaths = new List<string> { "c://temp.txt" };

        foreach (var filePath in filePaths) {
            FilesOnHdd.Add(new SearchableFile(filePath));
        }
        var csvFiles = new List<string> { "c://temp.csv" };
        foreach (var csvFile in csvFiles) {
            var lines = File.ReadAllLines(csvFile);
            foreach (var line in lines) {
                if (IsHeader(line)) {
                    continue;
                }
                var str = ComposeString(line);

                foreach (var singleFileOnHdd in FilesOnHdd) {
                    var result = singleFileOnHdd.ContainsCompositeString(str);
                    if (result) {
                        // do stuff with the line and bool
                    }
                }
            }
        }
    }

- Hasan Emrah Süngü