我有一个非常大的文本文档。我正在实现“搜索”功能以查找文件中给定字符串的出现并显示其位置。它不仅是整个单词搜索,它还可以包含单词/句子/段落的一部分。我正在为这个过程研究高效的数据结构。如果是全词搜索,我可以使用 tries/哈希表。由于文件非常大,我将无法使用后缀数组/后缀树。排序也不是那么有效。其他简单的选择就是使用框架的字符串搜索/正则表达式功能,这需要线性时间。这种操作是否有更好的方法?最初它只是字符串搜索,后来计划用元字符进行搜索。
最佳答案
Trie 和后缀树/数组是一个不错的选择,但如果您不喜欢它们,我还有另一种解决方案:创建一个哈希表:
- 为所有长度为 1、2、3、.. N 的字符串创建一个哈希表,其中 N 是您想要的任何数字,复杂度为 O(N * size_of_text)
如果你想找到一个字符串,你有两个选择:
如果字符串的大小小于 N 你只需将它搜索到哈希表中 ~O(1) 用于搜索和 o(size_of_string) 用于创建 hash_key
如果大小大于 N 你只需创建大小为 N 的 block 并执行此操作:搜索一个 block 并记住所有位置。比你对下一个 block 做同样的事情并检查是否有连续的数字(例如:第一次我们有 i, j 和第二次我们有 k, i+N ,比 i, i+N 是一个很好的组合)保存连续对的最后一个数字(i,i+N,你只保留 i+N)并继续,直到你的 Stack 中没有数字或者你完成了这个词
希望对您有所帮助。
关于c# - 文件搜索功能的有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9322857/