面向数据的句法分析消歧  

Disambiguation for Data-Oriented Parsing

作　　者：张玥杰[1] 张涛[2] 朱靖波[3] 姚天顺[3] 

机构地区：[1]复旦大学计算机科学与工程系 [2]上海财经大学信息管理与工程学院,上海200433 [3]东北大学信息科学与工程学院,沈阳110006

出　　处：《计算机科学》2006年第3期174-178,共5页Computer Science

基　　金：本文得到国家自然科学基金(编号:60203010;70501018与605333100);上海财经大学"211工程"(2004年)资助

摘　　要：面向数据的分析技术(Data-Oriented Parsing,DOP)是一种概率分析策略,其概率模型的主要目的在于为一个给定的句子找到最可能的分析,即分析消歧。实际上,有关算法计算复杂度的大量研究证明,该类消歧问题属于NP-完全问题。因此,为有效实现最可能的分析,国外学者提出许多近似分析算法。本文主要论述在 DOP 框架中,基于 Monte Carlo 方法找到最可能分析的近似分析算法,并说明该方法可在合理的算法时间代价范围内实现,而且在统计上受控,以确保所获得的近似解确实对应着分析消歧后的精确解。Data-Oriented Parsing（DOP）technique is a kind of probabilistic parsing strategy. The main goal of DOP model is to find the most probable parse for a given input sentence, that is, parse disambiguation. In fact, it is proved through a lot of research work about algorithm computation complexity that this kind of disambiguation problem belongs to the class of NP-Complete problem. So in order to implement the most probable parse efficiently, some researchers have proposed many approximation parsing algorithms. This paper mainly presents a kind of approximation parsing algorithm based on Monte Carlo method in DOP framework, which can be implemented at reasonable（i, e. polynomial）algorithmic cost. And at the same time, under statistical control, it is guaranteed that an obtained approximate solution indeed corresponds to an exact solution of the problem after disambiguation.

关 键 词：面向数据的句法分析 随机树替换文法 消歧 MONTE CARLO方法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] TP391.2[自动化与计算机技术—计算机科学与技术]