algorithm - 在文件中找到两行相同的行

Question

我在亚马逊的一次采访中被问到这个问题。

您有一个包含许多行的文件，但其中两行是相同的。找到那两条线。我给出了在 N^2 时间内运行的明显答案。然后我想出了一个使用哈希表的答案，但他们也不喜欢这个答案，因为他们说如果文件以千兆字节为单位，它就行不通。我想出的另一个答案不是将哈希结果存储在内存中，而是创建一个与哈希值同名的文件，并将具有相同哈希值的行存储在文件中。他们要么无法理解我的解决方案，要么他们不喜欢它。

有什么想法吗？

谢谢

Answer 1

对于这个问题，我可以想到两类基本的解决方案：

1. 概率内存解决方案。 您可以尝试通过在主内存中存储文件行的摘要来解决此问题。然后，您可以在主内存中进行计算以识别可能的重复项，然后通过回顾磁盘检查每个可能的重复项。这些解决方案可能是最好的，因为它们具有低内存使用率、高效率和最小化磁盘访问。此类别中的解决方案包括

   1. 计算文件每一行的哈希值，然后存储哈希值。任何有哈希冲突的线都代表一对可能发生冲突的线，并且可以探索这些线​​。
   2. 使用布隆过滤器存储文件的所有行，然后只检查布隆过滤器中冲突的对。这本质上是 (1) 的变体，更节省空间。

2. 确定性的磁盘解决方案。您可以尝试使用磁盘上的整个数据集进行计算，将主内存用作临时暂存空间。这可以让您获得准确的答案，而不必将整个文件保存在内存中，但可能会更慢，除非您进行一些稍后的处理并且可以从重组数据中受益。此类别中的解决方案包括

   1. 使用外部排序算法（外部快速排序、外部基数排序等）对文件进行排序，然后对其进行线性搜索以查找一对重复元素。
   2. 构建一个磁盘上的数据结构，例如包含所有字符串的 B-tree，然后查询 B-tree。这需要大量的预处理时间，但会使以后对文件的操作更快。
   3. 将所有内容放入数据库并查询数据库。

希望这可以帮助！

Answer 2

您可以使用布隆过滤器：

http://en.wikipedia.org/wiki/Bloom_filter

然后，您可以检测（几乎没有误报）重复的行并将其存储在内存中，然后再次浏览文件。

两次遍历文件，内存占用极少，美观

Answer 3

遍历线条并计算每条线的长度。你最终会得到类似的东西：

0: 4  
1: 6  
2: 10  
3: 4  
....  

只比较那些长度相同的线。使用此类索引可以进一步优化（例如，不将所有内容存储在平面数组中，而是存储在某种树中，或其他任何东西中）。

顺便说一句，由于性能原因，您对文件的第二个想法可能会被拒绝。对硬盘进行频繁的随机 IO 通常是个坏主意：尝试在内存中尽可能多地存储。