Сбалансированный перенос слов (минимальная рвность) в PHP

Question

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

Пример ввода текста:

How to do things 

Неправильный выход (это нормальное поведение перенос слов), м = 6:

How to 
do 
things 

Желаемый выход, всегда т = 6

How 
to do 
things 

Doe у кого есть предложения или рекомендации о том, как реализовать эту функцию? В принципе, Я ищу что-то для довольно коротких коротких фраз на двух или трех (насколько это возможно) линии с одинаковой длиной.

---

Update: Кажется, я ищу именно для Minimum raggedness word wrap algorithm. Но я не могу найти какую-либо реализацию на реальном языке программирования (кто-то, тогда я могу преобразовать его в PHP).

---

Update 2: Я начал баунти для этого. Возможно ли, что не существует какой-либо публичной реализации алгоритма минимальной рваности на любом процедурном языке? Мне нужно что-то написанное таким образом, чтобы его можно было перевести в процедурные инструкции. Все, что я могу найти сейчас, - это просто реплика (общее) уравнение, которое, однако, нуждается в оптимальной процедуре поиска. Я буду признателен также за реализацию, которая может только приблизить этот оптимальный алгоритм поиска.

Answer 1

Быстрая и грязная, в C++

#include <sstream> 
#include <iostream> 
#include <vector> 
#include <cstdlib> 
#include <memory.h> 

using namespace std; 

int cac[1000][1000]; 
string res[1000][1000]; 
vector<string> words; 
int M; 

int go(int a, int b){ 
    if(cac[a][b]>= 0) return cac[a][b]; 
    if(a == b) return 0; 

    int csum = -1; 
    for(int i=a; i<b; ++i){ 
    csum += words[i].size() + 1; 
    } 
    if(csum <= M || a == b-1){ 
    string sep = ""; 
     for(int i=a; i<b; ++i){ 
      res[a][b].append(sep); 
      res[a][b].append(words[i]); 
      sep = " "; 
    } 
    return cac[a][b] = (M-csum)*(M-csum); 
    } 

    int ret = 1000000000; 
    int best_sp = -1; 
    for(int sp=a+1; sp<b; ++sp){ 
    int cur = go(a, sp) + go(sp,b); 
    if(cur <= ret){ 
     ret = cur; 
     best_sp = sp; 
    } 
    } 
    res[a][b] = res[a][best_sp] + "\n" + res[best_sp][b]; 
    return cac[a][b] = ret; 
} 


int main(int argc, char ** argv){ 
    memset(cac, -1, sizeof(cac)); 
    M = atoi(argv[1]); 
    string word; 
    while(cin >> word) words.push_back(word); 
    go(0, words.size()); 
    cout << res[0][words.size()] << endl; 
} 

Тест:

$ echo "The quick brown fox jumps over a lazy dog" |./a.out 10 
The quick 
brown fox 
jumps over 
a lazy dog 

РЕДАКТИРОВАТЬ: просто просмотрите страницу wikipedia для минимальной обертки слова оборванности. Изменен алгоритм на заданное (с квадратными штрафов)

Answer 2

Justin's link до Knuth's Breaking Paragraphs Into Lines является исторически best Ответ. (Новейшие системы также применяют методы , такие как возиться с шириной символов, кернинг и т. Д., Но если вы просто ищете моноширинный текст, эти дополнительные подходы не помогут.)

Если вы просто хотите для решения проблемы утилита fmt(1), поставляемая во многих Linux-системах Free Software Foundation, реализует вариант алгоритма Кнута, который также пытается избежать разрывов строк в конце предложений.Я написал свои входы и больший пример, и побежал их через fmt -w 20, чтобы заставить 20-символьные строки:

$ fmt -w 20 input 
Lorem ipsum dolor 
sit amet 

Supercalifragilisticexpialidocious 
and some other 
small words 

One long 
extra-long-word 

This extra-long 
paragraph 
was writtin to 
demonstrate how the 
`fmt(1)` program 
handles longer 
inputs. When 
testing inputs, 
you don't want them 
to be too short, 
nor too long, 
because the quality 
of the program can 
only be determined 
upon inspection 
of complex 
content. The quick 
brown fox jumps 
over the lazy 
dog. Congress 
shall make no 
law respecting 
an establishment 
of religion, or 
prohibiting the 
free exercise 
thereof; or 
abridging the 
freedom of speech, 
or of the press; 
or the right of the 
people peaceably 
to assemble, 
and to petition 
the Government 
for a redress of 
grievances. 

