PCFG句法分析之CYK算法

CYK算法

原来使用堆栈和线图的浪费空间，还比较慢。那我们肯定想办法优化啊。感谢John Cocke, Daniel Younger and Tadao Kasami三位大神设计出来的CYK算法！！！

其实说白了，就是动态规划。
由于我们的所有产生式要么就是$A\to BC$要么就是$A\to \alpha$，并且某一个单词只能作为一颗CFG产生树的一个叶子节点而存在（这块其实就是之后CYK算法的精髓）

伪代码

# 输入：带分析的词序列words和PCFG规则集R
# 输出：最有可能的句法结构树
def Probabilistic_CYK(word, R):    
for j in range(1, len(words)):        
	for all in {A | A -> words[i] in R}:            
		table[j-1, j, A] = P(A -> word[i])        
	for i in range(j-2, 0):            
		for k in range(i+1, j-1):
			# 下面一步是精髓，为什么是[i,k]和[k,j]的乘积？上面已经提示过答案了
			for all in {A | A -> BC in R, and table[i, k, B] > 0 and table[j, k, C] > 0}:                    
				if table[i, j, A] < P(A -> BC)*table[i, k, B]*table[j, k, C]:                        
					table[i, j, A] < P(A -> BC)*table[i, k, B]*table[j, k, C]                        
					back_trace[i, j, A] = {k, B, C}    
return BUILD_TREE 

我们使用上课的时候老师讲的例子：

计算到最后，我们就能求出一个局部的最优解（一些潜在的最佳方案可能被丢弃了）

参考：哈工大自然语言PPT