Bọc từ cân bằng (Độ rách tối thiểu) trong PHP

Question

Tôi sẽ tạo một thuật toán bọc từ trong PHP. Tôi muốn chia nhỏ các đoạn văn bản (cụm từ ngắn) trong n các dòng tối đa m ký tự (n không được cung cấp, vì vậy sẽ có nhiều dòng nếu cần). Tính đặc thù là độ dài của dòng (trong ký tự) phải cân bằng nhiều nhất có thể trên các dòng.

Ví dụ về nhập văn bản:

How to do things 

đầu ra sai (đây là hành vi word-wrap bình thường), m = 6:

How to 
do 
things 

đầu ra mong muốn, luôn luôn m = 6:

How 
to do 
things 

Doe Có ai có gợi ý hay hướng dẫn về cách thực hiện chức năng này không? Về cơ bản, Tôi đang tìm kiếm thứ gì đó để viết cụm từ ngắn gọn trên hai hoặc ba (càng nhiều càng tốt) các dòng có độ dài bằng.

---

Cập nhật: Có vẻ như tôi đang tìm kiếm chính xác cho một Minimum raggedness word wrap algorithm. Nhưng tôi không thể tìm thấy bất kỳ thực hiện trong một ngôn ngữ lập trình thực sự (bất cứ ai, sau đó tôi có thể chuyển đổi nó trong PHP).

---

Cập nhật 2: Tôi bắt đầu một bounty cho việc này. Có thể không tồn tại bất kỳ sự thực thi nào của thuật toán rách rưới tối thiểu trong bất kỳ ngôn ngữ thủ tục nào không? Tôi cần một thứ gì đó được viết theo cách có thể được dịch sang hướng dẫn thủ tục. Tất cả tôi có thể tìm thấy bây giờ chỉ là một bounch của (generic) phương trình mà tuy nhiên cần một thủ tục tìm kiếm tối ưu. Tôi cũng sẽ biết ơn về việc triển khai mà chỉ có thể ước tính thuật toán tìm kiếm tối ưu đó.

Answer 1

nhanh chóng và dơ bẩn, trong 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; 
} 

Test:

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

CHỈNH SỬA: chỉ cần xem trang wikipedia để có từ bọc rách rưới tối thiểu. thuật toán thay đổi đến một nhất định (với hình phạt squared)

Answer 2

Justin's link đến Knuth's Breaking Paragraphs Into Lines là câu trả lời phù hợp nhất trong lịch sử tốt nhất. (Các hệ thống mới hơn cũng áp dụng các kỹ thuật microtypography chẳng hạn như độ rộng ký tự, kerning, v.v., nhưng nếu bạn chỉ đơn giản là tìm kiếm văn bản đơn thuần, thì các phương pháp tiếp cận bổ sung này sẽ không giúp ích.)

Nếu bạn chỉ muốn để giải quyết vấn đề, tiện ích fmt(1) được cung cấp trên nhiều hệ thống Linux của Quỹ Phần mềm Tự do thực hiện một biến thể của thuật toán Knuth cũng cố gắng tránh ngắt dòng ở cuối câu.Tôi đã viết đóng góp của bạn và một tấm gương lớn, và chạy chúng thông qua fmt -w 20 để buộc dòng 20 ký tự:

$ 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. 

Kết quả trông đẹp hơn nhiều nếu bạn cho phép nó trở thành mặc định 75 ký tự chiều rộng cho đầu vào không tầm thường:

$ 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 phiên bản:

// 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; 
} 

Output 1:

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

Output 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 

Kết quả 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

Tôi nghĩ cách đơn giản nhất để xem xét - là với sự lặp lại giữa các giới hạn

Ví dụ:

/** 
* 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]; 
} 

Với đầu vào "làm thế nào để làm những việc"

nó ra

How 
to do 
things 

Với đầu vào "Mary có một con chiên nhỏ"

nó ra

 
Mary had a 
little lamb 

Được cung cấp đầu vào "Đoạn cực dài này đã được viết để chứng minh cách thức chương trình fmt(1) xử lý các đầu vào dài hơn. Khi kiểm tra đầu vào, bạn không muốn chúng quá ngắn, cũng không quá dài, vì chất lượng của chương trình chỉ có thể được xác định khi kiểm tra nội dung phức tạp. The quick brown fox jumps over the lazy dog. Quốc hội sẽ không đưa ra luật tôn trọng việc thành lập tôn giáo, hoặc cấm việc thực hiện các tôn giáo đó; hoặc rút gọn tự do ngôn luận, hoặc báo chí; . Hoặc quyền của người dân một cách hòa bình để lắp ráp, và kiến ​​nghị Chính phủ cho những nỗi bất bình ", và giới hạn trong 75 ký tự chiều rộng tối đa, nó kết quả đầu ra:

 
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

Tôi đã thực hiện trên các dòng cùng Alex, mã hóa thuật toán Wikipedia, nhưng trực tiếp trong PHP (một bài tập thú vị với tôi) Hiểu cách sử dụng hàm chi phí tối ưu f (j), tức là phần 'lặp lại', không phải là rất dễ dàng. mã được nhận xét tốt.

/** 
* 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

Đây là một phiên bản bash:

#! /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 

dụ:

$ 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. 

Đòi hỏi 'gấp' và 'wc' mà thường có sẵn nơi bash được cài đặt.