如何从CYK算法中提取解析概率及最可能的解析树？

我来给你详细拆解一下这两个问题哈：

一、提取每个解析对应的概率 #

概率CYK算法的核心是跟踪推导过程中的概率乘积，要拿到每个解析的概率，关键是在填充CYK表的时候不丢弃任何可能的推导路径，具体步骤是这样的：

• 初始化阶段：对于输入句子的每个位置i（对应终结符a_i），单元格[i,i]里会记录所有能推导出a_i的非终结符X，以及对应的产生式概率P(X→a_i)——这就是该非终结符对应单个字符解析的基础概率。
• 表填充阶段：处理长度l≥2的子串时，对每个单元格[i,j]，遍历所有可能的拆分点k（从i到j-1），以及所有形如X→YZ的产生式。对于每个组合，计算概率：P(X→YZ) * P(Y在[i,k]的概率) * P(Z在[k+1,j]的概率)。如果要保留所有解析路径，就把每个(X,Y,Z,k)组合对应的概率都存储在单元格里，而不是只保留最大值。
• 最终汇总：整个句子的所有解析，对应起始符号S在[1,n]（n是句子长度）单元格里的所有推导路径。每个解析的概率，就是这条路径上所有产生式概率的乘积——比如从S拆分到Y和Z，Y又拆分到A和B，直到所有叶子都是终结符，把这些产生式的概率连乘起来，就是这个解析树的概率。

二、获取最可能的解析树 #

这其实是Viterbi-CYK算法的工作，核心是在填充表的时候记录最大概率的回溯路径，具体操作如下：

• 带回溯的表填充：在填充每个单元格[i,j]的非终结符X时，除了存储能得到X的最大概率，还要额外记录这个最大概率是怎么来的——也就是对应的拆分点k，以及产生式X→YZ里的Y和Z（即Y在[i,k]、Z在[k+1,j]的非终结符）。
• 回溯构建解析树：从起始符号S所在的[1,n]单元格开始，根据记录的回溯信息，找到拆分点k和对应的Y、Z；接着递归处理Y所在的[1,k]单元格，以及Z所在的[k+1,n]单元格；一直回溯到单个终结符的单元格（也就是叶子节点）。把这些回溯得到的产生式按层级组合起来，就得到了概率最大的解析树。

举个简单例子：如果S的最大概率来自拆分k=2，对应产生式S→AB，那我们就去看A在[1,2]的回溯信息，B在[3,n]的回溯信息，依次拆解，直到每个叶子都是输入的终结符，这样就拼出了最可能的树结构。

内容的提问来源于stack exchange，提问作者blue-sky