用最重的词语分句子

我正在研究一个游戏，我需要为特定的句子找到最大的分量。用最重的词语分句子

假设我有一句话“快速棕色狐狸”，并假设他们的定义体重只有单个单词：“the” - > 10，“quick” - > 5，“brown” - > 3，“fox” - > 8

在这种情况下，问题是微不足道的，因为解决方案包括添加每个单词的权重。

现在假设我们还加双字，所以除了上述的话，我们也有“快” - > 5，“敏捷的棕色” - > 10，“棕色狐狸” - > 1

我d想知道哪个单字和双字组合提供了最大的重量，在这种情况下，它将是“the”，“quick brown”，“fox”我的问题是，除了明显的暴力方法外，有没有其他可能的方法来获得解决方案？不用说，我正在寻找一些最佳的方法来实现这个更大的句子。

谢谢。

来源

2012-04-03 Dan

因此，句子'快速'的分数是'10 + 5 + 5'？ – mbatchkarov 2012-04-04 16:54:45

首先，句子应该包含所有的单词，无论是单或双。在我显示的情况下，总分将是10 + 10 + 8。请注意，分数适用于单词或双字，而不是两者。 – Dan 2012-04-04 17:44:26

您可以查看Integer Linear Program库，如lp_solve。在这种情况下，您需要最大化分数，并且您的目标函数将包含权重。然后你可以对它进行限制，就像你不能同时拥有“快速棕色”和“棕色”一样。

对于单词对齐，这是用于此paper，但您的问题比这更简单，但您可以浏览论文以了解如何使用ILP。除了ILP以外，可能还有其他一些算法可以用来解决这个问题，但ILP可以针对小问题以最优和有效的方式解决这个问题。

来源

2012-04-04 03:17:38

谢谢，这似乎对我想达到的目标非常有用。将看看这篇论文，并希望了解如何将我的问题映射到这种方法。 – Dan 2012-04-04 17:42:17

这感觉就像一个动态编程问题。

我可以想象在每个单词（即总共k-1个灯泡）之间放置一个灯泡的句子的k个单词。如果灯泡开启，这意味着毗连它的单词是单个短语的一部分，如果它关闭，它们不是。因此，这些灯泡的任何配置都会指示重量的可能组合。当然，许多配置都不可能实现，因为我们没有为他们需要的短语获得任何分数。所以k-1灯泡意味着我们可以通过最多2 ^（k-1）个可能的答案。我们可以认识到，我们可以在其他计算中重用每个计算的一部分，所以对于（The）（快速）（brown fox ...懒狗）和（the quick）（棕色狐狸...懒惰的狗），我们可以只计算一次（棕色狐狸...懒狗）的最高分数，记住它并在下次看到它时不做任何额外的工作而重新使用它。

在我们开始之前，我们应该首先摆脱只有1个可能值的灯泡（假设我们没有“棕色狐狸”这个短语或者带有这个短语的任何更大的短语，那么光线“棕色”和“狐狸”之间的灯泡总是必须关闭）。每个取下的灯泡将解决方案空间减半。

如果w1，w2，w3是单词，那么灯泡将是w1w2，w2w3，w3w4等。所以

Optimal(w1w2 w2w3 w3w4 ...) = max(Optimal(w2w3 w3w4 ...) given w1w2 is on, Optimal(w2w3 w3w4 ...) given w1w2 is off)

（买者如果我们到达那里，我们有没有可能解决方案的东西，我们只是回到MIN_INT，事情应该工作了）

我们可以解决这样的问题，但我们大概可以节省更多时间，如果是聪明的我们接近灯泡的顺序。也许首先攻击中心灯泡可能会有所帮助。我不确定这部分。

来源

2012-04-04 17:43:37

用最重的词语分句子

回答

相关问题