6 ms·

Note: 2007. Knuth-Plass line-breaking is cool, and it's something I've looked at a fair bit for my own website, because it would likely help with fixing blatan

by gwern 5y ago

Note: 2007. Knuth-Plass line-breaking is cool, and it's something I've looked at a fair bit for my own website, because it would likely help with fixing blatant nastiness on mobile browsers (where you get a lot of stretched lines or large gaps, particularly when stuff like blockquotes or lists narrow the width further). But every HTML/JS version of Knuth-Plass (and/or microtypography adjusting spacing/glyph size) seems to be a performance abomination and fragile†, and web browsers have clearly signaled that they are never going to provide better native typesetting (even as their greedy linebreaking means that it doesn't work as well as you'd assume to insert linebreaking/nobreak character entities to try to control it). † One person a few years ago did a cool approach where they precomputed every possible screen width to provide the exact layout tailored to a reader's screen width, since there's only a few thousand reasonable screen widths & K-P screams... And their demo is already broken in browsers. Bleh.

copperx 5y ago
Knuth-Plass is missing from all e-readers, but is built into the most popular software for typesetting books, InDesign. Adobe even created a streaming version of the algorithm. It's mind-boggling that e-readers don't implement it. Hell, even Internet Explorer used Knuth-Plass to justify text.
- chrismorgan 5y ago
  > even Internet Explorer used Knuth-Plass to justify text I haven’t heard of this before, and I don’t believe it’s at all correct. Searching, I’m finding only https://elliotjaystocks.com/blog/justification-hyphenation/ https://elliotjaystocks.com/blog/justification-hyphenation/ to be relevant: “Internet Explorer, which seems to use the Knuth / Plass algorithm, or an approximation of it, enabled through the text-justify: newspaper CSS property.” `text-transform: newspaper` is nothing like Knuth-Plass: rather, it was what is currently spelled `text-transform: inter-character`, which is a terrible idea for English.
  - gwern 5y ago
    > `text-transform: newspaper` is nothing like Knuth-Plass According to Bramstein, who seems to be the source for this claim, after he implemented K-P in browsers, he checked IE's 'newspaper' against his own implementation, and it delivered almost identical results: https://news.ycombinator.com/item?id=5189258 https://news.ycombinator.com/item?id=5189258 >> 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.
    - chrismorgan 5y ago
      Ah hah, good to know; I didn’t find that comment in my search. Seems odd to me because the main screenshot I’ve seen <https://www.mediumwell.com/wp-content/uploads/newsprint-justify-example.gif https://www.mediumwell.com/wp-content/uploads/newsprint-just...> exhibits identical line-breaking to greedy, just with inter-character spacing being done. On reflection, the narrow width combined with lack of hyphenation does make that a rather pathological case where there’s not much for Knuth-Plass to work with, beyond perhaps lines 14–16. (I haven’t actually tried Knuth-Plass on it.) Well, even if it did activate Knuth-Plass, it also enabled inter-character spacing which is rather bad for English and a most curious combination. I’m almost tempted to get out a VM with old IE (I’m guessing it was removed by IE9, though I suppose I could check it on IE11 first which I do have ready access to) and compare it more.
leephillips 5y ago
“One person a few years ago did a cool approach where they precomputed every possible screen width” I realize if you remembered a link or name you'd probably have mentioned it, but just in case, do you...?
- Jtsummers 5y ago
  Possibly this: https://mpetroff.net/2020/05/pre-calculated-line-breaks-for-html-css/ https://mpetroff.net/2020/05/pre-calculated-line-breaks-for-...
  - leephillips 5y ago
    Looks like it. Thanks!
thechao 5y ago
That’s unfortunate; I think the KP line breaking algorithm is one of my favorites. Obviously, it’s not as fast as greedy, but it is “mostly” linear. Here’s my notes & some C++ code… https://github.com/jaroslov/knuth-plass-thoughts/blob/master/plass.md https://github.com/jaroslov/knuth-plass-thoughts/blob/master...
chrismorgan 5y ago
You can’t precompute the layout as in your † (that is, your results will be wrong), because you don’t know ahead of time what fonts will be used.
- leephillips 5y ago
  The technique requires a web font.
  - chrismorgan 5y ago
    You can’t depend on web fonts. They may fail to load for a variety of reasons, or be overridden for reasons of accessibility or user preference. In short, you can’t get it right in pure CSS, and once you require JavaScript anyway, there isn’t at least as much point in precomputing it.
chrismorgan 5y ago
> web browsers have clearly signaled that they are never going to provide better native typesetting I don’t think that’s accurate. There’s enough interest that the CSS Text Module Level 4 draft expands the white-space CSS property to cover more line-breaking stuff, including a text-wrap property that lets you control the line-breaking algorithm <https://drafts.csswg.org/css-text-4/#text-wrap https://drafts.csswg.org/css-text-4/#text-wrap>; to be sure, no browser has implemented it yet, and not everything that’s in such drafts ever gets implemented, but it shows interest at the least. Firefox also has a long-standing bug for it, https://bugzilla.mozilla.org/show_bug.cgi?id=630181 https://bugzilla.mozilla.org/show_bug.cgi?id=630181, where you can see definite interest from key Firefox developers (so long as the performance hazards are managed), though they personally are unlikely to implement it, so it’s most likely to happen if someone external decides to put effort into it.
- gwern 5y ago
  It's been 8+ years since text-wrap was added to the spec, and not a single maintained browser on the face of the earth supports that or K-P AFAICT, or has any concrete plans to do so, or has any prototyped code. (Nor is this at all unusual when it comes to typography in web browsers; it took how many years after release for desktop Chrome to get something as basic as hyphenation?) I'm not going to hold my breath.

