首页 > 试题广场 >

假设有10亿网页已经被我们存下来，现在希望去掉其中的重复网页

[问答题]

假设有10亿网页已经被我们存下来，并提供如下信息：网页全文（即网页的源码）、全文长度、网页正文（即网页中提取的主体文字）、
正文长度，以及其他网页提取物等，现在希望去掉其中的重复网页，请提出可行的方案，计算出每个网页对应的重复度，你可以自己
对网页重复下定义，也可以提出需要哪些更多的网页提取物来实现更好的去重复方案。

牛客304487号

10亿网址，假设每个网址平均长度为100字符，则这份网址的列表将占据400G，直接创建散列表再查找可能非常低效。考虑利用分而治之的思想，有以下两种解法。

解法1：先将所有数据储存到一台机器上，对数据进行2次扫描，第一次扫描将网址列表拆分为400组，每组1G。可以将每个网址u存放在名为<x>.txt的文件中，其中x=hash(u)%400。我们会根据网址的散列值分割这些网址，这样所有散列值相同的网址都会被存进同一个文件。第二次扫描可以将文件载入内存，创建网址的散列表，找出重复的。

解法2：可以使用多台机器，此时我们将网址发送到机器x上，而不是储存至文件<x>.txt上。这种方法的优点是可以并行的执行该操作，同时处理400个分组，对于海量数据能迅速有效的解决问题。缺点是必须依靠400台机器，要做到准确无误较难，需要考虑如何处理机器故障，且这样也会增加系统的复杂性，需要更高的成本。

发表于 2015-06-29 21:01:08 回复(0)