文档相似度比较

实验报告实验题目：相似度。

实验要求：判断两个文档的相似度。

实验代码：

#include

#include

#define MAXSIZE 50

#define N 500

typedef struct{

char e[MAXSIZE][10];

int front;

int rear;

}QUEUE;

typedef struct{

char a[20];

}STRING;

void InitQueue(QUEUE *pQ){

pQ->front=pQ->rear=0;

}

void ClearQueue(QUEUE *pQ){

pQ->front=pQ->rear=0;

}

int QueueLength(QUEUE Q){

return((Q.rear+MAXSIZE-Q.front)%MAXSIZE);

}

void EnQ(QUEUE *pQ,char *x){

int i=0;

while(x[i]!='\0'){

pQ->e[pQ->rear][i]=x[i];

i++;

}

pQ->e[pQ->rear][i]='\0';

pQ->rear=(pQ->rear+1)%MAXSIZE;

}

STRING DeQ(QUEUE *pQ){

STRING s;

int i=0;

while(pQ->e[pQ->front][i]!='\0'){

s.a[i]=pQ->e[pQ->front][i];

i++;

}

s.a[i]='\0';

pQ->front=(pQ->front+1)%MAXSIZE;

return s;

}

int compare(STRING a,STRING b){

int i=0;

for(i=0;a.a[i]!='\0'&&b.a[i]!='\0';i++){

if(a.a[i]!=b.a[i]) return 0;

}

if(a.a[i]=='\0'&&b.a[i]=='\0') return 1;

return 0;

}

float GetMaxsub(float a,float b,float c){

if(a>=b){

if(a>=c) return a;

return c;

}

if(b>=c) return b;

return c;

}

float GetMaxpart(QUEUE Q1,QUEUE Q2){

int Q1len,Q2len;

QUEUE Q_1,Q_2;

Q_1=Q1;

Q_2=Q2;

float sub,sub1,sub2,sub3;

if(QueueLength(Q1)==0||QueueLength(Q2)==0) return 0;

if(compare(DeQ(&Q1),DeQ(&Q2))){

sub=GetMaxpart(Q1,Q2);

sub=sub++;

return sub;

}

sub1=GetMaxpart(Q_1,Q2);

sub2=GetMaxpart(Q1,Q_2);

sub3=GetMaxpart(Q1,Q2);

sub=GetMaxsub(sub1,sub2,sub3);

return sub;

}

int getsentence(FILE *fp,QUEUE *pQ){

char c,a[20];

int i=0;

while((c=fgetc(fp))!=EOF){

if(c!='.'&&c!=','){

if(c!=' '){

a[i]=c;

i++;

}

else{

a[i]='\0';

EnQ(pQ,a);

i=0;

a[0]='\0';

}

}

else{

a[i]='\0';

EnQ(pQ,a);

i=0;

a[0]='\0';

return 1;

}

}

return 0;

}

float sim(FILE *fp1,FILE *fp2){

QUEUE Q1,Q2;

int i=0,k=0,m1,m2,a[N];

float b[N],sum=0;

InitQueue(&Q1);

InitQueue(&Q2);

do{

m1=getsentence(fp1,&Q1);

m2=getsentence(fp2,&Q2);

if(m1&&m2){

a[k]=QueueLength(Q1);

b[k]=GetMaxpart(Q1,Q2);

k++;

}

ClearQueue(&Q1);

ClearQueue(&Q2);

}while(m1&&m2);

for(i=0;i

printf("b[%d]=%f\n",i,b[i]);

printf("a[%d]=%d\n",i,a[i]);

printf("sub[%d]=%f\n",i,b[i]/a[i]);

sum+=b[i]/a[i];

}

return sum/k;

}

