我正在处理从一篇长文章中提取的图。这个有向加权图，实际上只是一个字典，包含作为顶点的头词，这些头词通过边连接到文章中跟随该词的每个词（尾词）。因此，如果单词“yellow”在文章中出现了3次，并且后面跟着单词“brick”、“brick”和“submarine”，那么在图中“yellow”的条目将被表示为如下形式：

{"yellow": ["brick", "brick", "submarine"]}

这个图是使用我编写的名为ExtractedGraph的Python类生成的，除了一个执行生成图工作的__init__方法外，还有一个getProb(self, head_word, tail_word)方法，该方法以头词和尾词作为输入，并输出头词跟随尾词的概率，这是连接头词节点和尾词节点的边的权重。因此，如果我们输入“yellow”和“brick”，输出将是2/3。

我的问题是，如何对这个图进行Beam Search以找到得分最高的句子。具体来说，如果Beam Search函数的输入是一个prefix_words字符串，一个beam_width整数和一个sen_length整数（句子的最大词长度），算法会是什么样的？在网上阅读了关于Beam Search算法的资料并观看了许多教程后，我不确定Beam Search函数在这种特定场景下如何真正工作。

回答：

假设graph_nodes是字典，每个句子必须以概率为1.0的<s>符号开始，并且所有句子必须以特殊符号</s>结束。为了避免对假设进行排序，我将它们保存在堆中，因此添加元素是常数时间操作。

import heapqbeam = [(1.0, ["<s>"])]for _ in range(sen_length):    new_beam = []    for score, hypothesis in beam:        hypothesis_end = hypothesis[-1]        # 完成的假设将返回到beam中并与新的假设竞争        if hypothesis_end == "</s>":            heapq.heappush(new_beam, (score, hypothesis))            if len(new_beam) > beam_width:                heapq.heappop(new_beam)        # 扩展未完成的假设        for possible_continuation in graph_nodes[hypothesis_end]:            continuation_score = score * get_prob(hypothesis_end, possible_continuation)            heapq.heappush(                new_beam, (continuation_score, hypothesis + [possible_continuation])            )            if len(new_beam) > beam_width:                heapq.heappop(new_beam)    beam = new_beam

如果你的假设可以有不同的长度，你应该考虑一些长度归一化（例如，概率的几何平均）。此外，乘概率可能并不总是数值稳定的，因此你可能想要使用对数的和来代替。