Перенос слов в X строк вместо максимальной ширины (наименьшая резкость)

Question

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

e.g. "I would like to be wrapped into two lines"
goes to
"I would like to be
wrapped into two lines"

"I would like to be wrapped into three lines"
goes to
"I would like to
be wrapped into
three lines"

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

Ответы предпочтительнее на языке .NET, но любой язык будет полезен. Очевидно, что если есть каркасный способ сделать это, я не знаю, дайте мне знать.

Редактировать Я нашел это, так как я думаю, что принятый ответ является решением моей проблемы, но мне трудно понять его. Алгоритм разделения текста на 3 группы одинакового размера любой шанс, что кто-нибудь сможет преобразовать его в c # или vb.net.

Answer 1

Способ решения этой проблемы - использование динамического программирования. Вы можете решить эту проблему, используя динамическое программирование, см. Алгоритм минимальной шероховатости .Я использовал некоторые сведения, которые вы добавляете, когда редактируете свое сообщение: Алгоритм разделения текста на 3 группы одинакового размера

---

Обозначения:

Пусть назовет ваш текстовый документ = "word1 word2 .... wordp"

n = необходимое количество строк

LineWidth = len (document) / n

---

Функция стоимости:

Сначала необходимо определить функцию стоимости, состоящую в том, чтобы от слова [i] к слову [j] в одной строке вы могли взять то же самое, что иодин как один в Википедии, с p = 2, например:

Он представляет расстояние между объективной длиной линии и фактической длиной.

Функция общей стоимости для оптимального решения может быть определена с помощью следующего рекурсивного соотношения:

---

Решение проблемы:

Вы можете решить эту проблему с помощью динамического программирования.Я взял код по ссылке, которую вы дали, и изменил его, чтобы вы увидели, что использует программа.

1. На этапе k вы добавляете слова в строку k.
2. Затем выПосмотрите на оптимальную стоимость наличия слова от i до j в строке k.
3. После перехода от строки 1 к n вы берете наименьшую стоимость на последнем шаге и получаете оптимальный результат:

Вот результат из кода:

D=minragged('Just testing to see how this works.')

number of words: 7
------------------------------------
stage : 0
------------------------------------
word i to j in line 0       TotalCost (f(j))
------------------------------------
i= 0 j= 0           121.0
i= 0 j= 1           49.0
i= 0 j= 2           1.0
i= 0 j= 3           16.0
i= 0 j= 4           64.0
i= 0 j= 5           144.0
i= 0 j= 6           289.0
i= 0 j= 7           576.0
------------------------------------
stage : 1
------------------------------------
word i to j in line 1       TotalCost (f(j))
------------------------------------
i= 0 j= 0           242.0
i= 0 j= 1           170.0
i= 0 j= 2           122.0
i= 0 j= 3           137.0
i= 0 j= 4           185.0
i= 0 j= 5           265.0
i= 0 j= 6           410.0
i= 0 j= 7           697.0
i= 1 j= 2           65.0
i= 1 j= 3           50.0
i= 1 j= 4           58.0
i= 1 j= 5           98.0
i= 1 j= 6           193.0
i= 1 j= 7           410.0
i= 2 j= 4           26.0
i= 2 j= 5           2.0
i= 2 j= 6           17.0
i= 2 j= 7           122.0
i= 3 j= 7           80.0
------------------------------------
stage : 2
------------------------------------
word i to j in line 2       TotalCost (f(j))
------------------------------------
i= 0 j= 7           818.0
i= 1 j= 7           531.0
i= 2 j= 7           186.0
i= 3 j= 7           114.0
i= 4 j= 7           42.0
i= 5 j= 7           2.0
reversing list
------------------------------------
Just testing        12
to see how      10
this works.         11

• * Поэтому наилучшим выбором будет иметь слова от 5 до 7 в последней строке (см. Stage2)
• затем слова 2–5 во второй строке (ср. Stage1)
• затем слова 0–2 в первой строке (ср. Ступень 0). *

Reverseэто и вы получите:

Just testing          12
to see how          10
this works.          11

