一、概述
针对文本相似性计算,很多开发朋友首先想到的应该是使用向量空间模型VSM(Vector Space Model)。使用VSM计算相似度,先对文本进行分词,然后建立文本向量,把相似度的计算转换成某种特征向量距离的计算,比如余弦角、欧式距离、Jaccard相似系数等。这种方法存在很大一个问题:需要对文本两两进行相似度比较,无法扩展到海量文本的处理。想想像Google这种全网搜索引擎,收录了上百亿的网页,爬虫每天爬取的网页数都是百万千万级别的。为了防止重复收录网页,爬虫需要对网页进行判重处理。如果采用VSM方法,计算量是相当可观的。
二、思想
输入为一个N维向量V,比如文本的特征向量,每个特征具有一定权重。输出是一个C位的二进制签名S。
1)初始化一个C维向量Q为0,C位的二进制签名S为0。
2)对向量V中的每一个特征,使用传统的Hash算法计算出一个C位的散列值H。对1<=i<=C,
如果H的第i位为1,则Q的第i个元素加上该特征的权重;
否则,Q的第i个元素减去该特征的权重。
3)如果Q的第i个元素大于0,则S的第i位为1;否则为0;
4)返回签名S。
三、java实现
import java.math.BigInteger; import java.util.StringTokenizer; public class SimHash { private String tokens; private BigInteger strSimHash; private int hashbits = 128; public SimHash(String tokens) { this.tokens = tokens; this.strSimHash = this.simHash(); } public SimHash(String tokens, int hashbits) { this.tokens = tokens; this.hashbits = hashbits; this.strSimHash = this.simHash(); } public BigInteger simHash() { int[] v = new int[this.hashbits]; StringTokenizer stringTokens = new StringTokenizer(this.tokens); while (stringTokens.hasMoreTokens()) { String temp = stringTokens.nextToken(); BigInteger t = this.hash(temp); System.out.println("temp = " + temp+" : " + t); for (int i = 0; i < this.hashbits; i++) { BigInteger bitmask = new BigInteger("1").shiftLeft(i); if (t.and(bitmask).signum() != 0) { v[i] += 1; } else { v[i] -= 1; } } } BigInteger fingerprint = new BigInteger("0"); for (int i = 0; i < this.hashbits; i++) { if (v[i] >= 0) { fingerprint = fingerprint.add(new BigInteger("1").shiftLeft(i)); } } return fingerprint; } private BigInteger hash(String source) { if (source == null || source.length() == 0) { return new BigInteger("0"); } else { char[] sourceArray = source.toCharArray(); BigInteger x = BigInteger.valueOf(((long) sourceArray[0]) << 7); BigInteger m = new BigInteger("1000003"); BigInteger mask = new BigInteger("2").pow(this.hashbits).subtract( new BigInteger("1")); for (char item : sourceArray) { BigInteger temp = BigInteger.valueOf((long) item); x = x.multiply(m).xor(temp).and(mask); } x = x.xor(new BigInteger(String.valueOf(source.length()))); if (x.equals(new BigInteger("-1"))) { x = new BigInteger("-2"); } return x; } } public int hammingDistance(SimHash other) { BigInteger m = new BigInteger("1").shiftLeft(this.hashbits).subtract( new BigInteger("1")); BigInteger x = this.strSimHash.xor(other.strSimHash).and(m); int tot = 0; while (x.signum() != 0) { tot += 1; x = x.and(x.subtract(new BigInteger("1"))); } return tot; } public static void main(String[] args) { String s = "China people's Republic of China Chinese China people's Republic of China People's Republic of China"; SimHash hash1 = new SimHash(s, 128); System.out.println(hash1.strSimHash + " " + hash1.strSimHash.bitLength()); s = "China people's Republic of China Chinese China people's Republic of China"; SimHash hash2 = new SimHash(s, 128); System.out.println(hash2.strSimHash + " " + hash2.strSimHash.bitCount()); s = "China people's Republic"; SimHash hash3 = new SimHash(s, 128); System.out.println(hash3.strSimHash + " " + hash3.strSimHash.bitCount()); System.out.println("============================"); System.out.println(hash1.hammingDistance(hash2)); System.out.println(hash1.hammingDistance(hash3)); } }
相关推荐
Simhash算法是一种文本相似度计算中的关键技术,由Charikar于2002年提出。该算法主要通过将文本信息映射成一组“指纹”,即一系列哈希值,然后通过比较这些指纹的相似度来识别文本的相似性。Simhash算法因其检索速度...
文本相似度计算是自然语言处理和信息检索领域中的一个重要研究方向,它可以应用于过滤相似度很高的新闻、考试防作弊系统、论文抄袭检查等多个领域。文本相似度计算的方法有很多,主要来说有两种,一是余弦定律,二是...
### 基于汉明距离的文本相似度计算 #### 引言 随着信息技术的快速发展,文本信息检索已成为人们获取信息的重要手段之一。在信息检索技术中,如何准确有效地衡量文本之间的相似度是非常重要的问题。传统的文本...
在提供的资料中,可能包含多个实验对比,比如使用不同的词向量模型(如CBOW、Skip-gram)、不同的训练参数(如窗口大小、迭代次数)对文本相似度计算的影响。通过这些对比,我们可以深入理解不同模型和参数设置对...
3. **余弦相似度计算**:编写代码来执行上述的余弦相似度公式。 4. **测试与评估**:可能包括一些样例文本,用于验证系统的性能和准确性。 通过这样的系统,用户可以输入两篇文本,系统将返回它们的相似度得分,...
simhash高效的文本相似度去重算法实现simhash是什么Google发明的的文本去重算法,适合于大批量文档的相似度计算主要步骤对文本分词,得到N维特征向量(默认为64维)为分词设置权重(tf-idf)为特征向量计算哈希对...
基于Hadoop的文本相似度计算是一个重要的应用,常用于信息检索、推荐系统和文档分类等场景。在这个项目中,我们利用TF-IDF(词频-逆文档频率)和向量空间模型来计算文本之间的相似性,同时采用IKAnalyzer作为中文...
python自然语言处理-学习笔记(三)之文本相似度计算-附件资源
由一系列算法组成的Java版相似度计算工具包,目标是传播自然语言处理中相似度计算方法...SimHash + 汉明距离 Sørensen–Dice系数 知网义原 词语义原树 情感分析 正面倾向程度 负面倾向程度 情感倾向性 近似词 word2vec
本文提出的是一种新颖的文本相似度计算方法,这种新方法的核心在于采用码字(code words)来表征文本信息的特征,从而实现对文本相似性的快速和有效的计算。这种新方法相较于传统的文本相似度计算方法,主要具有两个...
该资源主要参考我的博客:word2vec词向量训练及中文文本相似度计算 http://blog.csdn.net/eastmount/article/details/50637476 其中包括C语言的Word2vec源代码(从官网下载),自定义爬取的三大百科(百度百科、互动...
中文文本句对相似度匹配-ATEC数据集_sentence-similarity
1.提供基于余弦相似度、编辑距离和Jaccard相似度等算法的文本相似度计算功能; 2.完成文本预处理功能,其中包括去除停用词、分词和词性标注等; 3.提供文本相似度计算结果的可视化功能,可以直观地展示两个文本之间...
1.提供基于余弦相似度、编辑距离和Jaccard相似度等算法的文本相似度计算功能; 2.完成文本预处理功能,其中包括去除停用词、分词和词性标注等; 3.提供文本相似度计算结果的可视化功能,可以直观地展示两个文本之间...
标题中的“一行代码使用BERT生成句向量,BERT做文本分类、文本相似度计算”揭示了BERT模型在自然语言处理(NLP)领域的广泛应用。BERT,全称为Bidirectional Encoder Representations from Transformers,是由Google...
综上所述,中文文本相似度匹配通常涉及预处理(如分词)、哈希表示(如simHash)和相似度计算(如海明距离)。这些技术结合在一起,可以有效解决中文文本的相似性问题,尤其在处理大量文本数据时,既保证了效率,又...
在IT领域,文本相似度计算是一项重要的技术,广泛应用于自然语言处理、信息检索、机器学习等领域。本资源提供了一个易语言实现的快速计算文本相似度的源码,可以帮助开发者高效地进行文本比较和分析。 易语言是一种...