一、概述
针对文本相似性计算,很多开发朋友首先想到的应该是使用向量空间模型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)); } }
相关推荐
文本相似度计算是自然语言处理和信息检索领域中的一个重要研究方向,它可以应用于过滤相似度很高的新闻、考试防作弊系统、论文抄袭检查等多个领域。文本相似度计算的方法有很多,主要来说有两种,一是余弦定律,二是...
在文本相似度计算中,KMeans可以用来识别和归类具有相似主题或内容的文本。以下是对这个主题的详细解释。 ### KMeans算法基本原理 1. **初始化**: 首先,选择k个初始质心,通常是随机选取数据集中的一些样本点。 2...
### 基于汉明距离的文本相似度计算 #### 引言 随着信息技术的快速发展,文本信息检索已成为人们获取信息的重要手段之一。在信息检索技术中,如何准确有效地衡量文本之间的相似度是非常关键的问题。传统的文本...
该文则首先建立文本集与码字集之间的 #.# 对应关系, 然后借用编码理论中汉明距离的概念, 由汉明距离的计算公式, 得到了一种全新的文本相似度的计算方法, 与传统的方法相比较, 它具有简便, 快速等优点。
python自然语言处理-学习笔记(三)之文本相似度计算-附件资源
由一系列算法组成的Java版相似度计算工具包,目标是传播自然语言处理中相似度计算方法...SimHash + 汉明距离 Sørensen–Dice系数 知网义原 词语义原树 情感分析 正面倾向程度 负面倾向程度 情感倾向性 近似词 word2vec
4. **相似度计算**:最后,通过比较两个文本的SimHash值的汉明距离(Hamming Distance),来评估它们的相似度。汉明距离越小,说明两个文本越相似。 在实际应用中,这个库可以用于如下的场景: - **文本相似度检测*...
该资源主要参考我的博客:word2vec词向量训练及中文文本相似度计算 http://blog.csdn.net/eastmount/article/details/50637476 其中包括C语言的Word2vec源代码(从官网下载),自定义爬取的三大百科(百度百科、互动...
1.提供基于余弦相似度、编辑距离和Jaccard相似度等算法的文本相似度计算功能; 2.完成文本预处理功能,其中包括去除停用词、分词和词性标注等; 3.提供文本相似度计算结果的可视化功能,可以直观地展示两个文本之间...
文本相似度计算是自然语言处理中的一项基础性研究,通过总结和分析文本相似度计算的经典方法和当前最新的研究成果,完善对文本相似度计算方法的系统化研究,以便于快速学习和掌握文本相似度计算方法。 文本相似度...
1.提供基于余弦相似度、编辑距离和Jaccard相似度等算法的文本相似度计算功能; 2.完成文本预处理功能,其中包括去除停用词、分词和词性标注等; 3.提供文本相似度计算结果的可视化功能,可以直观地展示两个文本之间...
标题中的“一行代码使用BERT生成句向量,BERT做文本分类、文本相似度计算”揭示了BERT模型在自然语言处理(NLP)领域的广泛应用。BERT,全称为Bidirectional Encoder Representations from Transformers,是由Google...
综上所述,中文文本相似度匹配通常涉及预处理(如分词)、哈希表示(如simHash)和相似度计算(如海明距离)。这些技术结合在一起,可以有效解决中文文本的相似性问题,尤其在处理大量文本数据时,既保证了效率,又...
在IT领域,文本相似度计算是一项重要的技术,广泛应用于自然语言处理、信息检索、机器学习等领域。本资源提供了一个易语言实现的快速计算文本相似度的源码,可以帮助开发者高效地进行文本比较和分析。 易语言是一种...
在中文文本处理中,可以将待比较的文本转换为词向量序列,然后计算这两个序列的平均向量,再用该平均向量与其他词向量进行相似度计算,从而判断文本间的关系。 **应用场景** word2vec词向量在NLP(自然语言处理)...
基于 Python 的文本相似度计算系统源码数据库是一个完整的毕业设计论文,讨论了自然语言处理中文本相似度计算的重要性和挑战性。该系统使用 Python 语言开发,旨在解决文本处理和分析的挑战,提供了一个基于文本...
TF-IDF(Term Frequency-Inverse Document Frequency)是一种在信息检索和自然语言处理中广泛使用的文本相似度计算方法。它的核心思想是评估一个词在文档中的重要性,即它在当前文档中的频率(TF)和在整个文档集合...