Выход выглядит гораздо лучше, если вы позволите ему по умолчанию 75 символов ширины для нетривиального ввода:

$ fmt input 
Lorem ipsum dolor sit amet 

Supercalifragilisticexpialidocious and some other small words 

One long extra-long-word 

This extra-long paragraph was writtin to demonstrate how the `fmt(1)` 
program handles longer inputs. When testing inputs, you don't want them 
to be too short, nor too long, because the quality of the program can 
only be determined upon inspection of complex content. The quick brown 
fox jumps over the lazy dog. Congress shall make no law respecting an 
establishment of religion, or prohibiting the free exercise thereof; 
or abridging the freedom of speech, or of the press; or the right of 
the people peaceably to assemble, and to petition the Government for a 
redress of grievances. 

Answer 3

AC версии:

// This is a direct implementation of the minimum raggedness word wrapping 
// algorithm from http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness 

#include <stdio.h> 
#include <string.h> 
#include <ctype.h> 
#include <stdlib.h> 
#include <limits.h> 

const char* pText = "How to do things"; 
int LineWidth = 6; 
int WordCnt; 
const char** pWords; 
int* pWordLengths; 

int* pC; 
int* pF; 
int* pW; 
int* pS; 

int CountWords(const char* p) 
{ 
    int cnt = 0; 

    while (*p != '\0') 
    { 
    while (*p != '\0' && isspace(*p)) p++; 

    if (*p != '\0') 
    { 
     cnt++; 
     while (*p != '\0' && !isspace(*p)) p++; 
    } 
    } 

    return cnt; 
} 

void FindWords(const char* p, int cnt, const char** pWords, int* pWordLengths) 
{ 
    while (*p != '\0') 
    { 
    while (*p != '\0' && isspace(*p)) p++; 

    if (*p != '\0') 
    { 
     *pWords++ = p; 
     while (*p != '\0' && !isspace(*p)) p++; 
     *pWordLengths++ = p - pWords[-1]; 
    } 
    } 
} 

void PrintWord(const char* p, int l) 
{ 
    int i; 

    for (i = 0; i < l; i++) 
    printf("%c", p[i]); 
} 

// 1st program's argument is the text 
// 2nd program's argument is the line width 
int main(int argc, char* argv[]) 
{ 
    int i, j; 

    if (argc >= 3) 
    { 
    pText = argv[1]; 
    LineWidth = atoi(argv[2]); 
    } 

    WordCnt = CountWords(pText); 

    pWords = malloc(WordCnt * sizeof(*pWords)); 
    pWordLengths = malloc(WordCnt * sizeof(*pWordLengths)); 

    FindWords(pText, WordCnt, pWords, pWordLengths); 

    printf("Input Text: \"%s\"\n", pText); 
    printf("Line Width: %d\n", LineWidth); 
    printf("Words  : %d\n", WordCnt); 

#if 0 
    for (i = 0; i < WordCnt; i++) 
    { 
    printf("\""); 
    PrintWord(pWords[i], pWordLengths[i]); 
    printf("\"\n"); 
    } 
#endif 

    // Build c(i,j) in pC[] 
    pC = malloc(WordCnt * WordCnt * sizeof(int)); 
    for (i = 0; i < WordCnt; i++) 
    { 
    for (j = 0; j < WordCnt; j++) 
     if (j >= i) 
     { 
     int k; 
     int c = LineWidth - (j - i); 
     for (k = i; k <= j; k++) c -= pWordLengths[k]; 
     c = (c >= 0) ? c * c : INT_MAX; 
     pC[j * WordCnt + i] = c; 
     } 
     else 
     pC[j * WordCnt + i] = INT_MAX; 
    } 

    // Build f(j) in pF[] and store the wrap points in pW[] 
    pF = malloc(WordCnt * sizeof(int)); 
    pW = malloc(WordCnt * sizeof(int)); 
    for (j = 0; j < WordCnt; j++) 
    { 
    pW[j] = 0; 
    if ((pF[j] = pC[j * WordCnt]) == INT_MAX) 
    { 
     int k; 
     for (k = 0; k < j; k++) 
     { 
     int s; 
     if (pF[k] == INT_MAX || pC[j * WordCnt + k + 1] == INT_MAX) 
      s = INT_MAX; 
     else 
      s = pF[k] + pC[j * WordCnt + k + 1]; 
     if (pF[j] > s) 
     { 
      pF[j] = s; 
      pW[j] = k + 1; 
     } 
     } 
    } 
    } 

    // Print the optimal solution cost 
    printf("f   : %d\n", pF[WordCnt - 1]); 

    // Print the optimal solution, if any 
    pS = malloc(2 * WordCnt * sizeof(int)); 
    if (pF[WordCnt - 1] != INT_MAX) 
    { 
    // Work out the solution's words by back tracking the 
    // wrap points from pW[] and store them on the pS[] stack 
    j = WordCnt - 1; 
    for (;;) 
    { 
     *pS++ = j; 
     *pS++ = pW[j]; 
     if (!pW[j]) break; 
     j = pW[j] - 1; 
    } 
    // Print the solution line by line, word by word 
    // in direct order 
    do 
    { 
     int k; 
     i = *--pS; 
     j = *--pS; 
     for (k = i; k <= j; k++) 
     { 
     PrintWord(pWords[k], pWordLengths[k]); 
     printf(" "); 
     } 
     printf("\n"); 
    } while (j < WordCnt - 1); 
    } 

    return 0; 
} 

