基于CKY算法回溯指针生成未知层级嵌套列表的所有组合

Alright, let's tackle this problem head-on—you need to expand those CKY backpointers into full, nested parse trees, right? The core challenge is recursively exploring every possible split path in the backpointer dictionary until we hit terminal nodes, then assembling each unique path into a proper nested structure.

First, Let's Clarify the Backpointer Structure #

Your backpointer is a dictionary where each key is a tuple (i, j, nt) representing a non-terminal nt spanning positions i to j. The value is a set of splits, each split being (k, left_nt, right_nt)—meaning the non-terminal can be split into left_nt (covering i to k) and right_nt (covering k to j).

The Recursive Approach #

We'll use a recursive function that, given a (i, j, nt) triple, returns all possible nested subtrees for that node. Here's the step-by-step logic:

1. Base Case: If the triple isn't in the backpointer, it's a terminal token (a leaf node). Return a list containing just that triple wrapped in a list (to keep nesting consistent across all nodes).
2. Recursive Case: For each split option of the current node:
   • Recursively generate all possible left subtrees from the left split component.
   • Recursively generate all possible right subtrees from the right split component.
   • Combine every left subtree with every right subtree, wrapping them with the current node to form a complete subtree.
3. Collect all these combined subtrees and return them as the result for the current node.

Python Implementation #

Here's a working implementation tailored to your backpointer data:

def generate_all_parse_trees(i, j, nt, backpointer):
    # Base case: terminal node (no splits available)
    if (i, j, nt) not in backpointer:
        return [[(i, j, nt)]]
    
    all_trees = []
    # Iterate over every possible split for this non-terminal
    for split in backpointer[(i, j, nt)]:
        k, left_nt, right_nt = split
        # Get all possible left and right subtrees
        left_subtrees = generate_all_parse_trees(i, k, left_nt, backpointer)
        right_subtrees = generate_all_parse_trees(k, j, right_nt, backpointer)
        # Combine every left-right pair with the current node
        for left in left_subtrees:
            for right in right_subtrees:
                all_trees.append([(i, j, nt), left, right])
    
    return all_trees

# Your backpointer data (converted to Python set syntax)
backpointer = {
    (0, 2, 'NP'): {(1, 'AD', 'NP')},
    (1, 3, 'X1'): {(2, 'NP', 'PA')},
    (1, 3, 'NP'): {(2, 'NP', 'NP')},
    (0, 3, 'X1'): {(2, 'NP', 'PA'), (1, 'DT', 'NP')},
    (2, 4, 'X2'): {(3, 'PA', 'VP')},
    (1, 4, 'S'): {(2, 'NP', 'X2'), (3, 'X1', 'VP')},
    (0, 4, 'S'): {(2, 'NP', 'X2'), (3, 'X1', 'VP')}
}

# Generate all parse trees starting from the root (0,4,'S')
parse_trees = generate_all_parse_trees(0, 4, 'S', backpointer)

# Print each unique parse tree
for idx, tree in enumerate(parse_trees, 1):
    print(f"Parse Tree {idx}:")
    print(tree)
    print("---")

What This Outputs #

Running this code will generate all unique nested parse trees starting from your root node (0,4,'S'). Each tree is an independent nested list where:

• The first element is the current node (i,j,nt)
• The second element is the full nested left subtree
• The third element is the full nested right subtree

For example, one of the output trees will look like this:

[
 (0, 4, 'S'),
 [
  (0, 3, 'X1'),
  [
   (0, 2, 'NP'),
   [(0, 1, 'AD')],
   [(1, 2, 'NP')]
  ],
  [(2, 3, 'PA')]
 ],
 [(3, 4, 'VP')]
]

Handling Deep Nesting #

This recursive approach works seamlessly for 5-6 level deep parse trees—Python's default recursion depth limit is way higher than that, so you won't hit issues unless you're dealing with extremely long sentences.

内容的提问来源于stack exchange，提问作者S Roshan