PCFG句法分析之CYK算法_在给定一个pcfg规则集后

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 
1
2
3
4
5
6
7
8
9
10
11
12
13

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

图中，我们可以发现，根据CYK算法，我们先填充$[j-1,j]$位置上的概率（我们一定能知到这个位置上的概率，因为产生式$A\to \alpha$），然后我们对于表中的第$j$列，从$[j-2,j]$一直计算到$[0,j]$，我们记$i=j-2to0$每一个$[i,j]$我们都是使用$[i,k]$和$[k,j]$来计算（这里面就会用到每个单词只能作为一个叶子节点的性质了）。

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

参考：哈工大自然语言PPT