改进的shingling算法（On the Evolution of Clusters of NearDuplicateWeb）

### 改进的Shingling算法：《On the Evolution of Clusters of Near-Duplicate Web Pages》 #### 引言 本文旨在深入解析一篇名为“On the Evolution of Clusters of Near-Duplicate Web Pages”的英文原版论文，该论文由Dennis Fetterly、Mark Manasse与Marc Najork共同撰写。这篇研究论文探讨了近似重复网页的聚类随时间演化的特性，并且介绍了一种改进的shingling算法来辅助搜索引擎进行网页去重的工作。 #### Shingling算法概述 Shingling算法是一种用于度量文档间相似性的技术，它最初由Broder等人在1997年提出。这种算法的核心思想是将文档转换为一系列shingle（即文档中相邻词的固定长度序列），并利用这些shingle来比较不同文档之间的相似度。如果两个文档拥有相同的shingle集，则认为这两个文档是相等的；如果它们的shingle集有显著的交集，则可以判断这两个文档高度相似。 #### 改进的Shingling算法 在本论文中，作者们针对原有shingling算法进行了改进，目的是提高其在实际应用中的效率和准确性。具体来说，改进主要包括以下几个方面： 1. **无偏确定性抽样**：为了减少存储需求和降低文档比较时的计算复杂度，Broder等人采用了一种无偏确定性抽样技术来从每个文档的shingle集中抽取一个小而具有代表性的子集。这一技术不仅能够有效减少存储空间的需求，还能显著减少文档比较时所需的计算资源。 2. **稳定性分析**：论文还关注了近似重复文档聚类随时间的变化趋势。通过对150百万个网页每周进行下载并跟踪分析，研究人员发现大约29.2%的网页与其他页面非常相似，而22.2%的页面几乎完全相同。更进一步的研究显示，一旦两个文档被认为是近似重复的，那么它们在未来十周内仍然保持这种状态的概率非常高。这一发现对于搜索引擎来说具有重要的意义。 3. **搜索引擎优化策略**：基于上述稳定性分析的结果，论文提出了一些针对搜索引擎的优化建议。例如，当发现两篇文档是近似重复时，爬虫程序可以决定只对其中一个版本进行重新抓取，或者至少降低其他版本的抓取优先级，从而节省爬虫资源，让这些资源可以更高效地应用于其他更有价值的地方。 #### 论文贡献 通过这项研究，作者们不仅验证了改进后的shingling算法的有效性，而且也为搜索引擎提供了宝贵的优化思路。具体来说，该研究的主要贡献包括： - 提出了一个改进的shingling算法，该算法能够在保证准确度的同时显著减少计算资源的需求。 - 首次系统地研究了近似重复网页聚类的时间演化特性，并揭示了这些聚类具有较高的稳定性。 - 为搜索引擎提供了一种有效的去重方法，有助于提升爬虫效率并改善用户体验。 《On the Evolution of Clusters of Near-Duplicate Web Pages》是一篇在搜索引擎领域具有重要意义的研究论文。它不仅对shingling算法进行了改进，还提出了针对搜索引擎优化的具体策略，对于提高搜索引擎的性能具有重要的指导作用。