Алгоритм: разбить строку на N частей, используя пробелы, чтобы все части имели почти одинаковую длину

Question

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

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

редактировать: Чтобы уточнить мой вопрос, я опишу вам проблему, которую пытаюсь решить.

Я генерирую изображения с фиксированной шириной. На этих изображениях я пишу имена пользователей, используя GD и Freetype в PHP. Поскольку у меня фиксированная ширина, я хочу разделить имена на 2 или 3 строки, если они не помещаются в одну.

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

(Затем я вычисляю ширину текстового блока, используя 1, 2 или 3 строки, и если он умещается в моем изображении, я отрисовываю его. Просто, если есть 3 строки и они не помещаются, я уменьшаю размер шрифта, пока все не будет в порядке .)

Пример: This is a long text должно отображаться что-то вроде этого:

This is a
long text

или

This is
a long
text

но не:

This
is a long
text

а также нет:

This is a long
text

Надеюсь, я смогу объяснить более четко, что я ищу.

Answer 1

Если вы говорите о переносе строк, взгляните на Динамическое разбиение строк , которое дает решение Динамическое программирование для разделения слов на строки.

Answer 2

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

Кажется, что приведенный ниже код работает, хотя есть много ошибок, которые он не обрабатывает. Кажется, что он будет работать в O (n), где n - это количество строк, которое вы хотите.

class Program
{
    static void Main(string[] args)
    {
        var s = "This is a string for testing purposes. It will be split into 3 parts";
        var p = s.Length / 3;
        var w1 = 0;
        var w2 = FindClosestWordIndex(s, p);
        var w3 = FindClosestWordIndex(s, p * 2);
        Console.WriteLine(string.Format("1: {0}", s.Substring(w1, w2 - w1).Trim()));
        Console.WriteLine(string.Format("2: {0}", s.Substring(w2, w3 - w2).Trim()));
        Console.WriteLine(string.Format("3: {0}", s.Substring(w3).Trim()));
        Console.ReadKey();
    }

    public static int FindClosestWordIndex(string s, int startIndex)
    {
        int wordAfterIndex = -1;
        int wordBeforeIndex = -1;
        for (int i = startIndex; i < s.Length; i++)
        {
            if (s[i] == ' ')
            {
                wordAfterIndex = i;
                break;
            }
        }
        for (int i = startIndex; i >= 0; i--)
        {
            if (s[i] == ' ')
            {
                wordBeforeIndex = i;
                break;
            }
        }

        if (wordAfterIndex - startIndex <= startIndex - wordBeforeIndex)
            return wordAfterIndex;
        else
            return wordBeforeIndex;
    }
}

Выход для этого:

1: This is a string for
2: testing purposes. It will
3: be split into 3 parts

Answer 3

Опять же, после ответа Брайана, я сделал PHP-версию его кода:

// Input text
$txt = "This is a really long string that should be broken up onto lines of about the same number of characters.";

// Number of lines
$numLines = 3;

/* Do it, result comes as an array: */
$aResult = splitLinesByClosestWhitespace($txt, $numLines);

/* Output result: */
if ($aResult) 
{
    for ($x=1; $x<=$numLines; $x++) 
        echo "Line ".$x.": ".$aResult[$x]."<br>";

} else {
    echo "Not enough spaces to generate the lines!";
}



/**********************/



/**
 * Splits a string into multiple lines of the closest possible same length, 
 * using the closest whitespaces
 * @param string $txt   String to split
 * @param integer $numLines Number of lines
 * @return array|false
 */
 function splitLinesByClosestWhitespace($txt, $numLines) 
 {
   $p           = intval( strlen($txt) / $numLines );
   $aTxtIndx    = array();
   $aTxt        = array();

   // Check we have enough whitespaces to generate the number of lines
   $wsCount = count( explode(" ", $txt) ) - 1;
   if ($wsCount<$numLines)
       return false;

   // Get the indexes
   for ($x=1;  $x<=$numLines; $x++) 
   {
       $aTxtIndx[$x] = FindClosestWordIndex($txt, $p * ($x-1) );
   }

   // Do the split
   for ($x=1;  $x<=$numLines; $x++) 
   {
       if ($x != $numLines)
           $aTxt[$x] = substr( $txt, $aTxtIndx[$x], trim($aTxtIndx[$x+1]) );
       else
           $aTxt[$x] = substr( $txt, trim($aTxtIndx[$x]) );
   }

   return $aTxt;
 }


