PCFG与CYK算法实战：Python实现句法分析的5个关键步骤

在自然语言处理领域，句法分析是理解句子结构的基础技术。本文将带你从零实现一个基于概率上下文无关文法（PCFG）和CYK算法的完整句法分析系统，通过5个关键步骤构建语法树。

1. 理解PCFG与CYK算法基础

概率上下文无关文法（PCFG）是传统CFG的扩展，为每个产生式规则赋予概率值。一个PCFG可以表示为五元组：

• 终结符集合（X）：句子中的实际词汇
• 非终结符集合（V）：语法类别如NP、VP等
• 开始符号（S）：通常是"S"表示句子
• 产生式规则（R）：形如A→BC或A→a的规则
• 概率（P）：每条规则对应的概率值

CYK算法是一种基于动态规划的自底向上分析方法，其核心思想是通过填表记录子问题的解。算法要求文法必须符合乔姆斯基范式（CNF），即每条规则只能是：

A → B C # 两个非终结符 A → a # 或一个终结符

关键数据结构选择：

# 使用字典嵌套存储概率表和回溯表 probs = {} # 键：(i,j)位置，值：{非终结符:最大概率} pi = {} # 键：(i,j)位置，值：{非终结符:最佳分割点}

2. 构建PCFG语法规则库

实际应用中，我们需要从树库（如Penn Treebank）中提取规则并计算概率。这里展示一个简化版的规则示例：

Python实现规则加载：

class PCFG: def __init__(self, grammar_file): self.rules = defaultdict(list) self.rhs_to_rules = defaultdict(list) with open(grammar_file) as f: for line in f: lhs, rhs, prob = line.strip().split('\t') self.rules[lhs].append((tuple(rhs.split()), float(prob))) self.rhs_to_rules[tuple(rhs.split())].append((lhs, rhs, float(prob)))

3. 实现CYK算法核心

CYK算法通过动态规划填表，分为初始化、填表和回溯三个阶段。

初始化阶段

def __init__(self, grammar): self.grammar = grammar def parse_with_backpointers(self, tokens): n = len(tokens) # 初始化表格 pi = {(i,j): {} for i in range(n+1) for j in range(i+1, n+1)} probs = {(i,j): {} for i in range(n+1) for j in range(i+1, n+1)} # 填充对角线（长度为1的子串） for i, word in enumerate(tokens): for rhs, rules in self.grammar.rhs_to_rules.items(): if len(rhs) == 1 and rhs[0] == word: for lhs, _, prob in rules: pi[(i,i+1)][lhs] = word probs[(i,i+1)][lhs] = math.log(prob)

动态规划填表

# 处理长度>1的子串 for length in range(2, n+1): for i in range(n-length+1): j = i + length for k in range(i+1, j): # 所有可能的分割点 for B in pi[(i,k)]: for C in pi[(k,j)]: for rhs, rules in self.grammar.rhs_to_rules.items(): if rhs == (B, C): for lhs, _, rule_prob in rules: new_prob = math.log(rule_prob) + probs[(i,k)][B] + probs[(k,j)][C] if lhs in pi[(i,j)]: if new_prob > probs[(i,j)][lhs]: pi[(i,j)][lhs] = ((B,i,k), (C,k,j)) probs[(i,j)][lhs] = new_prob else: pi[(i,j)][lhs] = ((B,i,k), (C,k,j)) probs[(i,j)][lhs] = new_prob

4. 回溯构建语法树

填表完成后，我们需要从表格右上角回溯构建完整的语法树结构：

def get_tree(self, chart, i, j, nt): if isinstance(chart[(i,j)][nt], str): # 终结符 return (nt, chart[(i,j)][nt]) left, split, right = chart[(i,j)][nt] left_tree = self.get_tree(chart, left[1], left[2], left[0]) right_tree = self.get_tree(chart, right[1], right[2], right[0]) return (nt, left_tree, right_tree)

示例输出：

('S', ('NP', ('DT', 'the'), ('NN', 'dog')), ('VP', ('VB', 'chased'), ('NP', ('DT', 'the'), ('NN', 'cat'))))

5. 优化与调试技巧

实际实现中需要考虑以下几个关键点：

1. 对数概率处理：

   # 使用对数概率避免下溢 prob = math.log(rule_prob) + probs[(i,k)][B] + probs[(k,j)][C]

2. 性能优化：

   • 预处理文法规则，建立快速查找的数据结构
   • 使用memoization缓存中间结果

3. 调试建议：

   # 打印中间表格状态 def print_table(table, tokens): for i in range(len(tokens)): for j in range(i+1, len(tokens)+1): print(f"({i},{j}): {table[(i,j)]}")

4. 处理未知词：

   # 对未登录词添加默认规则 if word not in known_words: pi[(i,i+1)]['NN'] = word probs[(i,i+1)]['NN'] = math.log(0.001) # 小概率

通过这5个步骤，我们实现了一个完整的PCFG-CYK句法分析系统。实际应用中，可以进一步扩展为词汇化PCFG或加入平滑技术处理数据稀疏问题。这个基础实现已经能够处理简单的句子结构分析，为更复杂的NLP任务奠定基础。