main(){

FILE *fp1,*fp2;

float sub;

if((fp1=fopen("D1.txt","r"))==NULL){

printf("cannot open file\n");

exit(0);

}

if((fp2=fopen("D2.txt","r"))==NULL){

printf("cannot open file\n");

exit(0);

}

sub=sim(fp1,fp2);

printf("sub=%f\n",sub);

fclose(fp1);

fclose(fp2);

}

算法流程：1、判断两个文档第一个词是否相同。若是，则判读除去第一个次以后两文档的相似度，最后加上第一个词，得出总相似度。

2、否则，分别判断除去第一个文档的第一个词、第二个文档的第一个词、两个文档的第一个词三个相似度，取最大值得到总相似度。

实验结果：

1、文档1：this is a text book.and i love you too.

2、文档2：this is a english book.but i love me too.

3、相似度：

实验总结：1、运用递归解决去头或去尾的相似问题。

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。 然后按照停用词表中的词语将语料中对文本内容识别意义不大但出

现频率很高的词、符号、标点及乱码等去掉。如“这，的，和，会，为”等词几乎出现在任何一篇中文文本中，但是它们对这个文本所表达的意思几乎没有任何贡献。使用停用词列表来剔除停用词的过程很简单，就是一个查询过程：对每一个词条，看其是否位于停用词列表中，如果是则将其从词条串中删除。 图2.2.1-1中文文本相似度算法预处理流程 2.2.2文本特征项选择与加权 过滤掉常用副词、助词等频度高的词之后，根据剩下词的频度确定若干关键词。频度计算参照TF公式。 加权是针对每个关键词对文本特征的体现效果大小不同而设置的机制，权值计算参照IDF公式。 2.2.3向量空间模型VSM及余弦计算 向量空间模型的基本思想是把文档简化为以特征项（关键词）的权重为分量的N维向量表示。

这个模型假设词与词间不相关（这个前提造成这个模型无法进行语义相关的判断，向量空间模型的缺点在于关键词之间的线性无关的假说前提），用向量来表示文本，从而简化了文本中的关键词之间的复杂关系，文档用十分简单的向量表示，使得模型具备了可计算性。 在向量空间模型中，文本泛指各种机器可读的记录。 用D（Document）表示文本，特征项（Term，用t表示）指出现在文档D中且能够代表该文档内容的基本语言单位，主要是由词或者短语构成，文本可以用特征项集表示为D（T1，T2，…，Tn），其中Tk是特征项，要求满足1<=k<=N。 下面是向量空间模型（特指权值向量空间）的解释。 假设一篇文档中有a、b、c、d四个特征项，那么这篇文档就可以表示为 D（a，b，c，d） 对于其它要与之比较的文本，也将遵从这个特征项顺序。对含有n 个特征项的文本而言，通常会给每个特征项赋予一定的权重表示其重要程度，即 D＝D（T1，W1；T2，W2；…，Tn，Wn） 简记为 D＝D（W1，W2，…，Wn） 我们把它叫做文本D的权值向量表示，其中Wk是Tk的权重，

计算文本相似度几种最常用的方法，并比较它们之间的性能 编者按：本文作者为Yves Peirsman，是NLP领域的专家。在这篇博文中，作者比较了各种计算句子相似度的方法，并了解它们是如何操作的。词嵌入（word embeddings）已经在自然语言处理领域广泛使用，它可以让我们轻易地计算两个词语之间的语义相似性，或者找出与目标词语最相似的词语。然而，人们关注更多的是两个句子或者短文之间的相似度。如果你对代码感兴趣，文中附有讲解细节的Jupyter Notebook地址。以下是论智的编译。 许多NLP应用需要计算两段短文之间的相似性。例如，搜索引擎需要建模，估计一份文本与提问问题之间的关联度，其中涉及到的并不只是看文字是否有重叠。与之相似的，类似Quora之类的问答网站也有这项需求，他们需要判断某一问题是否之前已出现过。要判断这类的文本相似性，首先要对两个短文本进行embedding，然后计算二者之间的余弦相似度（cosine similarity）。尽管word2vec和GloVe等词嵌入已经成为寻找单词间语义相似度的标准方法，但是对于句子嵌入应如何被计算仍存在不同的声音。接下来，我们将回顾一下几种最常用的方法，并比较它们之间的性能。 数据 我们将在两个被广泛使用的数据集上测试所有相似度计算方法，同时还与人类的判断作对比。两个数据集分别是： STS基准收集了2012年至2017年国际语义评测SemEval中所有的英语数据 SICK数据库包含了10000对英语句子，其中的标签说明了它们之间的语义关联和逻辑关系 下面的表格是STS数据集中的几个例子。可以看到，两句话之间的语义关系通常非常微小。例如第四个例子： A man is playing a harp. A man is playing a keyboard.

