在大文本文件中快速搜索

Question

我正在尝试用 C# 编写一个搜索程序，它将在一个大文本文件 (5GB) 中搜索一个字符串。我已经完成了如下所示的简单代码，但搜索结果非常耗时，可能需要大约 30 分钟才能完成。这就是我的代码的样子-

public List<string> Search(string searchKey)
{
    List<string> results = new List<string>();
    StreamReader fileReader = new StreamReader("D:\Logs.txt");
    while ((line = fileReader.ReadLine()) != null)
    {
        if (line.Contains(searchKey)
        {
            results.Add(line);
        }
    }
}

虽然代码有效，但运行速度非常慢，大约需要 30 分钟才能完成。我们可以做些什么来将搜索时间缩短到一分钟以内吗？

Answer 1

对于非常大的文件中的字符串搜索，您可以使用 Boyer Moore 搜索算法，它是实用字符串搜索文献的标准基准。对于其实施，链接如下：

• Boyer-Moore 实用 C#？
• Boyer Moore 模式算法 搜索

Answer 2

文件索引在库 Bsa.Search.Core 中实现

您可以实现自己的文件读取版本。 FileByLinesRowReader - 按行读取文件并添加 externalId 等于行号的文档。 FileDocumentIndex 已经在 wiki 数据 json 字典上测试过

• .Net 核心

• .Net 472

       var selector = new IndexWordSelector();
       var morphology = new DefaultMorphology(new WordDictionary(), selector);
       var fileName = "D:\Logs.txt";
  
       // you can implement your own file reader, csv, json, or other
       var index = new FileDocumentIndex(fileName, new FileByLinesRowReader(null), morphology);
  
       // if index is already exist we skip file indexing
           if (!index.IsIndexed)
       index.Start();
       while (!index.IsReady)
       {
           Thread.Sleep(300);
       }
  
       var query = "("one" | two) ~50 ("error*")".Parse("*");
       var found = index.Search(new SearchQueryRequest()
       {
           Field = "*",
           Query = query,
           ShowHighlight = true,
       });
       // where ExternalId is line number from file  
       //found.ShardResult.First().FoundDocs.FirstOrDefault().Value.ExternalId
  

Answer 3

Gigantor 提供了一个

RegexSearcher

可以做到这一点。我用一个 32 GB 的文件测试了你的例子。在我的 MacBook Pro 上找到 8160 个匹配项用了不到 20 秒。代码如下所示。

Gigantor 提高了正则表达式的性能并处理巨大的文件。这是使用 Gigantor 的

Search

函数的代码。

public List<string> Search(string path, string searchKey)
{
    // Create regex to search for the searchKey
    System.Text.RegularExpressions.Regex regex = new(searchKey);
    List<string> results = new List<string>();

    // Create Gigantor stuff
    System.Threading.AutoResetEvent progress = new(false);
    Imagibee.Gigantor.RegexSearcher searcher = new(
        path, regex, progress, maxMatchCount: 10000);

    // Start the search and wait for completion
    Imagibee.Gigantor.Background.StartAndWait(
        searcher,
        progress,
        (_) => { },
        1000);

    // Check for errors
    if (searcher.Error.Length != 0) {
        throw new Exception(searcher.Error);
    }

    // Open the searched file for reading
    using System.IO.FileStream fileStream = new(path, FileMode.Open);
    Imagibee.Gigantor.StreamReader reader = new(fileStream);

    // Capture the line of each match
    foreach (var match in searcher.GetMatchData()) {
        fileStream.Seek(match.StartFpos, SeekOrigin.Begin);
        results.Add(reader.ReadLine());
    }
    return results;
}

这是测试代码。

[Test]
public void SearchTest()
{
    var path = Path.Combine(Path.GetTempPath(), "enwik9x32");
    Stopwatch stopwatch = new();
    stopwatch.Start();
    var results = Search(path, "unicorn");
    stopwatch.Stop();
    Console.WriteLine($"found {results.Count} results in {stopwatch.Elapsed.TotalSeconds} seconds");
}

这是控制台输出

found 8160 results in 19.1458573 seconds

这里是 Gigantor source repo。我知道有点晚了，但希望这个答案对某人有帮助。