基于扩展Viterbi路径的概率Earley算法

Probabilistic Earley Algorithm Based on Extended Viterbi Path

概率Earley句法分析算法采用Viterbi路径构造输入序列的句法树,由于文法限制,存在空树问题。提出了扩展启始状态、省略未覆盖句首和补充未覆盖子树等方法来对Viterbi路径进行扩展,解决了绝大多数空树问题,并有效提高了Earley算法的整体性能。

Probabilistic Earley algorithm applies Viterbi path to construct parse trees for input sequences,but the grammar limits often result in many empty trees.This paper exploited optional start states,new sequential beginnings and more subtrees to extend the traditional Viterbi path,removed almost all empty trees,and improved the general parsing performance of Earley algorithm.