News for hackers. Stuff that matters.
Re:Balancing text for better readability by dpcx on Friday February 08, 2013 @10:15AM (#5188204)
Why not just use the Knuth-Plass algorithm as implemented in http://www.bramstein.com/projects/typeset/?
Re:Balancing text for better readability by nimbupani on Friday February 08, 2013 @11:32AM (#5188642)
Bram Stein works for Adobe :) We did look into it but it was not fast enough for the needs of browsers.
Re:Balancing text for better readability by pdog on Friday February 08, 2013 @11:51AM (#5188759)
The run-time of that particular implementation of the Knuth-Plass algorithm is quadratic in paragraph length, which is too slow for web browsers (which might have to deal with very long paragraphs). However, the algorithm can be implemented to run in O(n) for large n, or O(n log n) with smaller fixed constants. Though you might have some issues with the line breaks made by the browser.
Re:Balancing text for better readability by bramstein on Friday February 08, 2013 @01:15PM (#5189258)
I'm not totally sure, but I think the linear time papers I've read sacrifice some of the aspects of the original Knuth and Plass algorithm. I think some of those are going to be necessary to properly implement the Knuth and Plass algorithm in browser (also, floats are going to be interesting.)

The performance isn't actually that bad, I can perform line breaking in JavaScript on some very large documents, with the only performance bottleneck being DOM node creation (which native implementations won't suffer from.) If necessary the linebreaking could also be done incrementally, with a first first-fit pass and then the Knuth and Plass algorithm.

I could be mistaken, but I'm fairly certain Internet Explorer implements the Knuth and Plass algorithm when using `text-justify: newspaper`. Unfortunately, I can't check because it isn't open source. The output however is pretty much identical to what my JavaScript version generates, so I'm inclined to believe it is the Knuth and Plass algorithm.

Re:Balancing text for better readability by slurgfest on Friday February 08, 2013 @10:54AM (#5188412)
None of Knuth's extensive work on typography seems to be well respected among designers (I'd love to be proven wrong about that).
Re:Balancing text for better readability by _delirium on Friday February 08, 2013 @11:34AM (#5188649)
InDesign implements a version of Knuth-Plass, so a lot of designers use it, whether they know about it or not.
Re:Balancing text for better readability by taeric on Friday February 08, 2013 @11:22AM (#5188570)
Not respected, or not known?

Edit: I'm seriously asking here, if anyone knows.

Re:Balancing text for better readability by bramstein on Friday February 08, 2013 @01:18PM (#5189271)
As mentioned above, Knuth's algorithms are implemented in many professional typesetting and layout applications. I think the people implementing those applications have great respect for Knuth (and Plass.)

My impression is that the users of those programs are unfamiliar with the algorithms used, so I think it is the latter.

Re:Balancing text for better readability by taeric on Friday February 08, 2013 @01:36PM (#5189369)
Awesome, thanks! I foolishly forgot to see if there were siblings to my post. (I try and keep a handle on discussions I'm in with the "threads" link.) So, yeah, apologies for missing those posts.
Re:Balancing text for better readability by bramstein on Friday February 08, 2013 @01:02PM (#5189171)
I'm really excited about this. While it is not the Knuth and Plass algorithm, it takes one of the nice features of it and proposes a simple algorithm to implement it. Implementing it should only be a minor adjustment to the text layout algorithms of browser rendering engines, and if implemented correctly it should not cause any reflows, only a repaint.