一、概述
针对文本相似性计算,很多开发朋友首先想到的应该是使用向量空间模型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 海明距离 IK分词 完整的可运行的示例代码 包含simHash 算法,使用IK 对中文文本进行分词处理
文本相似度计算的Simhash算法的实现与改进
kmeans算法 文本相似度计算(可控制台手动输入数据)
java实现的文本相似度系统,使用向量空间模型以及余弦相似度距离公式,实测可以实现2篇文本的相似度计算且有一定的效果。
传统的文本分类中相似度的计算, 是根据欧氏空间中向量之间夹角的余弦值来表征的, 它根据...念, 由汉明距离的计算公式, 得到了一种全新的文本相似度的计算方法, 与传统的方法相比较, 它具有简便, 快速等优点。
为了降低中文文本相似度计算方法的时间消耗、提高文本聚类的准确率,提出了一种PST_LDA(词性标注潜在狄利克雷模型)中文文本相似度计算方法。首先,对文本中的名词、动词和其他词进行词性标注;然后,分别对名词、...
,,,
,,,
该文则首先建立文本集与码字集之间的 #.# 对应关系, 然后借用编码理论中汉明距离的概念, 由汉明距离的计算公式, 得到了一种全新的文本相似度的计算方法, 与传统的方法相比较, 它具有简便, 快速等优点。
python自然语言处理-学习笔记(三)之文本相似度计算-附件资源
由一系列算法组成的Java版相似度计算工具包,目标是传播自然语言处理中相似度计算方法...SimHash + 汉明距离 Sørensen–Dice系数 知网义原 词语义原树 情感分析 正面倾向程度 负面倾向程度 情感倾向性 近似词 word2vec
simhash高效的文本相似度去重算法实现simhash是什么Google发明的的文本去重算法,适合于大批量文档的相似度计算主要步骤对文本分词,得到N维特征向量(默认为64维)为分词设置权重(tf-idf)为特征向量计算哈希对...
本文深入研究文本语义相似度计算方法,主要研究内容如下:(1)基于结构化表示的文本语义相似度计算方法针对句子级文本相似度计算方法中平面特征表征性弱的问题,本文提出了应用结构化特征来表示句子级文本的句法、语义等...
1.提供基于余弦相似度、编辑距离和Jaccard相似度等算法的文本相似度计算功能; 2.完成文本预处理功能,其中包括去除停用词、分词和词性标注等; 3.提供文本相似度计算结果的可视化功能,可以直观地展示两个文本之间...
该资源主要参考我的博客:word2vec词向量训练及中文文本相似度计算 http://blog.csdn.net/eastmount/article/details/50637476 其中包括C语言的Word2vec源代码(从官网下载),自定义爬取的三大百科(百度百科、互动...
传统的文本相似度计算大多基于词匹配的方法,忽略了词汇语义信息,计算结果很大程度上取决于文本的词汇重复率。虽然分布式词向量可以有效表达词汇语义关系,但目前基于词向量的文本处理方法大多通过词汇串联等形式...
基于Hadoop的文本相似度计算的代码 是用TFIDF 和向量空间模型,IKAnlayze来弄的 有代码,只是用来参考的 只是一个算法的演示,用于保存,以后查看的
词林,知网,字符向量,用于自然语言处理中的文本相似度计算词林,知网,字符向量,用于自然语言处理中的文本相似度计算词林,知网,字符向量,用于自然语言处理中的文本相似度计算词林,知网,字符向量,用于自然...