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对应跨度 "Revenue was 19.9 million" ; score(1, 4) = 100.0对应跨度 "was 19.9 million" ;
等等 ...

                                               #  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 (19.9 million)))对应于跨度 (0, 4) , (1, 4) , (2, 4) .
虽然，我得到 - (Revenue was 19.9 million)使用以下代码。
我试图做:

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

这是一个动态规划问题。
首先，您要将文本字符串转换为单词数组。因为这就是你的成本。
其次，您需要计算两个数据结构。

aggregate_cost[(start, end)]是来自 start 的区间的最佳解析的总成本至 end .

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)。