文本相似度算法 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。 然后按照停用词表中的词语将语料中对文本内容识别意义不大但出现频率很高的词、符号、标点及乱码等去掉。如“这，的，和，会，为”等词几乎出现在任何一篇中文文本中，但是它们对这个文本所表达的意思几乎没有任何贡献。使用停用词列表来剔除停用词的过程很简单，就是一个查询过程：对每一个词条，看其是否位于停用词列表中，如果是则将其从词条串中删除。

图2.2.1-1中文文本相似度算法预处理流程 2.2.2文本特征项选择与加权 过滤掉常用副词、助词等频度高的词之后，根据剩下词的频度确定若干关键词。频度计算参照TF公式。 加权是针对每个关键词对文本特征的体现效果大小不同而设置的机制，权值计算参照IDF公式。 2.2.3向量空间模型VSM及余弦计算 向量空间模型的基本思想是把文档简化为以特征项（关键词）的权重为分量的N维向量表示。 这个模型假设词与词间不相关（这个前提造成这个模型无法进行语义相关的判断，向量空间模型的缺点在于关键词之间的线性无关的假说前提），用向量来表示文本，从而简化了文本中的关键词之间的复杂关系，文档用十分简单的向量表示，使得模型具备了可计算性。 在向量空间模型中，文本泛指各种机器可读的记录。 用D（Document）表示文本，特征项（Term，用t表示）指出现在文档D中且能够代表该文档内容的基本语言单位，主要是由词或者短语构成，文本可以用特征项集表示为D（T1，T2，…，Tn），其中Tk 是特征项，要求满足1<=k<=N。 下面是向量空间模型（特指权值向量空间）的解释。 假设一篇文档中有a、b、c、d四个特征项，那么这篇文档就可以表示为 D（a，b，c，d） 对于其它要与之比较的文本，也将遵从这个特征项顺序。对含有n个特征项的文本而言，通常会给每个特征项赋予一定的权重表示其重要程度，即 D＝D（T1，W1；T2，W2；…，Tn，Wn）