Вот код для распечатки рассуждений (в Python извините, я не использую C # ... но я действительно перевел код в C #):

def minragged(text, n=3):


    P=2
    words = text.split()
    cumwordwidth = [0]
    # cumwordwidth[-1] is the last element
    for word in words:
        cumwordwidth.append(cumwordwidth[-1] + len(word))
    totalwidth = cumwordwidth[-1] + len(words) - 1  # len(words) - 1 spaces
    linewidth = float(totalwidth - (n - 1)) / float(n)  # n - 1 line breaks

    print "number of words:", len(words)
    def cost(i, j):
        """
        cost of a line words[i], ..., words[j - 1] (words[i:j])
        """
        actuallinewidth = max(j - i - 1, 0) + (cumwordwidth[j] - cumwordwidth[i])
        return (linewidth - float(actuallinewidth)) ** P

    """
    printing the reasoning and reversing the return list
    """
    F={} # Total cost function

    for stage in range(n):
        print "------------------------------------"
        print "stage :",stage
        print "------------------------------------"
        print "word i to j in line",stage,"\t\tTotalCost (f(j))"
        print "------------------------------------"


        if stage==0:
            F[stage]=[]
            i=0
            for j in range(i,len(words)+1):
                print "i=",i,"j=",j,"\t\t\t",cost(i,j)
                F[stage].append([cost(i,j),0])
        elif stage==(n-1):
            F[stage]=[[float('inf'),0] for i in range(len(words)+1)]
            for i in range(len(words)+1):
                    j=len(words)
                    if F[stage-1][i][0]+cost(i,j)<F[stage][j][0]: #calculating min cost (cf f formula)
                        F[stage][j][0]=F[stage-1][i][0]+cost(i,j)
                        F[stage][j][1]=i
                        print "i=",i,"j=",j,"\t\t\t",F[stage][j][0]            
        else:
            F[stage]=[[float('inf'),0] for i in range(len(words)+1)]
            for i in range(len(words)+1):
                for j in range(i,len(words)+1):
                    if F[stage-1][i][0]+cost(i,j)<F[stage][j][0]:
                        F[stage][j][0]=F[stage-1][i][0]+cost(i,j)
                        F[stage][j][1]=i
                        print "i=",i,"j=",j,"\t\t\t",F[stage][j][0]

    print 'reversing list'
    print "------------------------------------"
    listWords=[]
    a=len(words)
    for k in xrange(n-1,0,-1):#reverse loop from n-1 to 1
        listWords.append(' '.join(words[F[k][a][1]:a]))
        a=F[k][a][1]
    listWords.append(' '.join(words[0:a]))
    listWords.reverse()

    for line in listWords:
        print line, '\t\t',len(line)

    return listWords

Answer 2

Вот принятое решение от Алгоритм разделения текста на 3 группы одинакового размера , преобразованный в C #:

static List<string> Minragged(string text, int n = 3)
{
    var words = text.Split();

    var cumwordwidth = new List<int>();
    cumwordwidth.Add(0);

    foreach (var word in words)
        cumwordwidth.Add(cumwordwidth[cumwordwidth.Count - 1] + word.Length);

    var totalwidth = cumwordwidth[cumwordwidth.Count - 1] + words.Length - 1;

    var linewidth = (double)(totalwidth - (n - 1)) / n;

    var cost = new Func<int, int, double>((i, j) =>
    {
        var actuallinewidth = Math.Max(j - i - 1, 0) + (cumwordwidth[j] - cumwordwidth[i]);
        return (linewidth - actuallinewidth) * (linewidth - actuallinewidth);
    });

    var best = new List<List<Tuple<double, int>>>();

    var tmp = new List<Tuple<double, int>>();
    best.Add(tmp);
    tmp.Add(new Tuple<double, int>(0.0f, -1));
    foreach (var word in words)
        tmp.Add(new Tuple<double, int>(double.MaxValue, -1));

    for (int l = 1; l < n + 1; ++l)
    {
        tmp = new List<Tuple<double, int>>();
        best.Add(tmp);
        for (int j = 0; j < words.Length + 1; ++j)
        {
            var min = new Tuple<double, int>(best[l - 1][0].Item1 + cost(0, j), 0);
            for (int k = 0; k < j + 1; ++k)
            {
                var loc = best[l - 1][k].Item1 + cost(k, j);
                if (loc < min.Item1 || (loc == min.Item1 && k < min.Item2))
                    min = new Tuple<double, int>(loc, k);
            }
            tmp.Add(min);
        }
    }

    var lines = new List<string>();
    var b = words.Length;

    for (int l = n; l > 0; --l)
    {
        var a = best[l][b].Item2;
        lines.Add(string.Join(" ", words, a, b - a));
        b = a;
    }

    lines.Reverse();
    return lines;
}

Answer 3

Об этой точной проблеме (хотя она была сформулирована по-другому) шла дискуссия на http://www.perlmonks.org/?node_id=180276.

. В конце концов, лучшим решением было выполнить бинарный поиск по всем возможным значениям ширины, чтобы найтинаименьшая ширина, которая заканчивается не более, чем желаемое количество столбцов.Если имеется n элементов и средняя ширина равна m, то вам потребуется O(log(n) + log(m)) проходов, чтобы найти правильную ширину, каждый из которых занимает O(n) времени, для O(n * (log(n) + log(m))).Вероятно, это достаточно быстро, и вам больше не нужно быть умным.

Если вы хотите быть умным, вы можете создать массив словосочетаний и совокупной длины слов.Затем используйте бинарный поиск в этой структуре данных, чтобы выяснить, где находятся разрывы строк.Создание этой структуры данных - O(n), и все проходы для определения правильной ширины равны O(log(n) * (log(n) + log(m))), для которых при разумных длинах слов преобладает ваш первый O(n) проход.

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

Answer 4

btilly имеет правильный ответ здесь, но ради интереса я решил написать решение на python:

def wrap_min_width(words, n):
    r, l = [], ""
    for w in words:
        if len(w) + len(l) > n:
            r, l = r + [l], ""
        l += (" " if len(l) > 0 else "") + w
    return r + [l]  

def min_lines(phrase, lines):
    words = phrase.split(" ")
    hi, lo = sum([ len(w) for w in words ]), min([len(w) for w in words])
    while lo < hi:
        mid = lo + (hi-lo)/2
        v = wrap_min_width(words, mid)
        if len(v) > lines:
            lo = mid + 1
        elif len(v) <= lines:
            hi = mid
    return lo, "\n".join(wrap_min_width(words, lo))

Теперь это все еще может быть не совсем то, что вам нужно, поскольку, если можно обернуть слова в меньше, чем n строк, используя одинаковую ширину строки, вместо этого возвращается наименьшее количество кодировок строк. (Конечно, вы всегда можете добавить лишние пустые строки, но это немного глупо.) Если я запускаю его на вашем тестовом примере, вот что я получаю:

Дело: «Я бы хотел, чтобы меня обернули в три строки», 3 строки

Результат: 14 символов / строка

Я бы хотел

быть завернутым в

три строки

Answer 5

Это решение улучшает Миколу.

Это лучше, потому что

1. Он не использует строки.Вам не нужно использовать строки и объединять их.Вам просто нужен массив их длин.Таким образом, из-за этого он быстрее, также вы можете использовать этот метод с любым видом «элемента» - вам просто нужны ширины.
2. Произошла некоторая ненужная обработка в функции wrap_min_width.Он просто продолжал идти, даже когда выходил за рамки провала.Кроме того, он просто строит строку без необходимости.
3. Добавил "ширину разделителя" в качестве настраиваемого параметра.
4. Он вычисляет минимальную ширину - это действительно то, что вам нужно.
5. Исправлены некоторые ошибки.

Это написано на Javascript:

 // For testing calcMinWidth

var formatString = function (str, nLines) {

    var words = str.split(" ");
    var elWidths = words.map(function (s, i) {
        return s.length;
    });

    var width = calcMinWidth(elWidths, 1, nLines, 0.1);

    var format = function (width)
    {
        var lines = [];
        var curLine = null;
        var curLineLength = 0;

        for (var i = 0; i < words.length; ++i) {
            var word = words[i];
            var elWidth = elWidths[i];

            if (curLineLength + elWidth > width)
            {
                lines.push(curLine.join(" "));
                curLine = [word];
                curLineLength = elWidth;
                continue;
            }

            if (i === 0)
                curLine = [word];
            else
            {
                curLineLength += 1;
                curLine.push(word);
            }

            curLineLength += elWidth;
        }

        if (curLine !== null)
            lines.push(curLine.join(" "));

        return lines.join("\n");
    };

    return format(width);
};

var calcMinWidth = function (elWidths, separatorWidth, lines, tolerance)
{
    var testFit = function (width)
    {
        var nCurLine = 1;
        var curLineLength = 0;

        for (var i = 0; i < elWidths.length; ++i) {
            var elWidth = elWidths[i];

            if (curLineLength + elWidth > width)
            {
                if (elWidth > width)
                    return false;

                if (++nCurLine > lines)
                    return false;

                curLineLength = elWidth;
                continue;
            }

            if (i > 0)
                curLineLength += separatorWidth;

            curLineLength += elWidth;
        }

        return true;
    };


    var hi = 0;
    var lo = null;

    for (var i = 0; i < elWidths.length; ++i) {
        var elWidth = elWidths[i];

        if (i > 0)
            hi += separatorWidth;

        hi += elWidth;

        if (lo === null || elWidth > lo)
            lo = elWidth;
    }

    if (lo === null)
        lo = 0;

    while (hi - lo > tolerance)
    {
        var guess = (hi + lo) / 2;

        if (testFit(guess))
            hi = guess;
        else
            lo = guess;
    }

    return hi;
};

Answer 6

Я преобразовал принятый C # ответ в JavaScript для чего-то, над чем я работал. Размещение этого сообщения может сэкономить кому-то несколько минут на самостоятельной работе.

function WrapTextWithLimit(text, n) {
    var words = text.toString().split(' ');
    var cumwordwidth = [0];
    words.forEach(function(word) {
        cumwordwidth.push(cumwordwidth[cumwordwidth.length - 1] + word.length);
    });
    var totalwidth = cumwordwidth[cumwordwidth.length - 1] + words.length - 1;
    var linewidth = (totalwidth - (n - 1.0)) / n;
    var cost = function(i, j) {
        var actuallinewidth = Math.max(j - i - 1, 0) + (cumwordwidth[j] - cumwordwidth[i]);
        return (linewidth - actuallinewidth) * (linewidth - actuallinewidth);
    };
    var best = [];
    var tmp = [];
    best.push(tmp);
    tmp.push([0.0, -1]);
    words.forEach(function(word) {
        tmp.push([Number.MAX_VALUE, -1]);
    });
    for (var l = 1; l < n + 1; ++l)
    {
        tmp = [];
        best.push(tmp);
        for (var j = 0; j < words.length + 1; ++j)
        {
            var min = [best[l - 1][0][0] + cost(0, j), 0];
            for (var k = 0; k < j + 1; ++k)
            {
                var loc = best[l - 1][k][0] + cost(k, j);
                if (loc < min[0] || (loc === min[0] && k < min[1])) {
                    min = [loc, k];
                }
            }
            tmp.push(min);
        }
    }
    var lines = [];
    var b = words.length;
    for (var p = n; p > 0; --p) {
        var a = best[p][b][1];
        lines.push(words.slice(a, b).join(' '));
        b = a;
    }
    lines.reverse();
    return lines;
}

Answer 7

Я предполагаю, что вы пытаетесь минимизировать максимальную ширину строки с n разрывами. Это может быть сделано за O (слова (str) * n) времени и пространства с использованием динамического программирования или рекурсии с запоминанием.

Повторение будет выглядеть так, если слово было разбито на слова

def wordwrap(remaining_words, n):
    if n > 0 and len(remaining_words)==0:
        return INFINITY  #we havent chopped enough lines

    if n == 0:
        return len(remaining_words.join(' ')) # rest of the string

    best = INFINITY
    for i in range remaining_words:
        # split here 
        best = min( max(wordwrap( remaining_words[i+1:], n-1),remaining_words[:i].join(' ')), best  )  

    return best

Answer 8

Я просто подумал о подходе:
Вы можете написать функцию, принимающую два параметра: 1. Строка 2. Количество строк

Получить длину строки (String.length, если используется C #). Разделите длину на количество строк (скажем, результат равен n)

Теперь запустите цикл и получите доступ к каждому символу строки (используя строку [i]) Вставьте '\ n \ r' после каждого n-го вхождения в массив символов.

В цикле сохраните массив временных строк, который будет нулевым, если есть пустой символ (с сохранением каждого слова).
Если есть n-ное вхождение и временная строка не равна нулю, вставьте '\ n \ r' после этой временной строки.