SimHash 是怎么构造的?

简介: SimHash是Google提出的局部敏感哈希算法,通过普通哈希函数为关键词生成哈希值并保留权重信息。将关键词哈希值转为±1向量,乘以权重后按位相加,最终正负判断生成0/1指纹。该方法简化了高维空间划分,保留关键词重要性,使相似文档生成相近哈希值,广泛应用于去重与相似性检测。(238字)

不过,这种构造局部敏感哈希函数的方式也有一些缺陷:在原来的空间中,不同维度本来是有着不同权重的,权重代表了不同关键词的重要性,是一个很重要的信息。但是空间被 n 个超平面随机划分以后,权重信息在某种程度上就被丢弃了。

那为了保留维度上的权重,并且简化整个函数的生成过程,Google 提出了一种简单有效的局部敏感哈希函数,叫作 SimHash。它其实是使用一个普通哈希函数代替了 n 次随机超平面划分,并且这个普通哈希函数的作用对象也不是文档,而是文档中的每一个关键词。这样一来,我们就能在计算的时候保留下关键词的权重了。这么说有些抽象,让我们一起来看看 SimHash 的实现细节。

方便起见,我们就以 Google 官方介绍的 64 位的 SimHash 为例,来说一说它构造过程。整个过程,我们可以总结为 5 步。

  1. 选择一个能将关键词映射到 64 位正整数的普通哈希函数。
  2. 使用该哈希函数给文档中的每个关键词生成一个 64 位的哈希值,并将该哈希值中的 0 修改为 -1。比如说,关键词 A 的哈希值编码为 <1,0,1,1,0>,那我们做完转换以后,编码就变成了 <1,-1,1,1,-1>。
  3. 将关键词的编码乘上关键词自己的权重。如果关键词编码为 <1,-1,1,1,-1>,关键词的权重为 2,最后我们得到的关键词编码就变成了 <2,-2,2,2,-2>。
  4. 将所有关键词的编码按位相加,合成一个编码。如果两个关键词的编码分别为 <2,-2,2,2,-2> 和 <3,3,-3,3,3>,那它们相加以后就会得到 <5,1,-1,5,1>。
  5. 将最终得到的编码中大于 0 的值变为 1,小于等于 0 的变为 0。这样,编码 <5,1,-1,5, 1> 就会被转换为 <1,1,0,1,1> 。

通过这样巧妙的构造,SimHash 将每个关键词的权重保留并且叠加,一直留到最后,从而使得高权重的关键词的影响能被保留。从上图中你可以看到,整个文档的 SimHash 值和权重最大的关键词 word 2 的哈希值是一样的。这就体现了高权重的关键词对文档的最终哈希值的影响。此外,SimHash 通过一个简单的普通哈希函数就能生成 64 位哈希值,这替代了随机划分 64 个超平面的复杂工作,也让整个函数的实现更简单。

相关文章
|
3月前
|
人工智能 前端开发 Java
关于Agent框架,豆包,DeepSeek、Manus都选择了它
2025年被视为Agent元年,通过向Manus、豆包、DeepSeek提问“编程框架第一性原理”,发现三者不约而同推荐阿里巴巴开源的AgentScope。
612 2
关于Agent框架,豆包,DeepSeek、Manus都选择了它
|
存储 缓存 移动开发
|
4月前
|
编解码 算法 前端开发
java后端开发学习路线+避坑指南
java后端开发学习路线+避坑指南
|
2月前
|
存储 NoSQL 前端开发
告别踩坑!若依图片验证码实现与改造指南
若依(RuoYi)框架中图片验证码的完整实现逻辑、核心代码和定制化方法,我会从实现原理、核心代码拆解、关键配置、定制化改造四个维度讲解,覆盖验证码生成、存储、校验全流程,让你既能理解原理,也能按需修改验证码样式 / 规则。
205 10
|
4月前
|
数据采集 存储 机器学习/深度学习
搜索引擎的整体架构和工作过程
搜索引擎由爬虫、索引和检索三大系统构成:爬虫负责抓取网页并存储;索引系统对网页去重、分析并构建倒排索引;检索系统通过查询分析、相关性排序等技术,返回精准结果。全过程融合文本分析、机器学习与大规模计算,确保高效准确搜索。
|
4月前
|
算法 搜索推荐
如何使用概率模型中的 BM25 算法进行打分?
BM25是一种基于概率模型的文本相关性打分算法,可视为TF-IDF的升级版。它综合考虑词频(TF)、逆文档频率(IDF)、文档长度及查询词频,并引入非线性增长与饱和机制。通过参数k1、k2和b调节词频权重、文档长度影响和查询词权重,使评分更精准。广泛应用于Elasticsearch、Lucene等搜索引擎中。
|
4月前
|
算法 搜索推荐
经典的 TF-IDF 算法是什么?
TF-IDF是衡量词与文档相关性的经典算法,由词频(TF)和逆文档频率(IDF)相乘得出。TF反映词在文档中的重要性,IDF体现词的区分度。词频越高、文档频率越低的词,权重越大。通过累加各词项的TF-IDF值,可计算查询与文档的整体相关性,广泛应用于搜索引擎排序。
|
4月前
|
搜索推荐 数据库 索引
广告引擎的整体架构和工作过程
广告引擎核心是匹配用户与广告。通过用户标签、广告位信息及广告主定向条件,构建倒排索引,实现高效召回与排序,0.1秒内完成广告返回,并实时监测展现、点击与计费,确保精准投放与预算控制。
|
4月前
|
消息中间件 Java 程序员
SpringCloud(2026)
本课程基于传智教育·黑马程序员教学资源,系统讲解Spring Cloud微服务架构实战,涵盖服务注册、远程调用、网关、配置中心等核心应用,并深入RabbitMQ消息队列、ElasticSearch搜索技术及高频面试题解析,结合AI辅助开发与实操训练,助力高效掌握企业级微服务开发与面试要点。
|
4月前
|
人工智能 数据可视化 安全
通过阿里云 Chat App 合规接入 WhatsApp Business API:WABA 注册指南
本文将详解如何通过阿里云 Chat App 消息服务完成WABA 账号注册。
711 0