1文本相似度算法基本原理 1.1文本相似度含义 文本相似度来自于相似度概念，相似度问题是一个最基本的问题，是信息科学中绕不过去的概念，在不同的应用方向其含义有所不同，但基本的内涵表示了一个信息结构与另外一个信息结构的一致程度，从某个角度研究时特征量之间的距离大小[10]。比如，在机器翻译方面是指词这个基本单位的可替代性，在信息检索方面是指检索结果与检索内容的一致性，在自动问答方面是指搜索的结果与输入的问题的匹配程度。这充分表明文本相似度研究和应用领域十分广泛，所表达的含义也十分不同。从本文研究的角度来看，文本相似度可以描述为：有A、B两个对象，二者之间的公共区域越多、共性越大，则相似程度越高；若二者没有关联关系，则相似程度低。在文本相似度研究方面，一个层次是研究文档中以篇章、句子、词语衡量相似程度，这不同层次衡量算法也不同，研究的标准和依据也不同，算法的复杂程度也不同。从这个意义上，可以运用在新闻领域对新闻稿件进行归档，按照新闻的领域分门别类的存放在一起；也可以运用在信息检索进行信息查询，作为一个文本与另一个文本之间相似程度测量的基本方法。 1.2文本相似度计算方法分类 当前研究文本相似度都是以计算机作为计算工具，即利用计算机算法对文本进行分类，在各个领域应用十分广泛，比如包括网页文本分类、数据智能挖掘、信息识别检索、自动问答系统、论文查重分析和机器自主学习等领域，其中起最关键作用的是文本相似度计算算法，在信息检索、数据挖掘、机器翻译、文档复制检测等领域有着广泛的应用。 特别是随着智能算法、深度学习的发展，文本相似度计算方法已经逐渐不再是基于关键词匹配的传统方法，而转向深度学习，目前结合向量表示的深度学习使用较多，因此度量文本相似度从方法论和算法设计全局的角度看，一是基于关键词匹配的传统方法，如N-gram相似度；二是将文本映射到向量空间，再利用余弦相似度等方法，三是运用机器学习算法的深度学习的方法，如基于用户点击数据的深度学习语义匹配模型DSSM，基于卷积神经网络的ConvNet和LSTM 等方法。 本文研究的重点是对电子作业检查等各类电子文档对比，在对两个电子文档是否相同，相似比例为多少这一问题探究中需要比较文档的相似度，而文档的相似度又可分成段落相似度、句子相似度来进行考虑，所以课题的关键是如何定义

文本相似度的设计与实现 摘要：本文主要设计并实现了一个文本相似度系统，该系统主要功能计算文档之间的相似度，通过使用向量空间模型(VSM, Vector Space Model)及余弦相似度计算公式计算文档之间的相似度，数据预处理过程中加入word2vec模型进行语义扩充，从而能够匹配到更多相关文档。 1.向量空间模型 向量空间模型(VSM, Vector Space Model)由Salton等人于20世纪70年代年提出[1,2]。向量空间模型的主要思想是将文本内容的处理简化为向量空间中的向量运算，这样将空间上的相似度转化为语义上的相似度。当文档被表示为文档空间的向量时，便可通过计算向量之间的相似性来度量文档间的相似性。文本处理中最常用的相似性度量方式是余弦距离。 向量空间模型的基本思想： 给定一篇文档D=D(T1,T2,…T i,…,T n)，若T i在文档中既可以重复出现又存在先后次序，因此分析起来会较为困难。针对上述情况，暂不考虑T i的顺序，并要求T i互异，此时可将T1,T2,…T i,…,T n看作n维坐标，每一维对应相应值W i，因此D(W1,W2,…,W i,…,W n)便可以看作一个n维向量。 例如：有一篇文档D={大家好，才是真的好}，首先进行分词后转换为D={大家/好/才是/真的/好}，之后提取出公因词D={大家，好，才是，真的}，最后通过向量空间模型将文档转换为对应的向量D={1，2，1，1}。 向量空间模型只是将文档转换为方便计算的格式，若进行相似度计算，还需使用相似度计算公式进行计算。本文使用余弦相似度计算公式。 2.余弦相似度 余弦相似度计算公式广泛应用于文本数据之间的相似度计算过程中。其数学表达如下： 计算过程如下： 例如，有2个文档D1={大家好}，D2={才是真的好}，首先将D1、D2分词后，D1={大家/好}，D2={才是/真的/好}，其次提取出公因词D={大家，好，才是，真的}，然后通过向量空间模型转换成向量表达，D1={1，1，0，0}，D2={0，1，1，1}，最后进行相似度计算 Score== 3.文本相似度系统 本文主要使用向量空间模型及余弦相似度距离公式进行文本相似度计算任务，系统的基本架构如下图1所示：

