Knuth and Plass line-breaking Revisited | Hacker News Reader

Knuth and Plass line-breaking Revisited

defoe.sourceforge.net

42 pointsbootload18 comments

I made a little Knuth/Plass experiment using canvas and opentype.js here: http://kevinmahoney.co.uk/document-experiment/

I find pagination much easier to read than scrolling.

It depends on the content. Reading a web page is different than reading a book.

I prefer pagination on a longer text that is meant to be read linearly but scrolling and scanning for a typical web page text.

But then I also prefer pagination on devices that actually are meant for it. Reading a book on a laptop screen is an inferior experience to reading it on paper or at least on a dedicated hardware e-book reader.

Jakob Nielsen's AlertBox columns suggest the same thing: http://www.nngroup.com/articles/how-users-read-on-the-web/ http://www.nngroup.com/articles/f-shaped-pattern-reading-web... http://www.nngroup.com/articles/website-reading/

Nevertheless, your experiment looks good although I had to make my browser windows smaller. Before I only saw one page because there is not enough text to trigger pagination.

Very nice. Have you compared your approach to simply enabling css-hyphens in eg: Firefox? The chrome team apparently doesn't believe in hyphenation, but for me just having a sane column width, normal left justified text -- and enabling hyphenation does wonders for the readability.

Hyphenation is nice, but the Knuth/Plass line breaking really helps too, even with left justified text. The 'first fit' algorithms browsers tend to use can leave some ugly and confusing artefacts.

> even with left justified text

Just to clarify: Do you mean just breaking on whole words, with no hyphenation looks better with Knuth/Plass than typical browser line breaking?

Somewhat related, VPRI discovered that the could get away with rather simple algorithms for typesetting, if letters were allowed to "place themselves" relative to other letters. I first saw it in the 2011 STEPS report, I believe:

http://www.vpri.org/pdf/tr2011004_steps11.pdf (Look for the "Text Objects" headline)

And I think this essay is a write-up that focuses more on just that part (the STEPS report is on the entire system):

http://www.vpri.org/pdf/m2010001_pobjects.pdf

I haven't really experimented with neither TeX/Knuth or the approach from STEPS -- but while java isn't all that well suited to object oriented programming (As in: allocating a full object for each letter) -- it might be worth taking a look at. If nothing else, RAM is still getting cheaper.

Is anyone aware of any line-breaking algorithm which penalises for rivers or typesetting algorithm which adjusts spacing to compensate for it.

I'm interested that rivers are such a concern of manual typesetting but I have never heard mention of it in typesetting algorithms.

It is a very difficult problem to solve see http://tex.stackexchange.com/questions/4507/avoiding-rivers-.... With TeX most of the time you will not see any rivers.

I understand that it is hard to integrate into TeX. I don't see how the general problem is hard to solve. Detecting rivers is not hard (maybe hard to do optimally) and adding a penalty accordingly is all the Knuth-Plass line breaking algorithm needs to avoid rivers.

Knuth-Plass is fundamentally a dynamic programming algorithm that depends on being able to say "If in the future I determine that there is a line break at point X, I know for certain that the way I should have broken the paragraph up until X is B", where B depends only on information before X.

If you're trying to avoid rivers, then based on information after point X you might find that your sequence of breaks B wasn't actually the best after all, because it ended up interacting badly with later spaces and producing rivers. So you can no longer prove that you've achieved a global optimum of the penalty function.

Of course you may be willing to take this hit and settle for non-optimum line-breaking (and you still might do better than an algorithm that doesn't take rivers into account at all).

If you google something like "latex rivers" or "latex microtype river" then you will see that there have been discussions, and some attempts. (Perhaps the issue is not as pronounced for mathematics, because of authors shying away from overly long paragraphs and because displayed equations break up paragraphs?)

Tangent: For those interested in the story... http://genius.com/The-brothers-grimm-the-frog-king-or-iron-h...

For a page on typesetting algorithms, by someone writing a typesetting system, this web page is typesetting garbage. It's not possible to increase the font size and have it wrap to the current window width. I'm stuck with microscopic, unreadable text.

This page is using default font size (as in not overriden via styles). To me it looks the same size as on HN. Also zoom function works in Chrome and font size is increased when zooming.

I often forget that lots of people read the web on their phone; perhaps that's you.

On my laptop Firefox: View/Page Styles/No Styles. Renders in glorious 1990s properly flowed, un-fucked-with text that you can do anything you want with.

I don't browse on my phone enough to know if that's available on a phone browser.

Can we somehow get this for MS Word and replace its justify algorithm?

I rarely use MS Words, but it might help to simply turn on hyphenation? Eg: http://wordribbon.tips.net/T006825_Hyphenating_Your_Document...

That said, pretty layout and MS Word isn't really something I expect to ever see...

uBlockOrigin blocks this. Possibly a better host exists. Just sayin'.

Reply on news.ycombinator.com