知识卡片
SimHash把文档压成指纹
完全相同的页面约占全部页面的 20%,去重能省存储、避免重复抓取、还能把死链导向同内容页面。但百万级文档两两比文本不现实,所以要先把文档压成定长指纹。
SimHash 是局部敏感哈希的一个特例,四步:分词去噪后给每个特征词加权;用哈希函数把每个词映射成定长二进制串;按权重改写——比特为 1 记 +w、为 0 记 −w,再把所有词的向量逐位累加;最后逐位判决,大于 0 取 1、小于等于 0 取 0,得到文档指纹。两个指纹的相似度用海明距离(不同比特位的个数)衡量。
它流行的原因是「局部敏感」:文档越相似,指纹越接近,而算哈希比算文本相似度快得多、也省空间。压缩必然丢信息,所以要在压缩率与准确度之间取平衡——位数太长省不下空间,太短则不同文档撞在一起。
结构图:
flowchart TD
A[文档] --> B[分词去噪并加权]
B --> C[每词哈希为定长二进制]
C --> D[按权重改写为 ±w 向量]
D --> E[逐位累加]
E --> F[大于0取1,否则取0]
F --> G[文档指纹]
G --> H[按海明距离判相似]
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第4章 搜索系统框架及原理 · 查看原书依据
该算法流行的原因是:两个文档越相似,其对应的两个哈希值也就越接近,且哈希值的计算明显比文本计算快很多,同时也节省空间。
参考来源
- 位置:《智能搜索和推荐系统:原理、算法与应用(零基础掌握搜索和推荐系统的原理、架构、算法) (智能系统与技术丛书)》第4章 搜索系统框架及原理(源文件:extracted/智能搜索和推荐系统:原理、算法与应用(零基础掌握搜索和推荐系统的原理、架构、算法) (智能系统与技术丛书)/_epub-src/text/part0060.html)
- 结论依据:原文点明 SimHash 的两项优势——相似文档哈希接近(局部敏感性)与计算、存储成本低,这是它成为主流去重方案的原因。
- 原始内容:该算法流行的原因是:两个文档越相似,其对应的两个哈希值也就越接近,且哈希值的计算明显比文本计算快很多,同时也节省空间。