几种相似度计算方法作对比 句子相似度的计算在自然语言处理具有很重要的地位,如基于实例的机器翻译(Example Based Ma-chine Translation,EBMT)、自动问答技术、句子模糊匹配等.通过对术语之间的语义相似度计算,能够为术语语义识别[1]、术语聚类[2]、文本聚类[3]、本体自动匹配[4]等多项任务的开展提供重要支持。在已有的术语相似度计算方法中,基于搜索引擎的术语相似度算法以其计算 简便、计算性能较高、不受特定领域语料库规模和质量制约等优点而越来越受到重视[1]。 相似度计算方法总述： 1 《向量空间模型信息检索技术讨论》，刘斌，陈桦发表于计算机学报，2007 相似度S(Similarity)：指两个文档内容相关程度的大小，当文档以向量来表示时，可 以使用向量文档向量间的距离来衡量，一般使用内积或夹角0的余弦来计算，两者夹角越小说明似度越高。由于查询也可以在同一空间里表示为一个查询向量(见图1)，可以通过相似度计算公式计算出每个档向量与查询向量的相似度，排序这个结果后与设立的阈值进行比较。如果大于阈值则页面与查询相关，保留该页面查询结果；如果小于则不相关，过滤此页。这 样就可以控制查询结果的数量，加快查询速度。 2 《相似度计算方法综述》 相似度计算用于衡量对象之间的相似程度，在数据挖掘、自然语言处理中是一个基础性计算。其中的关键技术主要是两个部分，对象的特征表示，特征集合之间的相似关系。在信息检索、网页判重、推荐系统等，都涉及到对象之间或者对象和对象集合的相似性的计算。而针对不同的应用场景，受限于数据规模、时空开销等的限制，相似度计算方法的选择又会有所区别和不同。下面章节会针对不同特点的应用，进行一些常用的相似度计算方法进行介绍。 内积表示法： 1 《基于语义理解的文本相似度算法》，金博，史彦君发表于大连理工大学学报，2007 在中文信息处理中,文本相似度的计算广泛应用于信息检索、机器翻译、自动问答系统、文本挖掘等领域,是一个非常基础而关键的问题,长期以来一直是人们研究的热点和难点。计算机对于中文的处理相对于对于西文的处理存在更大的难度,集中体现在对文本分词的处理上。分词是中文文本相似度计算的基础和前提,采用高效的分词算法能够极大地提高文本相似度计算结果的准确性。本文在对常用的中文分词算法分析比较的基础上,提出了一种改进的正向最大匹配切分(MM)算法及歧义消除策略,对分词词典的建立方式、分词步骤及歧义字段的处理提出了新的改进方法,提高了分词的完整性和准确性。随后分析比较了现有的文本相似度计算方法,利用基于向量空间模型的TF-IDF方法结合前面提出的分词算法,给出了中文文本分词及相似度计算的计算机系统实现过程,并以科技文本为例进行了测试,对所用方

文本相似度计算系统 摘要 在中文信息处理中，文本相似度的计算广泛应用于信息检索、机器翻译、自动问答系统、文本挖掘等领域，是一个非常基础而关键的问题，长期以来一直是人们研究的热点和难点。本次毕设的设计目标就是用两种方法来实现文本相似度的计算。 本文采用传统的设计方法，第一种是余弦算法。余弦算法是一种易于理解且结果易于观察的算法。通过余弦算法可以快捷的计算出文本间相似度，并通过余弦算法的结果（0、1之间）判断出相似度的大小。由于余弦计算是在空间向量模型的基础上，所以说要想用余弦算法来完成本次系统，那么必须要将文本转化成空间向量模型。而完成空间向量模型的转换则要用到加权。在空间向量模型实现之前，必须要进行文本的去停用词处理和特征选择的处理。第二种算法是BM25算法，本文将采用最基础的循环来完成，目的是观察余弦算法中使用倒排索引效率是否提高有多大提高。 本次文本相似度计算系统的主要工作是去除停用词、文本特征选择、加权，在加权之后用余弦算法计算文本的相似度。在文本特征选择之后用BM25计算相似度。由于为了使系统的效率提高，在程序设计中应用了大量的容器知识以及内积、倒排算法。 关键词：文本相似度；余弦；BM25；容器

