CYK.tar.gz_CYK

算法说明： CYK算法与概率CYK算法的实现： CYK算法是一种基于动态规划的填表算法，整个填表过程需要O(n的三次方)。 初始条件： 对于输入的每个单词，即终结符ai,1<i<=N (N是单词的个数),推导出A->ai的唯一途径就是变元A。由于采用的是内部算法，故将这些满足条件的变元依次填入初始矩阵的对角线上(i,i)上，这样初始化工作就完成了。 递归过程： 内部算法只需要依次填充整个矩阵的右下三角，即整个矩阵的一半，对于下三角中间的某一个节点A(i,j),i<j;则需要考虑所有满足 A->BC, B和C均是之前已填充的节点，设为(m,n),(o,p);则节点A满足i=m,j=p,(j-i+1)=(n-m+1)+(p-o+1);(第三个式子中括内的内容代表单词的个数);有了这三个式子，就可以找到满足条件的格子B和C,找出是否存在满足条件的生成式。这便是递推过程。 结束条件： 对于输入的字符串，最后判断是否存在一颗递推树是很好判断的，只需要在生成的矩阵表中找到(1, length)的位置(length代表串中词的个数),判断它存的变元是否是开始变元即可。若是，则存在至少一棵递推树。