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

罗维的博客

{ 关注机器学习、计算广告、自然语言处理、大规模数据处理等 }

 
 
 
 
 

日志

 
 

三种Chart Parsing算法  

2010-05-17 20:50:58|  分类: 机器学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
前面介绍了Chart Parsing算法和他在句法解析中的作用。Chart是对算法特点的一套形象的比喻。在
用图(Graph)来表示句子词之间的点(Vertex)时,如果把每一条边(Edge)以长短区分覆盖的单词数量打印出来的话,输出的结果就是一个图表。

最近先后做了Bottom-Up, Top-Down,和Earley三种Chart Parsing算法的实现,觉得有必要把三种算法的原理简单概括一下,以免日久遗忘。由于算法涉及自然语言处理和编译器实现。感兴趣的人不多,所以很多许要的基本概念不太解释。这里做的记录期望是对还在为阅读和理解相关的论文而烦恼的同行。如果基本概念还不了解的话,可以先花一点时间查阅一些资料。

Fundamental Rule

不 论是Bottom-Up, Top-Down还是Earley算法。都要用到Fundamental Rule(Earley中叫Completor Rule).Fundamentals所做的基本工作有:对于每一个Active Edge,如果在他结束处有一个In-Active Edge正好开始。且这个Edge的LHS正好是这个Active Edge的RHS的下一个匹配对象,则视为匹配成功。这时要做的工作有创建一个新的边,其LHS为前者的LHS,其起始点(start)为前者的起始点,其结束点(end)为后者的结束点,Dot为前者的Dot+1,并且将这个边添加到Chart中。

如<1,2, NP,[Det],[N]> + <2, 3, N,...> = <1,3, NP, [Det, N] [] ...>

Top-Down Parsing

自顶向下的分析方法的思路在于,确定一个目标LHS,通常是代表整句的一个Production的LHS(如‘S’),将所有以其做为LHS的Production都添加一条Edge。然后在这些新添加的边中,以第一个RHS作为目标LHS,再次从Productions中查找,直到无法添加新的边为止。

Bottom-Up Parsing

自下向上的分析方法的思路是,从每个从0(句首)开始,并且已经完成的边(Inactive Edge)开始,对每一条第一个RHS和已完成的边的LHS相等的Production,都根据其添加一个新的边。依次结束。(CYK算法是其中一种)

Earley Parsing

Earley 算法和Top-Down Parsing很相似,区别是从不自上向下添加包含终结符的Production作为新的Edge,而是从第一个终结符开始,从左到由依次添加相应的边,每一次添加前都确保已有的路径都已经尝试过,再处理下一个单词。
  评论这张
 
阅读(1517)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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