c# 在所有文件中最快的字符串搜索

Question

问题(检查编辑说明)

我有大约 1500 个字符串的列表，对于这些字符串中的每一个，我必须检查目录(和子目录)中的任何文件是否包含该字符串(大约有 4000 个文件)。

代码

我现在有这两个变体:

原创

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

第二种变体(使用 ReadLines 而不是 ReadAllText，正如 VladL 在 this question 中所建议的那样)

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

编辑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
}

Answer 1

我认为最快的方法是:

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

Aho-Corasick 的实现可用 here .

我已经使用 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() took 00:00:09.8216836

anyViaAhoCorasick() took 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));

将每个文件完全加载到内存中与枚举每个文件中的字符(如上所述)进行比较以查看是否有任何区别是值得的。对于非常大的文件，避免将其全部内容加载到内存中可能很重要。