文件搜索功能的高效方法

本文关键字：高效 方法 功能 搜索 文件 | 更新日期: 2023-09-27 18:24:51

我有一个非常庞大的文本文档。我正在实现"搜索"功能，以查找文件中给定字符串的出现情况并显示其位置。这不仅仅是全词搜索，它还可以包含单词/句子/段落的一部分。我正在为这个过程制定有效的数据结构。如果是全词搜索，我可以使用trys/hash表。我将无法使用后缀数组/后缀树，因为文件大小非常大。排序也没有那么有效。另一个简单的选择是使用框架的字符串搜索/正则表达式功能，这需要线性时间。对于这种操作，有什么更为人所知的方法吗？最初它只是字符串搜索，后来计划用元字符进行搜索。

文件搜索功能的高效方法

Trie和后缀树/数组是一个不错的选择，但如果你不喜欢它们，我有另一个解决方案：创建一个哈希表：

  • 为长度为1、2、3、..的所有字符串创建哈希表。。N，其中N是您想要的复杂度O的任意数字（N*size_of_text）

  • 如果你想找到一个字符串，你有两个选项：

    如果字符串的大小小于N，则只需将其搜索到哈希表中~O（1）用于搜索，O（size_of_string）用于创建hash_key
    如果大小大于N，您只需创建大小为N的块，然后执行以下操作：搜索块并记住所有位置。然后你对下一个区块做同样的操作，并检查是否有连续的数字（例如：第一次我们有i，j，第二次我们有k，i+N，比i，i+N是一个很好的组合）保存连续对的最后一个数字（i，i+N，你只保留i+N），然后继续，直到你的堆栈中没有数字或你完成了单词
    希望它能有所帮助。

Lucene.NET是一个搜索引擎库，它使用索引进行文本扫描：http://incubator.apache.org/lucene.net/

相关文章：