京公网安备11010502063487号两个页面不完全一样,但内容几乎相同(换了广告、时间戳、几句话)。爬虫怎么判断?SimHash 是常见答案。这篇在一个合成语料上量一量:改了多少词汉明距离是多少、阈值怎么选、站点模板会怎样把所有页面拉近。
150 篇原文(各 400 个词),每篇另有改了 1%、5%、15% 的词的 3 个变体;另有 150 篇互不相关的文章。所有页面共用同一段 600 词的站点模板(导航、页脚)。共 750 篇
合成语料:150 篇 400 词的原文,每篇有改了 1%、5%、15% 词的 3 个变体,150 篇不相关文章,所有页面共用 600 词的模板。词是随机生成的 w0…w5999(近似 Zipf 分布),不是真实网页,结论只用来展示机制。
文章对 只对正文 含 600 词站点模板 原文 与 改 1% 最小 0、中位 1、最大 8 最小 0、中位 0、最大 3 原文 与 改 5% 最小 0、中位 4、最大 9 最小 0、中位 1、最大 4 原文 与 改 15% 最小 1、中位 7、最大 15 最小 0、中位 2、最大 6 互不相关的两篇 最小 4、中位 18、最大 36 最小 0、中位 6、最大 15 (对照:原文与变体的词集合 Jaccard 相似度平均 0.869;随机两篇的词集合 Jaccard 平均 0.150)
只对正文时,改得越多距离越大(中位 1、4、7),不相关的两篇中位 18。把站点模板一起做,变体之间的距离更小了,但不相关的页面也被拉近:中位只有 6,最小 0。
共 450 对"原文-变体"正例,279,975 对不相关的负例
k 召回(只对正文) 误报对数 召回(含模板) 误报对数
0 8.9% 0 31.6% 275
3 47.6% 0 93.1% 37005
6 76.0% 50 100.0% 194111
10 96.9% 2968 100.0% 278026
14 99.8% 38029 100.0% 279974
18 100.0% 144395 100.0% 279975
22 100.0% 243971 100.0% 279975
26 100.0% 276036 100.0% 279975只对正文,k=3 误报为 0 但召回只有 47.6%;k=10 召回 96.9% 但误报 2968 对。含站点模板时,k=3 召回 93.1% 看起来很好,可是 279,975 对无关文章里有 37005 对被判成重复。近似去重之前要先去掉导航、页脚这类共用的模板文字。
只对正文(3 元组):原文与改 5% 的距离 最小 4、中位 11、最大 21;原文与改 15% 的距离 最小 7、中位 19、最大 27;不相关的两篇 最小 14、中位 32、最大 50 含模板(3 元组):原文与改 5% 的距离 最小 2、中位 7、最大 14;原文与改 15% 的距离 最小 4、中位 12、最大 21;不相关的两篇 最小 5、中位 20、最大 35
用词的 3 元组而不是单个词当特征,不相关的文章与有关联文章的距离拉得更开(中位 32 对 11),但对同样的编辑,变体的距离也更大,阈值要重新选。
计算 400 词文章的 SimHash:1.47 ms/篇(纯 Python);两两比较 280,875 对汉明距离:0.07 秒,约 3.90 百万对/秒。两两比较是 O(n²),文章数到百万级就必须用索引(按位段分桶)
每篇 1.47 ms 的 SimHash 计算和每秒约 400 万对的比较,在几千篇规模没有压力;百万篇就需要索引,我没有实现。