python:在文件中搜索

Question

我有两个文本文件,都是大约1M行.我们称它们为f1和f2.

对于f1中的每一行,我需要在f2中找到行的索引,其中f1中的行是f2中行的子串.由于我需要为f1的所有行执行此操作,因此使用嵌套for循环的时间过于昂贵,我想知道是否有可以显着减少时间的变通方法.

提前感谢您的帮助.

Answer 1

肯定有比使用两个for循环更好的方法:D这会给你一个O(n ^ 2)运行时.查找子字符串非常有用的东西称为滚动哈希.这是一种使用以前的信息来加速查找子串的方法.它是这样的:

说我有字符串f1 = "cat"和长字符串f2 = "There once was a cat named felix".你要做的是根据你的f1字符串的字母定义一个"哈希".有关这方面的细节可以在各种来源的网上找到,但是对于这个例子,我们可以简化一些事情,并说字母被分配给从0开始到25的数字,我们将每个字母的值相乘以形成一个十进制数字,其数量为数字等于字符串的长度:

hash("cat") = 10^2 * 2 + 10^1 * 0 + 10^0 * 19
            = some value (in python the "hash" values of letters 
              are not 0 through 25 but given by using the ord cast: 
              ord("a") will give you 97)

现在这个下一部分非常酷.我们指定f1字符串大小的窗口,大小为3,并以与f1相同的方式对f2字符串进行散列.你从前三个字母开始.哈希不匹配所以我们继续前进.如果哈希匹配,我们确保它是相同的字符串(有时哈希相等,但不是相同的字符串,因为我们分配哈希的方式,但没关系).

COOL PART**我们不是简单地移动窗口并重新整理f2的2到4字母,而是"滚动"窗口并且不重新计算整个哈希(如果f1真的很长则会浪费时间),因为只改变字母是第一个也是最后一个!诀窍是减去第一个哈希值(在我们的示例中将是ord("t")*10 ^ 2),然后将剩余的整数乘以10(因为我们将所有内容移到左侧),并添加新哈希字母,ord("r")*10 ^ 0.再次检查匹配并继续.如果匹配,则返回索引.

为什么我们这样做:如果你有足够长的f1字符串,你将运行时间减少到O(n*len(n)),以便渐近线性!

现在,实际的实现需要时间,可能会变得混乱,但有很多来源在线这种答案.我的算法类在线有很好的课程笔记,有助于理解这个理论,并且有很多与python实现的链接.希望这可以帮助!