思享工具箱

【转】计算文档相似度（英文）

摘要：
已经有很多不同的方法来计算这些值，这些值叫做（词组）权重。通过文档相似度理论的假设，比较每个文档向量和原始查询向量之间的角度偏差，使得在文档搜索关键词的关联规则是能够计算的。向量的模通过下面的公式计算：由于这个模型所考虑的所有向量都是严格非负的，如果其余弦值为零，则表示查询向量和文档向量是正交的，即不符合，即两篇文档的相似度为0%。

转自：http://blog.chinaunix.net/uid-26548237-id-3541783.html

1、向量空间模型
向量空间模型作为向量的标识符，是一个用来表示文本文件的代数模型。它应用于信息过滤、信息检索、索引以及相关规则。
文档和问题都用向量来表示。
【转】计算文档相似度（英文）第1张
每一维都相当于一个独立的词组。如果这个术语出现在文档中，那它在向量中的值就非零。已经有很多不同的方法来计算这些值，这些值叫做（词组）权重。其中一种广为人知的算法就是tf_idf权重。我们是根据应用来定义词组的。典型的词组就是一个单一词、关键词、或者较长的短语。如果字被选为词组，那么向量的维数就是出现在词汇表中不同字的个数。向量运算能通过查询来比较各文档。

通过文档相似度理论的假设，比较每个文档向量和原始查询向量（两个向量的类型是相同的）之间的角度偏差，使得在文档搜索关键词的关联规则是能够计算的。实际上，计算向量之间夹角的余弦比直接计算夹角本身要简单。
【转】计算文档相似度（英文）第2张
其中d2*q是文档向量（即下图中的d2）和查询向量（即下图中的q）的点乘；分母分别为两个向量的模。向量的模通过下面的公式计算：
【转】计算文档相似度（英文）第3张
由于这个模型所考虑的所有向量都是严格非负的，如果其余弦值为零，则表示查询向量和文档向量是正交的，即不符合（换句话说，就是该检索词在文档中没有找到），即两篇文档的相似度为0%。

下面是一个tf-idf权重的例子。
【转】计算文档相似度（英文）第4张

优点：
相对于标准的布尔数学模型，向量空间模型具有如下优点：
1、基于线性代数的简单模型；
2、词组的权重不是二元的；
3、允许计算文档和索引之间的连续相似程度；
4、允许其根据可能的相关性来进行文件排序；
5、允许局部匹配；
局限：
1、不适用于较长的文件，因为它的相似度值不理想；
2、检索词组必须与文件中出现的词组精确匹配；
3、语义敏感度不佳，具有相同的语境但使用不同的词组的文件不能被关联起来；
4、词组在文档中出现的顺序在向量中间无法表示；
5、假定词组在统计上是独立的；
6、权重是直观上获得的而不够正式；
2、向量空间模型的使用
下面是利用向量空间模型来计算文件的相似度。以上面讲诉的余弦值Cosine为例，进行实现。
实现中的权重直接使用的是词出现的频率，另外，这里比较的是英文的相似度。

  1. #include<iostream>
  2. #include<map>
  3. #include<sys/stat.h>
  4. #include<cmath>
  5. using namespace std;
  7. #defineERROR-1
  8. #define OK 0
  9. #define DEBUG
  11. //用于去除文本中的无关紧要的词
  12. //constchar delim[]=" .,:;`/\"+i-_(){}[]<>*&^%$#@!?~/|\\=1234567890\t\n";
  13. const char delim[] = ".,:;'`/\"+-_(){}[]<>*&^%$#@!?~/|\\=1234567890 \t\n";
  15. char*strtolower(char*word)
  16. {
  17. char*s;
  19. for(s=word;*s;s++)
  20. {
  21. *s=tolower(*s);
  22. }
  23. return word;
  24. }
  26. intReadFile(char*text_name,map<string,int>&word_count)
  27. {
  28. char*str;
  29. char*word;
  30. char*file;
  31. struct stat sb;
  33. FILE*fp=fopen(text_name,"r");
  35. if(fp==NULL)
  36. {
  37. returnERROR;
  38. }
  40. if(stat(text_name,&sb))
  41. {
  42. returnERROR;
  43. }
  45. file=(char*)malloc(sb.st_size);
  46. if(file==NULL)
  47. {
  48. fclose(fp);
  49. returnERROR;
  50. }
  51. fread(file,sizeof(char),sb.st_size,fp);
  53. word=strtok(file,delim);
  55. while(word!=NULL)
  56. {
  57. //delete the length of word<=1
  58. if(strlen(word)<=1)
  59. {
  60. word=strtok(NULL,delim);
  61. continue;
  62. }
  64. str=strtolower(strdup(word));
  65. stringtmp=str;
  66. word_count[tmp]++;
  68. word=strtok(NULL,delim);
  69. }
  70. }
  72. intmain(intargc,char**argv)
  73. {
  74. char*text_name_one="./big.txt";
  75. //char*text_name_one="./1.txt";
  76. char*text_name_two="./big.txt";
  77. //char*text_name_two="./2.txt";
  79. map<string,int>word_count_one;
  80. map<string,int>word_count_two;
  82. double multi_one=0.0;
  83. double multi_two=0.0;
  84. double multi_third=0.0;
  86. if(ReadFile(text_name_one,word_count_one)==ERROR)
  87. {
  88. cout<<"ReadFile() error."<<endl;
  89. returnERROR;
  90. }
  92. #ifdef DEBUG
  93. map<string,int>::iterator map_first=word_count_one.begin();
  94. for(;map_first!=word_count_one.end();map_first++)
  95. {
  96. cout<<map_first->first<<" "<<map_first->second<<endl;
  97. }
  98. #endif
  100. if(ReadFile(text_name_two,word_count_two)==ERROR)
  101. {
  102. cout<<"ReadFile() error."<<endl;
  103. returnERROR;
  104. }
  106. #ifdef DEBUG
  107. map<string,int>::iterator map_second=word_count_two.begin();
  108. for(;map_second!=word_count_two.end();map_second++)
  109. {
  110. cout<<map_second->first<<" "<<map_second->second<<endl;
  111. }
  112. #endif
  114. map<string,int>::iterator map_one=word_count_one.begin();
  115. map<string,int>::iterator map_tmp;
  116. for(;map_one!=word_count_one.end();map_one++)
  117. {
  118. map_tmp=word_count_two.find(map_one->first);
  119. if(map_tmp==word_count_two.end())
  120. {
  121. multi_two+=map_one->second*map_one->second;
  122. continue;
  123. }
  124. multi_one+=map_one->second*map_tmp->second;
  125. multi_two+=map_one->second*map_one->second;
  126. multi_third+=map_tmp->second*map_tmp->second;
  127. word_count_two.erase(map_one->first);//从2中删除1中具有的
  128. }
  130. //检查2中是否仍然有元素
  131. for(map_tmp=word_count_two.begin();map_tmp!=word_count_two.end();map_tmp++)
  132. {
  133. multi_third+=map_tmp->second*map_tmp->second;
  134. }
  135. multi_two=sqrt(multi_two);
  136. multi_third=sqrt(multi_third);
  138. double result=multi_one/(multi_two*multi_third);
  139. cout<<"相似度为: "<<result*100<<"%"<<endl;
  140. return 0;
  141. }


