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 ms

第二个变体:2718,2804,2831 ms

我还尝试在原始语句中用ReadAllLines替换ReadAllText(不更改任何其他内容),但没有性能更改.

题

有没有更快的方法来检查字符串是否包含在任何文件(大量的大文件)中？

编辑

我承认我没有像我想的那样表达自己,说我有一个字符串列表.我实际拥有的是一个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 算法在每个文件的文本中搜索关键字。

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(). 但是，这是一个有点人为的测试用例，您的实际结果可能会有所不同。您应该使用实际数据进行检测，看看它是否真的有帮助。

请注意，在使用 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));

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