- From: Liam R E Quin <liam@w3.org>
- Date: Mon, 13 Oct 2014 00:52:16 -0400
- To: Zack Weinberg <zackw@panix.com>
- Cc: "Tab Atkins Jr." <jackalmage@gmail.com>, Bobby Mozumder <mozumder@futureclaw.com>, "Lewis, Eric" <eric.lewis@nytimes.com>, www-style list <www-style@w3.org>
On Sun, 12 Oct 2014 13:54:20 -0400 Zack Weinberg <zackw@panix.com> wrote: > All the optimal-balancing algorithms I know about are resilient in the > presence of a "this paragraph is too large, split it arbitrarily into > reasonably-sized chunks" heuristic. The original TeX algorithm had non-polynomial behaviour on the number of words in the paragraph, so that would be a "no" :-) > (One of these years I'll get around to implementing Knuth-Plass > linebreaking in Servo to see how it goes.) The original Knith-Plass line-breaking algorithm isn't actually all that good for a browser, because the underlying assumption is that the author is there to make corrections and guide the algorithm in edge cases. Anyone who has used TeX and seen messages like "underfull hbox" has seen problems. Their paper also shows that their algorithm is NP-complete. There are modified algorithms that work better. In practice, an balancing first-fit algorithm that averages out over a running n-line window is almost as good in most cases and doesn't have the bad edge-case behaviour - it's also massively faster, in algorithmic complexity linear in the number of words. I described it in a message to this list a year or two ago. However, the "balance text" Adobe suggest does seem better for headlines. Liam > -- Liam Quin - XML Activity Lead, W3C, http://www.w3.org/People/Quin/ Pictures from old books: http://fromoldbooks.org/
Received on Monday, 13 October 2014 04:52:21 UTC