布隆过滤器在网页去重中的研究与应用

摘要

随着互联网的发展，网络信息呈爆炸性的增长。大量的信息一方面给人们带来了更多的消息来源，而另一方面也给人们搜索有用的信息带来巨大的负担。根据中国互联网络信息中心CNNIC在2012年的统计:2011年全球网页的数量已经达到866亿个，而2012年这个数字已经增加到了1227亿个。因此如何更有效的消除互联网中的重复信息，让人们便捷的找到所求，已经成为现代互联网的一个重要的问题。
　　 布隆过滤器(Bloom Filter)是1970年提出的一种去重算法，它实际上是由一个很长的二进制向量和一系列随机映射函数组成的。如今，他已经运用在了很多领域，并且通过国内外的研究，逐渐改进了算法的缺点。
　　 本文从理论和应用同时入手，通过实验的方法，找到布隆过滤器在网页去重领域比较好的改进方案。
　　 首先，本文介绍了重复网页的概念和种类，总结了重复网页产生的原因。并且简要介绍了一些相关概念。
　　 其次，重点介绍了布隆过滤器以及其改进算法。以改进布隆过滤器的缺陷为出发点，选定了计数布隆过滤器和多维布隆过滤器这两种改进算法，并且在理论上对它们进行了分析，阐述了三种算法运行效率和优缺点。
　　 最后，论文进行了实验设计，通过创建一定规模的集合来分析三种算法，并且根据分析结果得出了结论，为进一步改进布隆过滤器在网页去重中的应用指出了参考方向。

目录

声明

摘要

第1章 绪论

1．1 研究背景与意义

1．2 国内外研究现状

1．3 本文组织结构

第2章 网页去重相关理论

2．1 搜索引擎介绍

2．2 重复网页介绍

2．3 重复网页产生的原因

2．4 搜索引擎的评价标准

2．4．1 准确率与召回率

2．4．2 平均准确率

2．4．3 重复网页对搜索结果的影响

2．5 本章小结

第3章 布隆过滤器及其改进算法介绍

3．1 标准布隆过滤器

3．1．1 标准布隆过滤器介绍

3．1．2 性能分析

3．1．3 算法缺点

3．2 计数布隆过滤器

3．2．1 计数布隆过滤器介绍

3．2．2 性能分析

3．3 多维布隆过滤器

3．3．1 多维布隆过滤器介绍

3．3．2 性能分析

第4章 模拟实验

4．1 实验评价标准

4．2 程序实现方式

4．3 Heritrix结构

4．4 代码结构

4．4．1 数据结构

4．4．2 哈希函数

4．4．3 方法函数

4．5 实验结果

4．5．1 标准布隆过滤器

4．5．2 计数布隆过滤器

4．5．3 多维布隆过滤器

4．6 本章小结

第5章 工作总结与展望

5．1 工作总结

5．2 后期展望

参考文献

致谢