Выход 1:

ww.exe 
Input Text: "How to do things" 
Line Width: 6 
Words  : 4 
f   : 10 
How 
to do 
things 

Выход 2:

ww.exe "aaa bb cc ddddd" 6 
Input Text: "aaa bb cc ddddd" 
Line Width: 6 
Words  : 4 
f   : 11 
aaa 
bb cc 
ddddd 

Выход 3:

ww.exe "I started a bounty for this. Is it possible that do not exist any public implementation of Minimum raggedness algorithm in any procedural language? I need something written in a way that can be translated into procedural instructions. All I can find now is just a bounch of (generic) equation that however need a optimal searhing procedure. I will be grateful also for an implementation that can only approximate that optimal searching algorithm." 60 
Input Text: "I started a bounty for this. Is it possible that do not exist any public implementation of Minimum raggedness algorithm in any procedural language? I need something written in a way that can be translated into procedural instructions. All I can find now is just a bounch of (generic) equation that however need a optimal searhing procedure. I will be grateful also for an implementation that can only approximate that optimal searching algorithm." 
Line Width: 60 
Words  : 73 
f   : 241 
I started a bounty for this. Is it possible that do not 
exist any public implementation of Minimum raggedness 
algorithm in any procedural language? I need something 
written in a way that can be translated into procedural 
instructions. All I can find now is just a bounch of 
(generic) equation that however need a optimal searhing 
procedure. I will be grateful also for an implementation 
that can only approximate that optimal searching algorithm. 

Answer 4

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

E.g.

/** 
* balancedWordWrap 
* 
* @param string $input 
* @param int $maxWidth the max chars per line 
*/ 
function balancedWordWrap($input, $maxWidth = null) { 
    $length = strlen($input); 
    if (!$maxWidth) { 
     $maxWidth = min(ceil($length/2), 75); 
    } 
    $minWidth = min(ceil($length/2), $maxWidth/2); 

    $permutations = array(); 
    $scores = array(); 
    $lowestScore = 999; 
    $lowest = $minWidth; 

    foreach(range($minWidth, $maxWidth) as $width) { 
     $permutations[$width] = wordwrap($input, $width); 
     $lines = explode("\n", $permutations[$width]); 

     $max = 0; 
     foreach($lines as $line) { 
      $lineLength = strlen($line); 
      if ($lineLength > $max) { 
       $max = $lineLength; 
      } 
     } 

     $score = 0; 
     foreach($lines as $line) { 
      $lineLength = strlen($line); 
      $score += pow($max - $lineLength, 2); 
     } 

     $scores[$width] = $score; 
     if ($score < $lowestScore) { 
      $lowestScore = $score; 
      $lowest = $width; 
     } 
    } 

    return $permutations[$lowest]; 
} 

Учитывая вход "как сделать что-то"

выводит

How 
to do 
things 

Учитывая вход "Мэри был барашек"

выводит

 
Mary had a 
little lamb 