by gwern 5y ago

copperx 5y ago

Knuth-Plass is missing from all e-readers, but is built into the most popular software for typesetting books, InDesign. Adobe even created a streaming version of the algorithm. It's mind-boggling that e-readers don't implement it. Hell, even Internet Explorer used Knuth-Plass to justify text.

chrismorgan 5y ago
> even Internet Explorer used Knuth-Plass to justify text I haven’t heard of this before, and I don’t believe it’s at all correct. Searching, I’m finding only https://elliotjaystocks.com/blog/justification-hyphenation/ https://elliotjaystocks.com/blog/justification-hyphenation/ to be relevant: “Internet Explorer, which seems to use the Knuth / Plass algorithm, or an approximation of it, enabled through the text-justify: newspaper CSS property.” `text-transform: newspaper` is nothing like Knuth-Plass: rather, it was what is currently spelled `text-transform: inter-character`, which is a terrible idea for English.
- gwern 5y ago
  > `text-transform: newspaper` is nothing like Knuth-Plass According to Bramstein, who seems to be the source for this claim, after he implemented K-P in browsers, he checked IE's 'newspaper' against his own implementation, and it delivered almost identical results: https://news.ycombinator.com/item?id=5189258 https://news.ycombinator.com/item?id=5189258 >> 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.
  - chrismorgan 5y ago
    Ah hah, good to know; I didn’t find that comment in my search. Seems odd to me because the main screenshot I’ve seen <https://www.mediumwell.com/wp-content/uploads/newsprint-justify-example.gif https://www.mediumwell.com/wp-content/uploads/newsprint-just...> exhibits identical line-breaking to greedy, just with inter-character spacing being done. On reflection, the narrow width combined with lack of hyphenation does make that a rather pathological case where there’s not much for Knuth-Plass to work with, beyond perhaps lines 14–16. (I haven’t actually tried Knuth-Plass on it.) Well, even if it did activate Knuth-Plass, it also enabled inter-character spacing which is rather bad for English and a most curious combination. I’m almost tempted to get out a VM with old IE (I’m guessing it was removed by IE9, though I suppose I could check it on IE11 first which I do have ready access to) and compare it more.

leephillips 5y ago

“One person a few years ago did a cool approach where they precomputed every possible screen width” I realize if you remembered a link or name you'd probably have mentioned it, but just in case, do you...?

Jtsummers 5y ago
Possibly this: https://mpetroff.net/2020/05/pre-calculated-line-breaks-for-html-css/ https://mpetroff.net/2020/05/pre-calculated-line-breaks-for-...
- leephillips 5y ago
  Looks like it. Thanks!

thechao 5y ago

That’s unfortunate; I think the KP line breaking algorithm is one of my favorites. Obviously, it’s not as fast as greedy, but it is “mostly” linear. Here’s my notes & some C++ code… https://github.com/jaroslov/knuth-plass-thoughts/blob/master/plass.md https://github.com/jaroslov/knuth-plass-thoughts/blob/master...

chrismorgan 5y ago

You can’t precompute the layout as in your † (that is, your results will be wrong), because you don’t know ahead of time what fonts will be used.

leephillips 5y ago
The technique requires a web font.
- chrismorgan 5y ago
  You can’t depend on web fonts. They may fail to load for a variety of reasons, or be overridden for reasons of accessibility or user preference. In short, you can’t get it right in pure CSS, and once you require JavaScript anyway, there isn’t at least as much point in precomputing it.

chrismorgan 5y ago

> web browsers have clearly signaled that they are never going to provide better native typesetting I don’t think that’s accurate. There’s enough interest that the CSS Text Module Level 4 draft expands the white-space CSS property to cover more line-breaking stuff, including a text-wrap property that lets you control the line-breaking algorithm <https://drafts.csswg.org/css-text-4/#text-wrap https://drafts.csswg.org/css-text-4/#text-wrap>; to be sure, no browser has implemented it yet, and not everything that’s in such drafts ever gets implemented, but it shows interest at the least. Firefox also has a long-standing bug for it, https://bugzilla.mozilla.org/show_bug.cgi?id=630181 https://bugzilla.mozilla.org/show_bug.cgi?id=630181, where you can see definite interest from key Firefox developers (so long as the performance hazards are managed), though they personally are unlikely to implement it, so it’s most likely to happen if someone external decides to put effort into it.

gwern 5y ago
It's been 8+ years since text-wrap was added to the spec, and not a single maintained browser on the face of the earth supports that or K-P AFAICT, or has any concrete plans to do so, or has any prototyped code. (Nor is this at all unusual when it comes to typography in web browsers; it took how many years after release for desktop Chrome to get something as basic as hyphenation?) I'm not going to hold my breath.