下面进行测试。
第一、进行检测两个相同的英文文本，文本链接为http://norvig.com/big.txt
【转】计算文档相似度（英文）第5张
给出了文本中词的部分统计，可以看到，两个相同文本的相似度为100%。
第二、 文本1内容：......this is one! 文本2的内容：()()()......this is two
【转】计算文档相似度（英文）第6张
运行结果与实际手算的结果相同，两个文本的相似度为66.6667%。
以上只是简单的进行两个英文文本的相似度计算，只是在词条的层次上进行计算，并没有涉及到语义，所以，相对比较简单。
我对这方面非常感兴趣，还会继续学习其他相关的内容。
理论知识引自：http://zh.wikipedia.org/wiki/%E5%90%91%E9%87%8F%E7%A9%BA%E9%96%93%E6%A8%A1%E5%9E%8B

标签：#char#向量的模 | 浏览：195 | 发布日期：

免责声明：文章转载自《【转】计算文档相似度（英文）》仅用于学习参考。如对内容有疑问，请及时联系本站处理。

上篇github-----文件项目的推拉二式UI自动化测试篇 ：Selenium2(Webdriver)&amp;amp;TestNG自动化测试环境搭建下篇

宿迁高防，2C2G15M，22元/月；香港BGP，2C5G5M，25元/月 雨云优惠码：MjYwNzM=

相关文章

C语言：字符数组 + 字符串指针

字符数组 C语言中没有特定的字符串类型，通常是将字符串放在一个字符数组中。 字符串指针 除了字符数组，C语言还支持另外一种表示字符串的方法，就是直接使用一个指针指向字符串。 char *str = "leetcode"; char *str; str = "leetcode"; 字符串中的所有字符在内存中是连续存放的，str指向的是字符串的第0个字符，即...

[转]NSString/NSMutableString字符串处理和常用代码 (实例)

Objective-C 中核心处理字符串的类是 NSString 与 NSMutableString ，这两个类最大的区别就是NSString 创建赋值以后该字符串的内容与长度不能在动态的更改，除非重新给这个字符串赋值。而NSMutableString 创建赋值以后可以动态在该字符串上更改内容与长度。  NSString 常用方法总结 +(id)str...

java中unicode和中文相互转换

public class Test{    public static void main(String[] args)    {        String s = "中转地设置导出模板";        String tt = gbEncoding(s);    }    public static String gbEncoding(final Str...

IDA，很好很强大

IDA，这款可以把程序反编译成C语言的东西。。 我用我们老师C++课上留的一道小学奥赛水平的弱智题的程序代码为例，先用MinGW编译，结果用IDA反编译出了几千个函数，全都是sub_加编号的名称，每一个都很短，变量名都是v1、v2等等的，一点也看不懂，我甚至连主函数在哪里都找不到。 然后又用VS2010编译，再反编译，令我大开眼界，函数名、变量名全能被...

FFmpeg在Linux下编译使用

1.FFmpeg编译 1.1.安装yasm 这里我是直接通过ubuntu包安装的，当然也可以通过编译源码来安装。 sudo apt-get install yasm 1.2.下载FFmpeg git clone https://git.ffmpeg.org/ffmpeg.git 1.3.配置、编译FFMPEG ./configure --prefix=ho...

Oracle中的日期和字符串互相转换

转载出处：http://blog.sina.com.cn/s/blog_44a005380100k6rv.html TO_DATE格式(以时间:2007-11-02   13:45:25为例)            Year:              yy two digits 两位年                显示值:07         yyy...

最新文章

随机推荐

思享工具箱导航