Text Similarity Algorithm Research Abstract In Chinese information processing，text similarity computation is widely used in the area of information retrieval，machine translation,automatic question—answering，text mining and etc．It is a very essential and important issue that people study as a hotspot and difficulty for a long time．Currently，most text similarity algorithms are based on vector space model(VSM)．However,these methods will cause problems of high dimension and sparseness．Moreover，these methods do not effectively solve natural language problems existed in text data．These natural language problems are synonym and polyseme．These problems sidturb the efficiency and accuracy of text similarity algorithms and make the performance of text similarity computation decline． This paper uses a new thought which gets semantic simirality computation into traditional text similarity computation to prove the performance of text similarity algorithms．This paper deeply discusses the existing text similarity algorithms and samentic text computation and gives a Chinese text similarity algorithm which is based on semantic similarity．There is an online information management system which is used to manage students’graduate design papers．Those papers ale used to calculate similarity by that the algorithm to validate that algorithm． This text similarity computing system's main job is to stop word removal, text feature selection, weighting, after weighting using cosine algorithm to calculate the

相似度计算方面 Jaccard相似度：集合之间的Jaccard相似度等于交集大小与并集大小的比例。适合的应用包括文档文本相似度以及顾客购物习惯的相似度计算等。 Shingling：k-shingle是指文档中连续出现的任意k个字符。如果将文档表示成其k-shingle集合，那么就可以基于集合之间的Jaccard相似度来计算文档之间的文本相似度。有时，将shingle哈希成更短的位串非常有用，可以基于这些哈希值的集合来表示文档。 最小哈希：集合上的最小哈希函数基于全集上的排序转换来定义。给定任意一个排列转换，集合的最小哈希值为在排列转换次序下出现的第一个集合元素。 最小哈希签名：可以选出多个排列转换，然后在每个排列转换下计算集合的最小哈希值，这些最小哈希值序列构成集合的最小哈希签名。给定两个集合，产生相同哈希值的排列转换所占的期望比率正好等于集合之间的Jaccard相似度。 高效最小哈希：由于实际不可能产生随机的排列转换，因此通常会通过下列方法模拟一个排列转换：选择一个随机哈希函数，利用该函数对集合中所有的元素进行哈希操作，其中得到的最小值看成是集合的最小哈希值。 签名的局部敏感哈希：该技术可以允许我们避免计算所有集合对或其最小哈希签名对之间的相似度。给定集合的签名，我们可以将它们划分成行条，然后仅仅计算至少有一个行条相等的集合对之间的相似度。通过合理选择行条大小，可以消除不满足相似度阈值的大部分集合对之间的比较。 向量空间距离方面 欧式距离：n维空间下的欧式距离，是两个点在各维上差值的平方和的算数平方根。适合欧式空间的另一个距离是曼哈顿距离，指两个点各维度的差的绝对值之和。 Jaccard距离：1减去Jaccard相似度也是一个距离测度。 余弦距离：向量空间下两个向量的夹角大小。 编辑距离：该距离测度应用于字符串，指的是通过需要的插入、删除操作将一个字符串处理成另一个字符串的操作次数。编辑距离还可以通过两个字符串长度之和减去两者最长公共子序列长度的两倍来计算。 海明距离：应用于向量空间。两个向量之间的海明距离计算的是它们之间不相同的位置个数。 索引辅助方面 字符索引：如果将集合表示成字符串，且需要达到的相似度阈值接近1。那么就可以将每个字符串按照其头部的一小部分字母建立索引。需要索引的前缀的长度大概等于整个字符串的长度乘以给定的最大的Jaccard距离。 位置索引：我们不仅可以给出索引字符串前缀中的字符，也可以索引其在前缀中的位置。如果两个字符串共有的一个字符并不出现在双方的第一个位置，那么我们就知道要么存在某些前面的字