Алгоритм группировки текста

Учитывая произвольную строку текста, задача состоит в том, чтобы сгруппировать текст в отдельные разделы шаблона. Каждый раздел имеет разные параметры минимальной и максимальной длины. Решение можно считать оптимальным для участка, если оно находится в этих пределах. Жадное решение может привести к тому, что некоторые разделы не будут соответствовать своим минимумам, что означает, что решение в целом неприемлемо.

У меня возникли проблемы с эффективным построением алгоритма для этого. Кажется, что подход динамического программирования мог бы помочь, но до сих пор мне не удавалось сформулировать его в терминах динамического программирования. У кого-нибудь есть наводки по решению этой проблемы?

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 и наш шаблон t в функцию groupText. groupText должен возвращать массив, в котором каждый элемент i соответствует разделу. Например, элемент 0 будет соответствовать s1. Значением элемента будет текст, присвоенный разделу.

В этом примере может быть решение.

s1text = "Это "

s2text = "это тест".


javascript coffeescript algorithm dynamic-programming
person tabdulla    schedule 14.03.2012    source источник
comment
Пример того, что вы хотите сделать, поможет нам лучше понять ваш вопрос. Особенно пример ввода и желаемого результата.   -  person High Performance Mark    schedule 14.03.2012
comment
Это звучит как задача линейного программирования.   -  person mindvirus    schedule 14.03.2012
comment
@HighPerformanceMark - я добавил пример. Дайте мне знать, если это поможет. Спасибо за ответ.   -  person tabdulla    schedule 14.03.2012
comment
Это не пример, это своего рода повторение вашего исходного вопроса в псевдокоде.   -  person High Performance Mark    schedule 14.03.2012
comment
@mdkess - Спасибо за совет. Я мало знаком с линейным программированием, но я возьму свою копию CLRS и посмотрю, что смогу найти.   -  person tabdulla    schedule 14.03.2012
comment
@tabdulla: основной формат: «Найти x1, x2, x3, ..., xn ›= 0, так что x1 + min1 ‹= max1 и x2 + min2 ‹= max2, .... Однако это было давно, поэтому Я могу ошибаться в своих догадках.   -  person mindvirus    schedule 15.03.2012
comment
@HighPerformanceMark Извините за это. Добавил реальный пример...   -  person tabdulla    schedule 15.03.2012

Ответы (2)


arrow_upward
2
arrow_downward

Если я правильно понял проблему, то искать не нужно... просто вычтите из общей длины сумму минимальных длин, и останется количество, которое нужно распределить. Затем распределите это количество на каждый элемент до его максимума, пока ничего не останется... в коде

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;
person 6502    schedule 14.03.2012

arrow_upward
0
arrow_downward

Итак, вот специальный, непроверенный алгоритм. Если это бесполезно, возможно, этого достаточно, чтобы подтолкнуть кого-то другого к лучшему ответу;

Давайте получим некоторые пробные данные. Предположим, ваш шаблон состоит из 6 разделов с минимальными и максимальными ограничениями:

1 - 12
13 - 25
5 - 7
6 - 7
5 - 5
10 - 25

это означает, что вам понадобится строка длиной не менее 40 и не более 81 символа, чтобы удовлетворить ваши ограничения. И в этом заключается решение. Сначала вычислите таблицу следующим образом:

40 - 81
39 - 69
26 - 34
21 - 37
15 - 30
10 - 25

в котором каждая строка дает общую длину строки, которая все еще может быть разделена по «слотам» в вашем шаблоне. В слот 1 вы помещаете текст так, чтобы у вас оставалось от 39 до 69 символов для остальных слотов. В слот 2 вы помещаете текст так, чтобы у вас оставалось от 26 до 34 символов. И так далее.

person High Performance Mark    schedule 14.03.2012