注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

金融IT小鸿的博客

致力于金融IT行业

 
 
 

日志

 
 
关于我

Organize the world's information I care about and share it with other people! Change the Financial Industry through Information Technology! 爱互联网,爱金融, 爱分享,爱运动, 也爱偶尔胡思乱想! 我是金融IT小鸿

网易考拉推荐

用ActionScript 3解决两个英文句子相似度的问题  

2010-12-05 23:09:19|  分类: AS & Flex |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       最近需要利用两个英文句子相似度来对一个英文填空题判分,就是看学生的写的答案与标准答案之间的相似度来给出一个分数。刚开始我想到利用我以前看到过的一个不错的算法来近似解决一下,就是一个用ActionScript 3实现的求两个字符串的最大公共子串。具体见这里。大体思路是(翻译自源网站):

       首先需要一个矩阵来存放两个字符串,以“sick”和“brick”为例,如下图所示:

用ActionScript 3解决两个英文句子相似度的问题 - IT小鸿 - IT小鸿的博客

       首先将矩阵用0填满,然后按照行列循环遍历整个矩阵,寻找一样的字母。如果找到一样的字母,其对应位置的值等于1加上其左上方位置对应的值。最后我们将选择矩阵里的最大数值作为最大公共子串的长度,沿着数值往回找就能找到最大公共子串。如果最大数值不唯一,则有多个最大公共子串。源代码可以参考来源网站

       然后我的问题是要对比两个句子,就对这个算法稍作处理就可以为我所用了。思路还是一样,只是把对应的字母变成了单词。当然首先要把输入字符串处理一下,我是约定单词之间用空格分开。源代码见这里

       这种方法其实还是很有问题的,一般会少给分数。比如标准答案为“I am a student”,学生作答是“I are a student”。这样匹配的单词个数就是2,其实3才是合理的。

       随后我请教了一个自然语言处理专业的同学,他说要是解决两个句子相似性的问题,只从句子结构上(先不谈语义,因为还存在同义词的问题)说,有一个比较好的解决办法,就是求编辑距离(Levenshtein distance)。这也是一个比较成熟的算法,编辑距离就是通过增、删、改三种方式最少几步能把一个字符串变成另一个字符串。随后搜了搜,还真找到了这个算法的ActionScript 3实现。更巧的是还是写刚才那个算法的哥们发表的,具体见这里。同样先介绍其大体思路(翻译自来源网站):

       给定两个分别有n个和m个字母组成的字符串,我们按照下图所示方式创建一个(m+1)*(n+1)的矩阵(原文中是m*n,应该是作者笔误):
用ActionScript 3解决两个英文句子相似度的问题 - IT小鸿 - IT小鸿的博客
 
     这个就是初始矩阵,与字符串紧挨着单元格里数值为对应字母在字符串中所处位置,其余元素为0。然后需要遍历右下角这个m*n的全零矩阵,修改其中的数值。第x行,第y列的元素值取以下三个值的最小值:

  • 其上边的元素的值 + 1(即第x-1行,第y列)
  • 其左边的元素的值 + 1(即第x行,第y-1列)
  • 其左上角的元素的值 + d (即第x-1行,第y-1列)

      如果第一个字符串的第y个字母与第二个字符串的第x个字母相同,则d = 0;如果不同,则d = 1;

     在这种情况下,矩阵的第一行应该如下图所示:
 
用ActionScript 3解决两个英文句子相似度的问题 - IT小鸿 - IT小鸿的博客

      红色的值取决与2(其左边元素的值 + 1)、2(其上边元素的值 + 1)、1(其左上边元素的值 + 1,因为T和F不同)中的最小值。
      绿色的值取决于2(其左边元素的值 + 1)、3(其上边元素的值 + 1)、2(其左上边元素的值 + 1,因为O和F不同)中的最小值。

       将这个规则应用到整个矩阵,得到如下图所示结果:

用ActionScript 3解决两个英文句子相似度的问题 - IT小鸿 - IT小鸿的博客
 
       右下角红色的数值即为编辑距离。源代码参考来源网站

       我依照同样的方式改写了这个算法,来判断两个句子的编辑距离。源代码见这里。这样就可以找到两个句子之间的编辑距离,但是评分方案还是要自己制定。

       如果学生答案与标准答案的长度相同,那么可以使用句子长度减去编辑距离,再除以句子长度得到相似度。但是存在两个句子长度不同的情况,那还要分两种情况:1)学生答案长度小于标准答案,用标准答案的长度减去编辑距离,再除以标准答案的长度也可以得到相似度;2)学生答案长度大于标准答案长度,那比较宽松一点的判分方法是,用学生答案长度减去编辑距离,再除以标准答案长度。也就是说多写了不扣分。比较严格一点可以在此基础上扣掉相应的多写的分数。

       这个评分方案也就是一个比较粗浅的方法,没有考虑同义词问题,而且代码运行效率也不一定很高。我只比较佩服这两个算法的精妙,所以在这里分享出来。其实网上还有一个用ActionScript 3写的关于String的常用工具包,里面也实现了编辑距离的求解。工具包见这里

Update:再附上编辑距离(Levenshtein Distance)的标准算法描述和另外几种语言的实现代码(Java,C++,VB,JavaScript):算法描述和前三种语言的实现     JavaScript的实现
  评论这张
 
阅读(490)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017