12
$\begingroup$

There is a linear time algorithm for breaking text evenly into lines of maximum width. It uses SMAWK (or Knuth & Plass) and "evenly" means: http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness

Is there an algorithm or a concave cost function for algorithm above which would take into account the number of lines I would like the text break into, instead of the maximum line width? Also in linear time?

In other words, I'm looking for a line breaking (or paragraph formation, or word wrapping) algorithm where the input is the desired number of lines, not the desired line width.

Just to describe a practically unusable approach: There are N words and N-1 spaces in-between each word pair, M is the desired number of lines (M <= N). After each space there might be at most one (possibly zero) line-break. Now, the algorithm would try to place the breaks in each possible combination, calculating the "raggedness" and return the best one. How to do it much faster?

Also, does such a problem have a name? What "family" of problems does it belong to? (E.g. "bin packing") If I wouldn't need the perfectly optimal solution, just a very good one, is it possible to solve it much faster? (some form of heuristics could be usable, if for a given input there were always the same, possibly sub-optimal, solution).

Update

Chandra Chekuri suggested bellow "a problem in Kleinberg and Tardos chapter on dynamic programming". It was a good read but it deals with line breaking based on width rather than line count. It might be adaptable to this problem which is something I'm trying to figure out now. Here is a good link to the solution, they even claim to solve it in linear time: http://web.media.mit.edu/~dlanman/courses/cs157/HW5.pdf

Also, there is a chapter "8.5 The Partition Problem" in The Algorithm Design Manual by Skiena which seems to be exactly on-topic, I'm still reading it, tough. (Unfortunately, from what I understood it has quadratic time complexity)

Improve this question
$\endgroup$
15
  • 5
    $\begingroup$ Nice dynamic programming problem! I might use it as homework in my class next semester. $\endgroup$
    – Jeffε
    Feb 26, 2012 at 15:38
  • 3
    $\begingroup$ @JɛffE if you want to use it for a homework problem, better close the question before the answer gets published on the web. $\endgroup$
    – Joe
    Feb 27, 2012 at 7:58
  • 1
    $\begingroup$ @Joe: as someone really interested in the answer I would prefer the question to be answered, rather than closed. $\endgroup$
    – Ecir Hana
    Feb 27, 2012 at 9:22
  • 2
    $\begingroup$ @Joe: it's not a homework, I don't even study CS. What the "homework level" goes, I find it very interesting that some people cannot even image how to solve a problem, while other people consider it "homework level". That said, the answer could be erased in a week or sent to my email for example. And I would be thankful for not so "full answer", as well. $\endgroup$
    – Ecir Hana
    Feb 29, 2012 at 9:43
  • 3
    $\begingroup$ There is a problem in Kleinberg and Tardos chapter on dynamic programming which is to format in such a way as to minimize the sum of the slacks in the lines. $\endgroup$
    – Chandra Chekuri
    Mar 4, 2012 at 0:33

2 Answers 2

Reset to default
4
$\begingroup$

If you can compute the raggedness of a line without knowing anything about the other lines, then you can model the problem as finding a minimum-weight $M$-link path in a graph. With concave integer weights for edges, there is an algorithm that solves the problem in $O(N \log U)$ time, where $U$ is the largest absolute edge weight. Another algorithm solves the problem in $N 2^{O(\sqrt{\log M \log \log N})}$ time for any concave edge weights, assuming $M = \Omega(\log N)$. Both algorithms assume that you can compute the weight of an edge in constant time.

You could also use binary search to find a line width such that SMAWK uses $M$ lines with it. In some cases, this algorithm does not guarantee a solution with exactly $M$ lines, however.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I'm very sorry but I don't think I follow. Is "edge weight" the length of a word? How does the "graph" look like? Is it just a linear graph where nodes are the breakpoints and edges are the lengths of words? And this "M-link path" breaks it up so that the resulting segments have minimal sum of edges? But most importantly, in the very first sentence - I'm not sure if I can compute the raggedness independently. It roughly is the difference between the longest line and the actual line so I need to know something about the other lines, no? More so for the last line, please see 15th comment above. $\endgroup$
    – Ecir Hana
    Mar 7, 2012 at 23:41
  • $\begingroup$ @Ecir: We are looking for the minimum-weight path having exactly $M$ edges from node $1$ to node $N+1$. Having edge $(i,j)$ in the path means that words $i$ to $j-1$ form a single line, and the weight of the edge is the contribution of that line to the raggedness of the solution. $\endgroup$
    – Jouni Sirén
    Mar 8, 2012 at 13:42
  • $\begingroup$ @Ecir: Essentially all algorithms based on dynamic programming require that you can compute the raggedness of a line independently. If that is not the case, you might want to use something like my second idea: guess a line width, compute a solution based on that width, and iterate to find better solutions. $\endgroup$
    – Jouni Sirén
    Mar 8, 2012 at 13:59
  • $\begingroup$ thank you for the explanation. Please, I have two more question: when using the "binary search" option, is there anything I can do to guarantee the number M of lines? If I add small random epsilon to each line width so there would be no lines with the same width, I could gain more resolution over the placing of breaks. $\endgroup$
    – Ecir Hana
    Mar 10, 2012 at 17:53
  • $\begingroup$ And in the case of "M-link path", both papers mention that "it is easy to show that the minimum K-link path can be computed in O(nK) time" - do you perhaps know what do they mean? I couldn't find any further information on it. The problem is, those papers are a tiny bit too complicated for my little head so I'm trying to find more information, an implementation maybe, ... $\endgroup$
    – Ecir Hana
    Mar 10, 2012 at 17:53
-3
$\begingroup$

I don't know if this helps, but towards the end of this comment someone implements what you want in PHP; maybe you can figure out the algorithm.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ In the comment they just cut-off the remaining lines after the desired number of lines. They use PHP's wordwrap(), which in turn uses the greedy (i.e. no "evenly") algorithm for wrapping. Even then, the question remains how to "guess" the $width argument of wordwrap(). But thanks for the reply, anyway! $\endgroup$
    – Ecir Hana
    Mar 3, 2012 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.