6 ms·

Knuth and Plass line-breaking Revisited

42 points by bootload 11y ago

maninalift 11y ago
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.
- jimhefferon 11y ago
  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?)
- yannis 11y ago
  It is a very difficult problem to solve see http://tex.stackexchange.com/questions/4507/avoiding-rivers-in-successive-lines-of-type http://tex.stackexchange.com/questions/4507/avoiding-rivers-.... With TeX most of the time you will not see any rivers.
  - qznc 11y ago
    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.
    - dfan 11y ago
      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).
SeanLuke 11y ago
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.
- domas 11y ago
  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.
- a3n 11y ago
  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.
kpmah 11y ago
I made a little Knuth/Plass experiment using canvas and opentype.js here: http://kevinmahoney.co.uk/document-experiment/ http://kevinmahoney.co.uk/document-experiment/ I find pagination much easier to read than scrolling.
- bhaak 11y ago
  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/how-users-read-on-the-web/ http://www.nngroup.com/articles/f-shaped-pattern-reading-web-content/ http://www.nngroup.com/articles/f-shaped-pattern-reading-web... http://www.nngroup.com/articles/website-reading/ 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.
- e12e 11y ago
  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.
  - kpmah 11y ago
    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.
    - e12e 11y ago
      > 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?
a3n 11y ago
uBlockOrigin blocks this. Possibly a better host exists. Just sayin'.
slowmovintarget 11y ago
Tangent: For those interested in the story... http://genius.com/The-brothers-grimm-the-frog-king-or-iron-henry-annotated/ http://genius.com/The-brothers-grimm-the-frog-king-or-iron-h...
hchenji 11y ago
Can we somehow get this for MS Word and replace its justify algorithm?
- e12e 11y ago
  I rarely use MS Words, but it might help to simply turn on hyphenation? Eg: http://wordribbon.tips.net/T006825_Hyphenating_Your_Document.html http://wordribbon.tips.net/T006825_Hyphenating_Your_Document... That said, pretty layout and MS Word isn't really something I expect to ever see...
e12e 11y ago
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 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 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.

42 points by bootload 11y ago

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.

jimhefferon 11y ago
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?)
yannis 11y ago
It is a very difficult problem to solve see http://tex.stackexchange.com/questions/4507/avoiding-rivers-in-successive-lines-of-type http://tex.stackexchange.com/questions/4507/avoiding-rivers-.... With TeX most of the time you will not see any rivers.
- qznc 11y ago
  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.
  - dfan 11y ago
    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).

SeanLuke 11y ago

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.

domas 11y ago
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.
a3n 11y ago
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.

kpmah 11y ago

I made a little Knuth/Plass experiment using canvas and opentype.js here: http://kevinmahoney.co.uk/document-experiment/ http://kevinmahoney.co.uk/document-experiment/ I find pagination much easier to read than scrolling.

bhaak 11y ago
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/how-users-read-on-the-web/ http://www.nngroup.com/articles/f-shaped-pattern-reading-web-content/ http://www.nngroup.com/articles/f-shaped-pattern-reading-web... http://www.nngroup.com/articles/website-reading/ 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.
e12e 11y ago
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.
- kpmah 11y ago
  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.
  - e12e 11y ago
    > 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?

a3n 11y ago

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

slowmovintarget 11y ago

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

hchenji 11y ago

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

e12e 11y ago
I rarely use MS Words, but it might help to simply turn on hyphenation? Eg: http://wordribbon.tips.net/T006825_Hyphenating_Your_Document.html http://wordribbon.tips.net/T006825_Hyphenating_Your_Document... That said, pretty layout and MS Word isn't really something I expect to ever see...

e12e 11y ago

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