/**
 * Finds the closest word to a string index
 * @param string $s String to search
 * @param integer $startIndex   Index at which to find the closest word
 * @return integer
 */
function FindClosestWordIndex($s, $startIndex) 
{
    $wordAfterIndex = 0;
    $wordBeforeIndex = 0;

    for ($i = $startIndex; $i < strlen($s); $i++)
    {
        if ($s[$i] == ' ')
        {
            $wordAfterIndex = $i;
            break;
        }
    }
    for ($i = $startIndex; $i >= 0; $i--)
    {
        if ($s[$i] == ' ')
        {
            $wordBeforeIndex = $i;
            break;
        }
    }

    if ($wordAfterIndex - $startIndex <= $startIndex - $wordBeforeIndex)
        return $wordAfterIndex;
    else
        return $wordBeforeIndex;
}

Answer 4

После ответа Брайана я сделал версию его кода на JavaScript: http://jsfiddle.net/gmoz22/CPGY2/.

// Input text
var txt = "This is a really long string that should be broken up onto lines of about the same number of characters.";

// Number of lines
var numLines = 3;

/* Do it, result comes as an array: */
var aResult = splitLinesByClosestWhitespace(txt, numLines);

/* Output result: */
if (aResult) 
{
    for (var x = 1; x<=numLines; x++) 
        document.write( "Line "+x+": " + aResult[x] + "<br>" );

} else {
    document.write("Not enough spaces to generate the lines!");
}


/**********************/
// Original algorithm by /2140102/algoritm-razbit-stroku-na-n-chastei-ispolzuya-probely-chtoby-vse-chasti-imeli-pochti-odinakovuy-dlinu#2140116, rewritten for JavaScript by Steve Oziel


/**
 * Trims a string for older browsers
 * Used only if trim() if it is not already available on the Prototype-Object
 * since overriding it is a huge performance hit (generally recommended when extending Native Objects)
 */
if (!String.prototype.trim) 
{
    String.prototype.trim = function(){return this.replace(/^\s+|\s+$/g, '');};
}


/**
 * Splits a string into multiple lines of the closest possible same length, 
 * using the closest whitespaces
 * @param {string} txt  String to split
 * @param {integer} numLines    Number of lines
 * @returns {Array}
 */
function splitLinesByClosestWhitespace(txt, numLines) 
{
    var p           = parseInt(txt.length / numLines);
    var aTxtIndx    = [];
    var aTxt        = [];

    // Check we have enough whitespaces to generate the number of lines
   var wsCount = txt.split(" ").length - 1;
   if (wsCount<numLines)
       return false;

    // Get the indexes
    for (var x=1;  x<=numLines; x++) 
    {
        aTxtIndx[x] = FindClosestWordIndex(txt, p * (x-1) );
    }
    // Do the split
    for (var x=1;  x<=numLines; x++) 
    {
        if (x != numLines)
            aTxt[x] = txt.slice(aTxtIndx[x], aTxtIndx[x+1]).trim();
        else 
            aTxt[x] = txt.slice(aTxtIndx[x]).trim();
    }

    return aTxt;
}

/**
 * Finds the closest word to a string index
 * @param {string} s    String to search
 * @param {integer} startIndex Index at which to find the closest word
 * @returns {integer}
 */
function FindClosestWordIndex(s, startIndex) 
{
    var wordAfterIndex = 0;
    var wordBeforeIndex = 0;
    for (var i = startIndex; i < s.length; i++)
    {
        if (s[i] == ' ')
        {
            wordAfterIndex = i;
            break;
        }
    }
    for (var i = startIndex; i >= 0; i--)
    {
        if (s[i] == ' ')
        {
            wordBeforeIndex = i;
            break;
        }
    }

    if (wordAfterIndex - startIndex <= startIndex - wordBeforeIndex)
        return wordAfterIndex;
    else
        return wordBeforeIndex;
}

Работает нормально, когда количество желаемых строк не слишком близко к количеству пробелов. В примере, который я привел, есть 19 пробелов, и он начинает ошибаться, когда вы просите разбить его на 17, 18 или 19 строк. Редактирование приветствуется!

Answer 5

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

Независимо от того, какой алгоритм вы используете, имейте в виду, что если вы не работаете со шрифтом фиксированной ширины, вы хотите работать с физической шириной слова, а не с количеством букв.

Answer 6

рабочие коды питона

1. Wrap.py - разбивать абзацы на строки, пытаясь избежать коротких строк.
2. SMAWK.py - То же самое в O(n)

коды David Eppstein .

Answer 7

Разделение на равные размеры NP-Complete