python - 使用最大和给定跨度的最佳解析树

Question

我想找到一种方法，通过对每棵树的跨度得分求和来对每棵树进行评分，并选择得分最高的二叉树，通过回溯来最大化总和。

假设我有以下句子:

string = "Revenue was 19.9 million"

spans 数组表示对应 (i, j) 位置处的 span 分数。这里:j=i+1

例如，

score(0, 1) = -100.0 对应于范围 "Revenue";

score(0, 4) = 100.0 对应于跨度“收入为 1990 万”；

score(1, 4) = 100.0 对应于跨度“为 1990 万”；

等等...

                                               #  1 2 3 4
spans = [[-100.0, -100.0, -100.0,  100.0],     # 0
         [ 0,     -100.0, -100.0,  100.0],     # 1
         [ 0,       0 ,   -100.0,  100.0],     # 2
         [ 0,       0,      0,    -100.0]]     # 3
         

预期的树是 - (Revenue (was (1990 万))) 对应于跨度 (0, 4), (1, 4) , (2, 4)。

尽管如此，我得到 - (收入为 1990 万)，代码如下。

我尝试这样做:

class MaxSpanCalculator:

    def __init__(self, s, spans):
        self.sentence = s.split(" ")
        self.spans = spans
        self.splits = []

    def get_max_span_sentence(self):
        n = len(self.sentence)
        # Initialize the splits array
        for i in range(n):
            s = []
            for j in range(n):
                s.append(-1)
            self.splits.append(s)

        # Here Using spans array itself as dp array
        for l in range(1, n+1):
            i = 0
            j = i + l - 1
            while j<n:
                if i!=j:
                    for p in range(i,j):
                        if self.spans[i][j] < self.spans[i][p] + self.spans[p+1][j]:
                            self.splits[i][j] = p
                            self.spans[i][j] = self.spans[i][p] + self.spans[p+1][j]
                i = i + 1
                j = j + 1

        print("Max span value: " + str(self.spans[0][n-1]))
        print("Max span sentence is : " + self.get_sentence(0, n-1))

    def get_sentence(self, start, end):
        # print(str(start) + " " + str(end))
        if start==end: return self.sentence[start]
        if self.splits[start][end] == -1:
            return " ".join(x for x in self.sentence[start:end+1])
        return "(" + self.get_sentence(start, self.splits[start][end]) + ")" + "(" + self.get_sentence(self.splits[start][end]+1, end) + ")"

Answer 1

这是一个动态规划问题。

首先，您希望将文本字符串转换为单词数组。因为这就是你的成本。

其次，您需要计算两个数据结构。

1. aggregate_cost[(start, end)] 是从 start 到 end 区间的最佳解析的总成本。<
2. best_parse[(start, end)] 是从 start 到 end 区间的最佳解析。

与所有动态规划问题一样，有自上而下和自下而上的方法来解决。无论哪种方式，关键的见解是总成本是以下各项中最大的:

cost(start, end),
cost(start, end) + aggregate_cost[(start, i)],
cost(start, end) + aggregate_cost[(i+1, end)],
cost(start, end) + aggregate_cost[(start, i)] + aggregate_cost[(i+1, end)]

其中i可以是start和end之间的任意位置。而 best_parse[(start, end)] 取决于您选择的其中一个(当然，还有选择了总成本的子区间的 best_parse)。