?

Log in

No account? Create an account

Agenda的作用

以前一直不理解CFG解析中的Agenda的作用,今天在重构项目时才突然悟到:原来Agenda的存在是Dynamic Programming必不可少的一环。有了Agenda的存在,在其他的规则向Chart添加Edges之后,是可以以O(1)的复杂度处理Fundamental Rules的,而如果没有了Agenda,只考Chart本身做Memorilation的话,复杂度是O(n),如此一来整个解析过程需要O(n^4)的时间复杂度,而不是O(n^3)。NLTK中的CFG解析器,复杂度其实就是O(n^4)的。

Comments