两个大文件中匹配字符串的算法

Question

两个大文件中匹配字符串的算法

stringalgorithmsearchmatching

6

我有一个关于搜索算法的问题。我目前有两个纯文本文件，每个文件至少有1000万行。目前，每行都是一个字符串，我想在第一个文件中找到每个也出现在第二个文件中的字符串。有没有高效的方法来做到这一点？任何关于算法或特殊语言功能的建议都将不胜感激。

- Shang Wang

1

文件的格式是什么？CSV/定宽？文件中的行是否已排序？ - Arun

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

如果你不知道文件的结构（比如它们是否已排序），那么解决这个问题有许多不同的方法，这取决于你对内存和空间使用的限制，可能是你正在寻找的。如果你有大量可用的RAM，一种选择是在内存中创建一个哈希表来保存字符串。然后，将第一个文件中的所有字符串加载到哈希表中。然后，逐个加载第二个文件中的每个字符串。对于每个字符串，请检查它是否在哈希表中。如果是，则报告匹配项。此方法使用O(m)内存（其中m是第一个文件中的字符串数），并且需要至少Ω(m + n)时间，具体取决于哈希函数的工作方式。这也（几乎肯定）是解决问题最简单、最直接的方法。

如果可用的RAM不多，但时间不是太紧迫，可以使用修改过的第一种算法。选择从第一个文件中加载一些行。然后，仅将这些字符串加载到哈希表中。完成后，扫描整个第二个文件以查找任何匹配项。然后，将哈希表中的所有行驱逐出去，并加载第一个文件的下一组行并重复。这样运行时间为Ω(mn/b)，其中b是块大小（因为有O(m/b)次完整线性扫描第二个文件中的所有n字节）。或者，如果你知道一个文件比另一个文件小得多，你可能想考虑将整个文件加载到内存中，然后扫描另一个文件。

如果你的可用RAM不多，但有能力使用更多的磁盘空间，一个选择可能是使用外部排序算法对两个文件中的每个文件进行排序（或者至少构建一个目录，列出每个文件的行按排序顺序）。一旦你将文件按排序顺序排好，就可以并行地扫描它们，找到所有匹配项。这使用了在两个已排序范围中查找所有重复元素的更通用的算法，其工作方式如下：

1.跟踪两个索引，一个指向第一个列表，另一个指向第二个列表，两个索引都从零开始。 2.同时遍历两个列表： - 如果相应索引处的项目匹配，则报告匹配项。 - 否则，如果第一个列表中的项目小于第二个列表中的项目，则增加第一个列表的索引。 - 否则，增加第二个列表的索引。

这个算法大概需要O(n log n)的时间来排序两个文件，然后需要总共O(n)次比较来查找列表中的公共项。然而，由于字符串比较不一定在O(1)时间内运行（实际上，它们经常需要更长的时间），因此实际运行时间可能会更长。如果我们假设每个文件都包含n个长度为m的字符串，则排序的运行时间将是O(mn log n)，因为每个比较需要O(m)的时间。同样，比较步骤可能需要O(mn)的时间，因为每个字符串比较也可能需要长达O(m)的时间。作为可能的优化，您可以考虑计算一个小的哈希码（例如16或32位）。假设哈希码具有良好的均匀性，这可以大大减少比较字符串所需的时间，因为大多数不相同的字符串将具有不同的哈希码，并且可以在O(1)时间内进行比较。

最后，如果文件的每行都足够长（例如至少8个字符），则一个选择可能是为文件的每行计算64位或更大的哈希值。然后，您可以使用上述任何技术来尝试查看两个文件中是否重复了任何哈希码（将所有内容保存在哈希表中，使用外部排序等）。假设您的哈希码具有足够的位数，冲突的数量应该很少，并且您应该能够快速找到匹配项并使用更少的内存。

希望这可以帮助您！

哇哦！这是我在Stack Overflow上的第1000个答案！ :-)