Python实战：用CKY算法解析句子结构（附可视化代码）

当我们在处理自然语言时，句法分析就像给句子做X光扫描，让我们能看清其内部结构。CKY算法作为自然语言处理领域的经典工具，能够将看似杂乱无章的词语序列转化为清晰的树状结构。本文将从零开始，带你用Python实现这个强大的算法，并通过直观的可视化展示其工作原理。

1. CKY算法基础与准备工作

CKY算法全称Cocke-Kasami-Younger算法，是一种基于动态规划的句法分析方法。它要求语法必须符合乔姆斯基范式(CNF)，这种范式将语法规则简化为两种基本形式：要么是一个非终结符生成两个非终结符(A→BC)，要么是一个非终结符生成一个终结符(A→w)。

安装必要的Python库：

pip install torch matplotlib numpy

核心数据结构准备：

import torch
import numpy as np
import matplotlib.pyplot as plt

# 示例句子和得分矩阵
words = ['The', 'cat', 'sat', 'on', 'the', 'mat']
score_matrix = torch.tensor([
    [-999, 1, -1, 1, -1, 1, -1],
    [-999, -999, 1, -1, 1, -1, 1],
    [-999, -999, -999, 1, -1, 1, -1],
    [-999, -999, -999, -999, 1, -1, 1],
    [-999, -999, -999, -999, -999, 1, -1],
    [-999, -999, -999, -999, -999, -999, 1],
    [-999, -999, -999, -999, -999, -999, -999]
]).unsqueeze(0)

mask = torch.triu(torch.ones_like(score_matrix), diagonal=1)

2. CKY算法核心实现

CKY算法的核心在于动态规划表的构建，它通过自底向上的方式填充一个三角矩阵，记录所有可能的子结构及其得分。

算法实现关键函数：

def stripe(x, n, w, offset=(0, 0), dim=1):
    """高效提取对角线带状数据的辅助函数"""
    x, seq_len = x.contiguous(), x.size(1)
    stride, numel = list(x.stride()), x[0, 0].numel()
    stride[0] = (seq_len + 1) * numel
    stride[1] = (1 if dim == 1 else seq_len) * numel
    return x.as_strided(
        size=(n, w, *x.shape[2:]),
        stride=stride,
        storage_offset=(offset[0]*seq_len + offset[1])*numel
    )

def cky(scores, mask):
    """CKY算法主函数"""
    lens = mask[:, 0].sum(-1).long()
    scores = scores.permute(1, 2, 0)
    seq_len, seq_len, batch_size = scores.shape
    
    s = scores.new_zeros(seq_len, seq_len, batch_size)
    p = scores.new_zeros(seq_len, seq_len, batch_size).long()
    
    for w in range(1, seq_len):
        n = seq_len - w
        starts = p.new_tensor(range(n)).unsqueeze(0)
        
        if w == 1:
            s.diagonal(w).copy_(scores.diagonal(w))
            continue
            
        s_span = stripe(s, n, w-1, (0,1)) + stripe(s, n, w-1, (1,w), 0)
        s_span = s_span.permute(2, 0, 1)
        s_span, p_span = s_span.max(-1)
        
        s.diagonal(w).copy_(s_span + scores.diagonal(w))
        p.diagonal(w).copy_(p_span + starts + 1)
    
    def backtrack(p, i, j):
        if j == i + 1:
            return [(i, j)]
        split = p[i][j]
        ltree = backtrack(p, i, split)
        rtree = backtrack(p, split, j)
        return [(i, j)] + ltree + rtree
    
    p = p.permute(2, 0, 1).tolist()
    trees = [backtrack(p[i], 0, length) for i, length in enumerate(lens.tolist())]
    return trees

3. 解析树可视化实现

理解算法的最好方式是看到它的输出结果。我们将实现一个树形可视化功能，直观展示句子的结构分析。

树结构可视化代码：

def build_parent_child(tree_nodes):
    """构建父节点到子节点的映射关系"""
    sorted_nodes = sorted(tree_nodes, key=lambda node: node[1]-node[0], reverse=True)
    parent_child = {}
    for parent in sorted_nodes:
        pi, pj = parent
        children = []
        for child in sorted_nodes:
            ci, cj = child
            if (child != parent) and (pi <= ci < cj <= pj):
                has_mid = any(
                    (mid != parent and mid != child) and 
                    (pi <= mid[0] <= ci < cj <= mid[1] <= pj)
                    for mid in sorted_nodes
                )
                if not has_mid:
                    children.append(child)
        children.sort(key=lambda x: x[0])
        parent_child[parent] = children
    return parent_child

