python:在文件中搜索

Question

我有两个大约 100 万行的文本文件。我们称它们为 f1 和 f2。

对于 f1 中的每一行，我需要找到 f2 中行的索引，其中 f1 中的行是 f2 中行的子字符串。由于我需要对 f1 的所有行都执行此操作，因此使用嵌套 for 循环太费时了，我想知道是否有可以显着减少时间的解决方法。

提前感谢您的帮助。

Answer 1

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

假设我有字符串 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 字符串。你从前三个字母开始。哈希值不匹配，所以我们继续。如果散列匹配，我们确保它是相同的字符串(有时散列彼此相等，但由于我们分配散列的方式不同，所以不是相同的字符串，但没关系)。

很酷的部分** 不是简单地移动窗口并重新散列 f2 的第 2 到第 4 个字母，我们“滚动”窗口并且不重新计算整个散列(如果 f1 真的很长，那将是浪费时间) 因为唯一改变的字母是第一个和最后一个!诀窍是减去第一个哈希值(在我们的示例中是 ord("t")*10^2)，然后将剩余的整个数字乘以 10(因为我们将所有内容都移到了左边)，然后添加新的哈希值字母，ord(“r”)* 10^0。再次检查匹配并继续。如果匹配，则返回索引。

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

现在，实际实现需要时间并且可能会变得困惑，但网上有大量资源可以提供此类答案。 My algorithms class在网上有很好的类(class)笔记，有助于更好地理解理论，并且有大量与 python 实现的链接。希望这对您有所帮助!