Ⅰ 如何用wordnet计算 文本相似度 算法实现
1.信息检索中的重要发明TF-IDF
1.1TF
Term frequency即关键词词频，是指一篇文章中关键词出现的频率，比如在一篇M个词的文章中有N个该关键词，则
（公式1.1-1）
为该关键词在这篇文章中的词频。
1.2IDF
Inverse document frequency指逆向文本频率，是用于衡量关键词权重的指数，由公式
（公式1.2-1）
计算而得，其中D为文章总数，Dw为关键词出现过的文章数。
2.基于空间向量的余弦算法
2.1算法步骤
预处理→文本特征项选择→加权→生成向量空间模型后计算余弦。
2.2步骤简介
2.2.1预处理
预处理主要是进行中文分词和去停用词，分词的开源代码有：ICTCLAS。
然后按照停用词表中的词语将语料中对文本内容识别意义不大但出现频率很高的词、符号、标点及乱码等去掉。如“这，的，和，会，为”等词几乎出现在任何一篇中文文本中，但是它们对这个文本所表达的意思几乎没有任何贡献。使用停用词列表来剔除停用词的过程很简单，就是一个查询过程：对每一个词条，看其是否位于停用词列表中，如果是则将其从词条串中删除。
Ⅱ 文本相似度算法
TF是指归一化后的词频，IDF是指逆文档频率。给定一个文档集合D，有d1,d2,d3,......,dn∈D。文档集合总共包含m个词（注：一般在计算TF−IDF时会去除如“的”这一类的停用词），有w1,w2,w3,......,wm∈W。我们现在以计算词wi在文档dj中的TF−IDF指为例。
TF的计算公式为：
TF=freq(i,j) / maxlen(j)
在这里freq(i,j) 为wi在dj中出现的频率，maxlen(j)为dj长度。
TF只能时描述词在文档中的频率，但假设现在有个词为”我们“，这个词可能在文档集D中每篇文档中都会出现，并且有较高的频率。那么这一类词就不具有很好的区分文档的能力，为了降低这种通用词的作用，引入了IDF。
IDF的表达式如下：
IDF=log(len(D) / n(i))
在这里len(D)表示文档集合D中文档的总数，n(i)表示含有wi这个词的文档的数量。
得到TF和IDF之后，我们将这两个值相乘得到TF−IDF的值：
TF−IDF=TF∗IDF
TF可以计算在一篇文档中词出现的频率，而IDF可以降低一些通用词的作用。因此对于一篇文档我们可以用文档中每个词的TF−IDF组成的向量来表示该文档，再根据余弦相似度这类的方法来计算文档之间的相关性。
BM25算法通常用来做搜索相关性评分的，也是ES中的搜索算法，通常用来计算query和文本集合D中每篇文本之间的相关性。我们用Q表示query，在这里Q一般是一个句子。在这里我们要对Q进行语素解析（一般是分词），在这里以分词为例，我们对Q进行分词，得到q1,q2,......,qt这样一个词序列。给定文本d∈D，现在以计算Q和d之间的分数（相关性），其表达式如下：
Score(Q,d)=∑ti=1wi∗R(qi,d)
上面式子中wi表示qi的权重，R(qi,d)为qi和d的相关性，Score(Q,d)就是每个语素qi和d的相关性的加权和。
wi的计算方法有很多，一般是用IDF来表示的，但这里的IDF计算和上面的有所不同，具体的表达式如下：
wi=IDF(qi)=logN−n(qi)+0.5n(qi)+0.5
上面式子中N表示文本集合中文本的总数量，n(qi)表示包含qi这个词的文本的数量，0.5主要是做平滑处理。
R(qi,d)的计算公式如下：
R(qi,d)=fi∗(k1+1)fi+K∗qfi∗(k2+1)qfi+k2
其中
K=k1∗(1−b+b∗dlavgdl)
上面式子中fi为qi在文本d中出现的频率，qfi为qi在Q中出现的频率，k1,k2,b都是可调节的参数，dl,avgdl分别为文本d的长度和文本集D中所有文本的平均长度。
一般qfi=1，取k2=0，则可以去除后一项，将上面式子改写成：
R(qi,d)=fi∗(k1+1)fi+K
通常设置k1=2,b=0.75。参数b的作用主要是调节文本长度对相关性的影响。
Ⅲ 文本相似度之Sim_hash算法
本文记录的目的是方便自己学习和复习，有误之处请谅解，欢迎指出。
最近项目有用到Sim_hash，做个简单记录。
Sim_hash是Google用来处理大量文本去重的算法，属于 局部敏感哈希（Locality Sensitive Hashing，LSH） ，LSH哈希能够使两篇只有小部分改动的文章编码后哈希值具有相似性，既可用于去重，也可用于计算相似度。对于只有小部分改动的两篇文章，在计算他们之间的相似度时，如果采用md5，两篇文章的md5编码值差异会非常大。但使用局部敏感哈希可以使相似的文章哈希编码后聚集在一起，删除符合阈值条件的文章，达到去重的效果。
一、算法流程
1）分词：对文本进行去停用词、分词，提取n个关键词和关键词的tf-idf权重来表征文章。如下图分词及权重。
2）关键词哈希编码：每个关键词通过hash函数生成固定位数二进制哈希。
3）权重编码：二进制编码中0调整为-1变为权重向量，与权重相乘。
4）权重编码叠加：将所有权重编码纵向求和，得到最终的文章权重。
5）二值化：按正数为1负数为0的规则将文章权重二值化。
6）汉明距离相似度：排除汉明距离小于阈值的文章，一般设置为3。汉明距离计算速度快，思路简单，原理是计算两个二值化编码相同位置处的不同值的个数。
二、Sim_hash整体流程
需求： 来了一个相似文章推荐需求，需要推荐出与文章内容相似的数据，但又不能完全相似。利用目前库中已有的POI标签和POI权重数据，结合simhash算法，计算出每个文章poi_sim_hash，计算距离
数据： 线上拉取10W文章数据
测试结果： 下图为随机抽样的测试结果（第一条为查询数据），基本 符合预期效果 。前期还可以使用 类目和发布时间 进行前置过滤，减少数据量。
Ⅳ 文本比较有哪些算法
用java比较两个文本文件的不同
RangeDifferencer
public class RangeDifferencer {
private static final RangeDifference[] EMPTY_RESULT= new RangeDifference[0];
/* (non Javadoc)
* Cannot be instantiated!
*/
private RangeDifferencer() {
// nothing to do
}
/**
* Finds the differences between two <code>IRangeComparator</code>s.
* The differences are returned as an array of <code>RangeDifference</code>s.
* If no differences are detected an empty array is returned.
*
* @param left the left range comparator
* @param right the right range comparator
* @return an array of range differences, or an empty array if no differences were found
*/
public static RangeDifference[] findDifferences(IRangeComparator left, IRangeComparator right) {
int rightSize= right.getRangeCount();
int leftSize= left.getRangeCount();
//
// Differences matrix:
// only the last d of each diagonal is stored, i.e., lastDiagonal[k] = row of d
//
int diagLen= 2 * Math.max(rightSize, leftSize); // bound on the size of edit script
int maxDiagonal= diagLen;
int lastDiagonal[]= new int[diagLen + 1]; // the row containing the last d
// on diagonal k (lastDiagonal[k] = row)
int origin= diagLen / 2; // origin of diagonal 0
// script corresponding to d[k]
LinkedRangeDifference script[]= new LinkedRangeDifference[diagLen + 1];
int row, col;
// find common prefix
for (row= 0; row < rightSize && row < leftSize && rangesEqual(right, row, left, row) == true;)
row++;
lastDiagonal[origin]= row;
script[origin]= null;
int lower= (row == rightSize) ? origin + 1 : origin - 1;
int upper= (row == leftSize) ? origin - 1 : origin + 1;
if (lower > upper)
return EMPTY_RESULT;
//System.out.println("findDifferences: " + maxDiagonal + " " + lower + " " + upper);
// for each value of the edit distance
for (int d= 1; d <= maxDiagonal; ++d) { // d is the current edit distance
if (right.skipRangeComparison(d, maxDiagonal, left))
return EMPTY_RESULT; // should be something we already found
// for each relevant diagonal (-d, -d+2 ..., d-2, d)
for (int k= lower; k <= upper; k += 2) { // k is the current diagonal
LinkedRangeDifference edit;
if (k == origin - d || k != origin + d && lastDiagonal[k + 1] >= lastDiagonal[k - 1]) {
//
// move down
//
row= lastDiagonal[k + 1] + 1;
edit= new LinkedRangeDifference(script[k + 1], LinkedRangeDifference.DELETE);
} else {
//
// move right
//
row= lastDiagonal[k - 1];
edit= new LinkedRangeDifference(script[k - 1], LinkedRangeDifference.INSERT);
}
col= row + k - origin;
edit.fRightStart= row;
edit.fLeftStart= col;
//Assert.isTrue(k >= 0 && k <= maxDiagonal);
script[k]= edit;
// slide down the diagonal as far as possible
while (row < rightSize && col < leftSize && rangesEqual(right, row, left, col) == true) {
++row;
++col;
}
//Assert.isTrue(k >= 0 && k <= maxDiagonal); // Unreasonable value for diagonal index
lastDiagonal[k]= row;
if (row == rightSize && col == leftSize) {
//showScript(script[k], right, left);
return createDifferencesRanges(script[k]);
}
if (row == rightSize)
lower= k + 2;
if (col == leftSize)
upper= k - 2;
}
--lower;
++upper;
}
// too many differences
//Assert.isTrue(false);
return null;
}
/**
* Finds the differences among two <code>IRangeComparator</code>s.
* In contrast to <code>findDifferences</code>, the result
* contains <code>RangeDifference</code> elements for non-differing ranges too.
*
* @param left the left range comparator
* @param right the right range comparator
* @return an array of range differences
*/
public static RangeDifference[] findRanges(IRangeComparator left, IRangeComparator right) {
RangeDifference[] in= findDifferences(left, right);
List out= new ArrayList();
RangeDifference rd;
int mstart= 0;
int ystart= 0;
for (int i= 0; i < in.length; i++) {
RangeDifference es= in[i];
rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, es.rightStart() - mstart, ystart, es.leftStart() - ystart);
if (rd.maxLength() != 0)
out.add(rd);
out.add(es);
mstart= es.rightEnd();
ystart= es.leftEnd();
}
rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, right.getRangeCount() - mstart, ystart, left.getRangeCount() - ystart);
if (rd.maxLength() > 0)
out.add(rd);
return (RangeDifference[]) out.toArray(EMPTY_RESULT);
}
//---- private methods
/*
* Creates a Vector of DifferencesRanges out of the LinkedRangeDifference.
* It coalesces adjacent changes.
* In addition, indices are changed such that the ranges are 1) open, i.e,
* the end of the range is not included, and 2) are zero based.
*/
private static RangeDifference[] createDifferencesRanges(LinkedRangeDifference start) {
LinkedRangeDifference ep= reverseDifferences(start);
ArrayList result= new ArrayList();
RangeDifference es= null;
while (ep != null) {
es= new RangeDifference(RangeDifference.CHANGE);
if (ep.isInsert()) {
es.fRightStart= ep.fRightStart + 1;
es.fLeftStart= ep.fLeftStart;
RangeDifference b= ep;
do {
ep= ep.getNext();
es.fLeftLength++;
} while (ep != null && ep.isInsert() && ep.fRightStart == b.fRightStart);
} else {
es.fRightStart= ep.fRightStart;
es.fLeftStart= ep.fLeftStart;
RangeDifference a= ep;
//
// deleted lines
//
do {
a= ep;
ep= ep.getNext();
es.fRightLength++;
} while (ep != null && ep.isDelete() && ep.fRightStart == a.fRightStart + 1);
boolean change= (ep != null && ep.isInsert() && ep.fRightStart == a.fRightStart);
if (change) {
RangeDifference b= ep;
//
// replacement lines
//
do {
ep= ep.getNext();
es.fLeftLength++;
} while (ep != null && ep.isInsert() && ep.fRightStart == b.fRightStart);
} else {
es.fLeftLength= 0;
}
es.fLeftStart++; // meaning of range changes from "insert after", to "replace with"
}
//
// the script commands are 1 based, subtract one to make them zero based
//
es.fRightStart--;
es.fLeftStart--;
result.add(es);
}
return (RangeDifference[]) result.toArray(EMPTY_RESULT);
}
/*
* Tests if two ranges are equal
*/
private static boolean rangesEqual(IRangeComparator a, int ai, IRangeComparator b, int bi) {
return a.rangesEqual(ai, b, bi);
}
/*
* Tests whether <code>right</code> and <code>left</code> changed in the same way
*/
private static boolean rangeSpansEqual(IRangeComparator right, int rightStart, int rightLen, IRangeComparator left, int leftStart, int leftLen) {
if (rightLen == leftLen) {
int i= 0;
for (i= 0; i < rightLen; i++) {
if (!rangesEqual(right, rightStart + i, left, leftStart + i))
break;
}
if (i == rightLen)
return true;
}
return false;
}
/*
* Reverses the range differences
*/
private static LinkedRangeDifference reverseDifferences(LinkedRangeDifference start) {
LinkedRangeDifference ep, behind, ahead;
ahead= start;
ep= null;
while (ahead != null) {
behind= ep;
ep= ahead;
ahead= ahead.getNext();
ep.setNext(behind);
}
return ep;
}
}
下面是一段关于如何使用这些类的简单的测试代码
public class RangeDifferencerTest extends TestCase {
InputStream left = null;
InputStream right = null;
/**
* @see junit.framework.TestCase#setUp()
*/
protected void setUp() throws Exception {
String file1 = "d:/temp/1.txt";
String file2 = "d:/temp/2.txt";
left = new FileInputStream(new File(file1));
right = new FileInputStream(new File(file2));
super.setUp();
}
/**
* @see junit.framework.TestCase#tearDown()
*/
protected void tearDown() throws Exception {
left.close();
right.close();
super.tearDown();
}
public static void main(String[] args) {
}
/*
* Test method for 'com.greatroad.smbnm.compare.RangeDifferencer.findDifferences(IRangeComparator, IRangeComparator)'
*/
public void testFindDifferences() {
try {
RangeDifference[] rds = RangeDifferencer.findRanges(new LineComparator(left,"GBK"),new LineComparator(right,"GBK"));
if(rds != null ){
for(int i=0; i<rds.length; i++){
RangeDifference rd = rds[i];
int length = rd.leftLength();
System.out.println(
"kind = "+rd.kind()
+",left["+rd.leftStart()+"-"+rd.leftEnd()
+"],right["+rd.rightStart()+"-"+rd.rightEnd()+"]");
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
}
Ⅳ 经典大规模文本相似识别架构和算法总结
在数据分析和挖掘领域，我们经常需要知道个体间差异大小，从而计算个体相似性。如今互联网内容爆发时代，针对海量文本的相似识别拥有极大需求。本文将通过识别两段文本是否相似，来看看常见的相似算法，及线上落地方案。
一般情况下，我们会将数据进行向量化，将问题抽象为数学问题。比如两个样本X、Y，X=（x1, x2, x3, … xn），Y=（y1, y2, y3, … yn）表示N维向量空间的两个样本，分析差异主要有距离度量和相似度度量。
文本向量化有很多方法，切词、ngram是最常用方法。一般的，分词加预处理能更好的表达语义，我们通过预处理，过滤掉无效字符及停用词。
对"组装衣柜，刚买不久" 和 "组装鞋柜，全新"向量化
距离（Distance）用于衡量样本在空间上的距离，距离越大，差异越大。
欧氏距离是最容易直观理解的距离度量方法，我们认知中两个点在空间中的距离就是欧氏距离。扩展到高维空间中，欧式距离的计算公式如图1：
图1 欧氏距离欧式距离因为计算是基于各维度特征的绝对数值，所以欧氏度量需要保证各维度指标在相同的刻度级别，当不同维度单位不同将使距离失去意义。
余弦相似度用向量空间中两个向量夹角余弦值作为衡量两个个体间差异的大小。余弦相似度更加注重两个向量在方向上的差异，而非距离或长度。公式如图2：
图2 余弦相似度
通过三维坐标系可以很直观的看到两者的区别，如图3所示：
图3 欧式距离和余弦相似度区别
欧氏距离和余弦相似度各自的计算方式和衡量特征，分别适用于不同的数据分析模型：欧式距离适应于需要从维度大小中体现差异的场景，余弦相似度更多的是方向上的差异。如果我们分词后，将每个词赋予一定的权重，那么可以使用欧氏距离。更多情况下，我们采用余弦相似度来计算两文本之间相似度。
上面的相似算法，适用于小量样本，两两计算。那么在大规模样本下，给定新的样本怎么找到相似的样本呢？
下面我们将引入 SimHash 算法。
SimHash是Google在2007年发表的一种指纹生成算法或者叫指纹提取算法（如图4），其主要思想是降维。
图4 SimHash算法
算法主要原理分为这几步：
大家可能存在疑问：生成一串二进制需要这么麻烦吗？直接用hash函数生成0和1的不是更简单。比如：md5和hashcode等。
可以看得出来，相似两个文本，simhash局部变化而普通的hashcode却天壤之别。文本转换为SimHash后，我们通过海明距离（Hamming distance）计算两个SimHash是否相似。
Google的论文给出的数据中，64位的签名，在汉明距离为3的情况下， 可认为两篇文档是相似。
为了查询相似，我们依然需要两两比较。但汉明距离算法给了我们降维的捷径。
可以证明，汉明距离小于3情况下，将hash code等分为4份，则必有一份完全相同。
基于上述特点，我们设计一个MySQL存储索引方案来实现，如图5所示。
图5 MySQL存储索引方案
Ⅵ 文本算法是什么意思
在文本信息空间内寻找任何两个最相关的文本信息，并将之简并成一个文本信息，从而实现信息数量的收缩。
简并算法的实现通过比较整个信息空间内的所有文本的相关性（相识性），得到相互之间的相关性后两两(注)进行配对。配对的要求是这两个文本信息的相关性最大，例如A 找到了文档B，那么B 也一定找到最相关的文档就是A 。
注，某些情况A 最相近的文档是C ，那么B 而B 最相关的文档也是C ，存在一种情况，A,B,C 三者之间自恰，就是构成空间信息最近的一个三角形。
得到了最相似文档后，将只进行平均化，或者简单的迭加。
信息空间中独立信息的数量会减少到原来的一半以下，然后重复实现1 的过程，在进行兼并。
信息最后简并到唯一的一个信息，就是整个信息文本的平均值。
画出信息树的结构，就能够根据要进行规模不同大小的聚类进行自动聚类了。
Ⅶ 文本、语音相似度算法
前段时间公司项目用到了语音识别,图像识别,视频识别等,其实不能说是识别,应该说是相似度对比吧,毕竟相似度对比还上升不了到识别哈,等以后有了更深的理解再来讨论修改下!这次就当做一个总结吧!
其实它的原理和视频图像相似度算法类似，将一系列的向量,特征,权重,进行合并,然后降维降到一维,其实这个算法也就是采用降维技术,将所有的特征都用一个唯一标识来表示.然后这个标识是经过这个算法内部的计算,再利用海明距离计算相似度，视频和图片是经过汉明距离计算的
文本我们是采用simhash算法：
1.我们给文本里面的词进行分词,我们是用ik算法,这个算法就是while循环,读取一行,然后调用ik智能分词的类,智能去切割里面的分词;
2.根据里面的词频,simhash算法会加一个权重,当然,得词频达到多少个的时候才会有有权重,这也是它的缺点,一般文本数据较少的时候,他是不准确的,一般数据量在500+;算法内部的话会将一系列的向量,特征,权重,进行合并,然后降维降到一维,其实这个算法也就是采用降维技术,将所有的特征都用一个唯一标识来表示.然后这个标识是经过这个算法内部的计算,然后得到的一个指纹签名；
3.然后对比两个文本的相似度就是将两个指纹签名进行海明距离计算,如果海明距离<8(根据业务和场景去判断这个值，8是建议，参考)的话,表示两个相似,小于3的话.表示两个文本重复.
simhash算法我们还可以做语音相似度,它的基本原理就是根据傅里叶变换处理得到声波的形状。
语音的坡度如果向上我们就用1表示,向下我们就用0表示,这样的话,我们也可以用二进制码去描述一首歌曲.得到一个唯一的指纹签名,对比两个音频的相似度就是将两个指纹签名进行海明距离计算<8的话,我们就默认两个音频相似.
总结：都是把特征降到一维，然后采用海明距离计算。计算的值小于多少时，就当做是相似。我这边讲的太浅了，实在领悟有限，时间有限，触摸不深，等下次有新的领悟再来补充！