查找文本文件中字符串的所有出现的行号
本文关键字:文件 字符串 查找 文本 | 更新日期: 2023-09-27 18:09:37
我想写一个函数,做以下事情:
给定一个文本文件,我想找到这个文件中某个字符串的所有出现;然后,对于每次出现,应该将找到它的行添加到列表中。我们假设每行最多只出现一次。文本文件可能会变得非常大,这意味着简单的for循环遍历文件的每行会太慢。
例如,假设我们有一个文件,其内容为:
- h j k l m n o
如果我要搜索"A",该函数将在第1行和第3行找到它,因此将1和3添加到列表中(然后返回列表)。
我正在考虑二进制搜索,但它似乎需要一个列表排序和元素是不同的-我正在寻找相同的值。
那么,有没有其他的搜索算法,我可以基于我的函数,与二分搜索大致相同的性能?
谢谢!
您可以索引您的行,如果它们不经常更改并且您将对它们执行许多搜索。索引它们的一种方法是创建一个直方图,显示哪些字符在哪些行中出现(可能还有出现多少次)。然后你可以反过来说,字母A,例如,出现在第5,10和20行。如果你正在搜索"ABF",你可以使用倒直方图来确定哪些行是候选的(即,包含字母"A","B"answers"F"),然后只看这些行。
这是否是一个有效的策略将取决于搜索的选择性和搜索字符串的长度,以及其他因素。只有测试才能揭示该算法是否适合您的特定使用模式。