Данные вход «Этот лишний абзац был решен, чтобы продемонстрировать, как программа fmt(1) обрабатывает более длинные входы. При тестировании входных данных вы не хотите, чтобы они были слишком короткими или слишком длинными, потому что качество программы может быть определено только при проверке сложного контента. Быстрая коричневая лиса прыгает через ленивую собаку. Конгресс не принимает никаких законов, касающихся установления религии или запрещает их свободное осуществление; или сокращению свободы слова или печати; . Или право народа мирно собираться и урезонить правительство для удовлетворения жалоб ", и ограничивается до 75 символов Максимальная ширина, она выводит:

 
This extra-long paragraph was writtin to demonstrate how the `fmt(1)` 
program handles longer inputs. When testing inputs, you don't want them 
be too short, nor too long, because the quality of the program can only be 
determined upon inspection of complex content. The quick brown fox jumps 
over the lazy dog. Congress shall make no law respecting an establishment 
of religion, or prohibiting the free exercise thereof; or abridging the 
freedom of speech, or of the press; or the right of the people peaceably 
to assemble, and to petition the Government for a redress of grievances. 

Answer 5

Я реализовал на тех же линиях Алекс, кодирующий алгоритм Википедии, но непосредственно в PHP (интересное упражнение для меня). Понимание того, как использовать функцию оптимальной стоимости f (j), т. Е. Часть «повторения», не очень проста. хорошо прокомментированный код.

/** 
* minimumRaggedness 
* 
* @param string $input paragraph. Each word separed by 1 space. 
* @param int $LineWidth the max chars per line. 
* @param string $lineBreak wrapped lines separator. 
* 
* @return string $output the paragraph wrapped. 
*/ 
function minimumRaggedness($input, $LineWidth, $lineBreak = "\n") 
{ 
    $words = explode(" ", $input); 
    $wsnum = count($words); 
    $wslen = array_map("strlen", $words); 
    $inf = 1000000; //PHP_INT_MAX; 

    // keep Costs 
    $C = array(); 

    for ($i = 0; $i < $wsnum; ++$i) 
    { 
     $C[] = array(); 
     for ($j = $i; $j < $wsnum; ++$j) 
     { 
      $l = 0; 
      for ($k = $i; $k <= $j; ++$k) 
       $l += $wslen[$k]; 
      $c = $LineWidth - ($j - $i) - $l; 
      if ($c < 0) 
       $c = $inf; 
      else 
       $c = $c * $c; 
      $C[$i][$j] = $c; 
     } 
    } 

    // apply recurrence 
    $F = array(); 
    $W = array(); 
    for ($j = 0; $j < $wsnum; ++$j) 
    { 
     $F[$j] = $C[0][$j]; 
     $W[$j] = 0; 
     if ($F[$j] == $inf) 
     { 
      for ($k = 0; $k < $j; ++$k) 
      { 
       $t = $F[$k] + $C[$k + 1][$j]; 
       if ($t < $F[$j]) 
       { 
        $F[$j] = $t; 
        $W[$j] = $k + 1; 
       } 
      } 
     } 
    } 

    // rebuild wrapped paragraph 
    $output = ""; 
    if ($F[$wsnum - 1] < $inf) 
    { 
     $S = array(); 
     $j = $wsnum - 1; 
     for (; ;) 
     { 
      $S[] = $j; 
      $S[] = $W[$j]; 
      if ($W[$j] == 0) 
       break; 
      $j = $W[$j] - 1; 
     } 

     $pS = count($S) - 1; 
     do 
     { 
      $i = $S[$pS--]; 
      $j = $S[$pS--]; 
      for ($k = $i; $k < $j; $k++) 
       $output .= $words[$k] . " "; 
      $output .= $words[$k] . $lineBreak; 
     } 
     while ($j < $wsnum - 1); 
    } 
    else 
     $output = $input; 

    return $output; 
} 

?>

Answer 6

Вот версия Баш:

#! /bin/sh 
if ! [[ "$1" =~ ^[0-9]+$ ]] ; then 
    echo "Usage: balance <width> [ <string> ]" 
    echo " " 
    echo " if string is not passed as parameter it will be read from STDIN\n" 
    exit 2 
elif [ $# -le 1 ] ; then 
    LINE=`cat` 
else 
    LINE="$2" 
fi 

LINES=`echo "$LINE" | fold -s -w $1 | wc -l` 
MAX=$1 
MIN=0 

while [ $MAX -gt $(($MIN+1)) ] 
do 
    TRY=$(($MAX + $MIN >> 1)) 
    NUM=`echo "$LINE" | fold -s -w $TRY | wc -l` 
    if [ $NUM -le $LINES ] ; then 
     MAX=$TRY 
    else 
     MIN=$TRY 
    fi 
done 

echo "$LINE" | fold -s -w $MAX 

пример:

$ balance 50 "Now is the time for all good men to come to the aid of the party." 
Now is the time for all good men 
to come to the aid of the party. 

Требует 'складку' и 'туалет', которые, как правило, доступны, где установлен Баш.