def plot_cky_tree(words, tree_nodes, save_path=None):
    """绘制CKY解析树"""
    parent_child = build_parent_child(tree_nodes)
    root = next(node for node in tree_nodes if node == (0, len(words)))
    
    def calculate_coords(root, parent_child):
        """计算节点坐标"""
        coords = {}
        def dfs(node, level):
            children = parent_child[node]
            y = -level * 1.5
            if not children:
                x = node[0] * 2
            else:
                child_coords = [dfs(child, level+1) for child in children]
                x = np.mean([child_x for child_x, _ in child_coords])
            coords[node] = (x, y)
            return (x, y)
        dfs(root, 0)
        return coords
    
    node_coords = calculate_coords(root, parent_child)
    
    plt.figure(figsize=(12, 8))
    ax = plt.gca()
    ax.set_aspect('equal')
    ax.axis('off')
    
    for node, (x, y) in node_coords.items():
        ni, nj = node
        span_len = nj - ni
        
        if span_len == 1:
            circle = plt.Circle((x, y), 0.4, color='#4CAF50', alpha=0.7)
            ax.add_patch(circle)
            ax.text(x, y, words[ni], ha='center', va='center', 
                   fontsize=10, fontweight='bold')
        else:
            rect = plt.Rectangle((x-0.6, y-0.3), 1.2, 0.6, 
                               color='#FF9800', alpha=0.7)
            ax.add_patch(rect)
            ax.text(x, y, f"TOP\n({ni},{nj})", ha='center', va='center', 
                   fontsize=9, fontweight='bold')
        
        for child in parent_child[node]:
            child_x, child_y = node_coords[child]
            ax.plot([x, child_x], [y, child_y], color='#333333', linewidth=1.5)
    
    all_x = [x for x, y in node_coords.values()]
    all_y = [y for x, y in node_coords.values()]
    x_margin = (max(all_x)-min(all_x))*0.2 if len(all_x)>1 else 1
    y_margin = (min(all_y)-max(all_y))*0.2 if len(all_y)>1 else 1
    
    ax.set_xlim(min(all_x)-x_margin, max(all_x)+x_margin)
    ax.set_ylim(min(all_y)-y_margin, max(all_y)+y_margin)
    
    plt.title('CKY Parsing Tree Visualization', fontsize=12, pad=20)
    if save_path:
        plt.savefig(save_path, dpi=300, bbox_inches='tight')
    plt.show()

4. 完整示例与结果分析

让我们用一个完整的例子来演示CKY算法的实际应用。

运行示例：

# 准备输入数据
words = ['The', 'cat', 'sat', 'on', 'the', 'mat']
score = torch.Tensor([
    [-999, 1, -1, 1, -1, 1, -1],
    [-999, -999, 1, -1, 1, -1, 1],
    [-999, -999, -999, 1, -1, 1, -1],
    [-999, -999, -999, -999, 1, -1, 1],
    [-999, -999, -999, -999, -999, 1, -1],
    [-999, -999, -999, -999, -999, -999, 1],
    [-999, -999, -999, -999, -999, -999, -999]
]).unsqueeze(0)

mask = torch.triu(torch.ones_like(score), diagonal=1)

# 运行CKY算法
trees = cky(score, mask)
print("解析树节点:", trees[0])

# 可视化结果
plot_cky_tree(words, trees[0], save_path="cky_tree_example.png")

输出结果分析：

1. 算法首先识别出基本的名词短语(NP)和动词短语(VP)
2. 然后组合这些短语形成更大的句法结构
3. 最终生成覆盖整个句子的完整解析树

常见问题排查：

• 如果得分矩阵设置不当，可能导致无法找到有效的解析树
• 确保mask矩阵正确反映了句子的实际长度
• 可视化时如果节点重叠，可以调整坐标计算中的间距参数

5. 性能优化与扩展应用

虽然基础版本的CKY算法已经能工作，但在处理长句子时可能会遇到性能问题。下面介绍几种优化方法。

优化技巧：

1. 批量处理：利用PyTorch的并行计算能力，同时处理多个句子

# 批量得分矩阵示例
batch_scores = torch.stack([score_matrix]*3)  # 同时处理3个句子
batch_mask = torch.stack([mask]*3)
batch_trees = cky(batch_scores, batch_mask)

2. 记忆化搜索：缓存中间结果，避免重复计算

from functools import lru_cache

@lru_cache(maxsize=None)
def memoized_backtrack(p, i, j):
    """带缓存的回溯函数"""
    if j == i + 1:
        return [(i, j)]
    split = p[i][j]
    ltree = memoized_backtrack(p, i, split)
    rtree = memoized_backtrack(p, split, j)
    return [(i, j)] + ltree + rtree

3. 近似算法：当处理非常长的句子时，可以考虑使用束搜索(beam search)等近似方法

扩展应用场景：

• 机器翻译中的句法引导
• 文本摘要中的关键结构提取
• 问答系统中的语义理解

在实际项目中，我发现将CKY算法与神经网络结合往往能取得更好的效果。例如，可以用神经网络来预测得分矩阵，然后用CKY算法进行精确的句法分析。这种混合方法结合了神经网络的表示能力和传统算法的精确性。