E.2 PCFG 的概率 CKY 句法分析

PCFG 的句法分析问题，是为给定句子 $S$ 生成最可能分析 $\hat T$：

计算最可能分析的算法，是标准句法分析算法的简单扩展。现代概率句法分析器大多以 Ney（1991）首次描述的概率 CKY 算法为基础。概率 CKY 假设 PCFG 采用 Chomsky 范式（CNF）。回忆一下，在 CNF 中，每条规则右部必须展开为两个非终结符或一个终结符，即形如 $A\to BC$ 或 $A\to w$。

CKY 算法把每个句子表示为词间带有索引的序列。因此，例句

（E.15） Book the flight through Houston.

假定词间有如下索引：

（E.16） 0 Book 1 the 2 flight 3 through 4 Houston 5

利用这些索引，CKY 分析树中的每个成分都编码在二维矩阵中。对于长度为 $n$ 的句子和包含 $V$ 个非终结符的语法，使用 $(n+1)\times(n+1)$ 矩阵的上三角部分。标准 CKY 中，每个单元格 $table[i,j]$ 含有一张成分列表，这些成分可以跨越从 $i$ 到 $j$ 的词序列。

对概率 CKY 来说，更简单的理解是把每个单元格中的成分视为最大长度为 $V$ 的第三个维度。这个维度对应能放入该单元格的每个非终结符；单元格的值不再是成分列表，而是该非终结符/成分的概率。总之，这个 $(n+1)\times(n+1)\times V$ 矩阵中的每个单元格 $[i,j,A]$，表示跨越输入位置 $i$ 到 $j$、类型为 $A$ 的成分的概率。

图 E.3 给出概率 CKY 算法。

函数 PROBABILISTIC-CKY(words, grammar) 返回最可能分析及其概率
  对 j ← 1 到 LENGTH(words)：
    对所有 {A | A → words[j] ∈ grammar}：
      table[j−1,j,A] ← P(A → words[j])
    对 i ← j−2 递减到 0：
      对 k ← i+1 到 j−1：
        对所有 {A | A → B C ∈ grammar，
                     table[i,k,B] > 0 且 table[k,j,C] > 0}：
          若 table[i,j,A] < P(A → B C) × table[i,k,B] × table[k,j,C]：
            table[i,j,A] ← P(A → B C) × table[i,k,B] × table[k,j,C]
            back[i,j,A] ← {k,B,C}
  返回 BUILD-TREE(back[0,LENGTH(words),S]), table[0,LENGTH(words),S]

图 E.3 给定 CNF 形式的 PCFG，寻找词串最大概率分析的概率 CKY 算法。back 是用于恢复最佳分析的回指针数组；构树函数留给读者练习。

与基本 CKY 算法一样，概率 CKY 要求语法采用 Chomsky 范式。把概率语法转换成 CNF 时，还必须修改概率，使每棵分析树在新 CNF 语法下的概率保持不变。练习 E.2 要求修改第 19 章的 CNF 转换算法，使其正确处理规则概率。

实践中通常采用能直接处理一元产生式的广义 CKY 算法。回忆相关练习要求对 CKY 作这一修改；练习 E.3 要求把它扩展到概率 CKY。

下面用一个已经采用 CNF 的微型语法观察概率 CKY 图表：

图 E.4 展示在该语法下对句子“The flight includes a meal”进行概率 CKY 分析的最初几步。

图 E.4 概率 CKY 矩阵的开始部分。图表其余部分留作练习 E.4。