Disambiguation for Data-Oriented Parsing
Yue Zhang · 2006
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 be- longs to the class of NP-Complete problem.So in order to implement the most probable parse efficiently,some re- searchers 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.pol- ynomial)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.