文本分组算法

给定一个任意字符串的文本，任务是将文本分组为模板的不同部分。每个部分具有不同的最小长度和最大长度参数。只要一个解决方案落在这些范围内，就可以认为解决方案是最优的。贪婪的解决方案可能会导致某些部分达不到最低要求，这意味着解决方案作为一个整体是不可接受的。文本分组算法

我很难有效地构造一个算法来做到这一点。似乎动态编程方法可能会有所帮助，但到目前为止，我还没有能够用动态编程术语来解决它。有没有人有解决这个问题的任何线索？

function groupText(str, template) 
Inputs: 
str: a string of text 
template: array of JavaScript objects. 
      One object per section that describes the min/max amount of text allowed 
Output: 
array: each element corresponds to one section. 
     The value of the element is the text that is in the section.

作为一个例子，让我们定义一个字符串str，它等于“这是一个测试”。我们也有一个模板t。 t由几个部分组成。每个部分s具有允许的最小字符数和最大字符数。假设这个例子只有两个部分：s1和s2。 S1具有最小1个字符的和最大的100 S2具有最小的10个字符，最多15。我们通过我们的字符串STR和我们的模板吨到功能groupText。 groupText必须返回一个数组，其中每个元素对应于一个段。例如，元素0将对应于s1。元素的值将是已分配给该部分的文本。

在这个例子中，一个解决方案可能是。

s1text = “此”

s2text = “是一个测试”。

来源

2012-03-14 tabdulla

你想要做的一个例子会帮助我们更好地理解你的问题。尤其是输入和期望输出的一个例子。 – 2012-03-14 19:43:31

这听起来像是一个线性编程问题。 – mindvirus 2012-03-14 19:54:06

@HighPerformanceMark - 我已经添加了一个例子。让我知道这是否有帮助。感谢您的反馈。 – tabdulla 2012-03-14 19:57:21

如果我正确地理解了问题，则不需要任何搜索......只需从总长度中减去最小长度的总和，剩下的就是要分配的数量。然后，直到没有剩下分发本金额每一个元素到其最大...代码

var minsum = 0; 
for (vsr i=0; i < sections.length; i++) 
    minsum += sections[i].min_size; 
var extra = text.length - minsum; 
if (extra < 0) return null; // no solution 
var solution = []; 
for (var i=0; i < sections.length; i++) 
{ 
    var x = sections[i].min_size + extra; 
    if (x > sections[i].max_size) 
     x = sections[i].max_size; 
    solution.push(x); 
    extra -= x - sections[i].min_size; 
} 
if (extra > 0) return null; // no solution 
return solution;

来源

2012-03-14 20:17:47 6502

OK，所以这里是一个特设的，未经测试的算法。如果它不好，也许这足以让别人更好地回答问题;

让我们有一些试用数据。假设你的模板包括6个部分，其中有最小，最大限制为：

这意味着你将需要至少40和最多81个字符的字符串，以满足您的约束。解决方案就在于此。首先，计算像这样的表：

，其中每行给出的字符串的总长度仍可以跨越“插槽”在您的模板进行分区。在插槽1中放置文本，以便剩下的插槽仍有39到69个字符。在插槽2中放置文字，以便您仍然有26到34个字符。等等。

来源

2012-03-14 20:20:50

文本分组算法

回答

相关问题