我一直听说布隆过滤器如何在网络爬虫中发挥作用，尤其是在确定 URL 是否已经被爬取时（因为布隆过滤器在测试集合成员时内存效率很高）。
但是，在网络爬虫的用例中，考虑到遇到几乎无限数量的 URL，比特/桶的数量是否需要很大？特别是，如果您是 Google 或尝试每天抓取数据的搜索引擎。
所以我的问题是，当 url 的数量不断增加并且桶的数量保持不变时，布隆过滤器如何帮助确定 URL 是否已经被抓取？
问问题
1528 次
2 回答
3
布隆过滤器基于哈希函数，它产生有限范围的值。无论遇到多少个 URL，每个函数都将返回其范围内的值之一。使用多个散列函数来选择位可以减少误报的可能性，但这总是有可能的。然而，它的概率很小，并且是准确性和效率之间的计算权衡。
URL 的长度有实际限制，请参阅这个问题。诚然，这是一个惊人的数字。当创建更多 URL 时，可能需要升级散列函数和存储桶大小，但今天可用的那些已经非常有能力应对当今可用的 URL，并且错误率可以接受。
于 2013-06-15T04:55:36.267 回答
2
对于这个用例，除非有大量的存储桶，否则您将遇到很大比例的误报（无论如何，几乎不可能完全消除误报，即使对于一个小型应用程序也是如此）。
一个有趣的解决方法是使用多级布隆过滤器而不是具有扁平结构，例如，第一级仅基于域名（例如 cnn.com），下一层可能包含扩展 url（例如如 cnn.com/sports/athletics）。但是当涉及到字符串操作和多个散列函数时，不确定它的性能如何。
于 2013-06-15T06:16:40.250 回答