5 ms·

So when are browsers going to abandon their greedy line breaking algorithm and implement Knuth/Plass or similar? In my opinion that is the single biggest probl

So when are browsers going to abandon their greedy line breaking algorithm and implement Knuth/Plass or similar? In my opinion that is the single biggest problem with web typography, and has been for years. Significantly more important than auto hyphenation. This has been a solved problem for 40 years (or at least 10–15, if we need to worry about fast performance for interactive use on a desktop computer). Should be table stakes for any software rendering long blocks of text.

chrisseaton 8y ago
Knuth/Plass seems to regularly need user input to resolve issues, at least in the TeX implementation - if that’s inherent can it be used in a browser?
- misterdoubt 8y ago
  For basic hyphenation of text paragraphs, it's been years since I felt the need to intervene in (La)Tex hyphenation. For typesetting more broadly, certainly. For making a clean right edge, no.
- svat 8y ago
  User intervention is (occasionally) needed in TeX only at its default settings, which are optimized for “rather than typeset any paragraph with a too-loose line, just give up and warn me loudly so I can take a look”. This makes sense for Knuth and his original goal of producing books. But it's not inherent; a combination of \tolerance=9999 (the default is 200) and \emergencystretch=\maxdimen makes it so that TeX will try to produce the best paragraph possible without requiring the user to intervene and rewrite the words. (Another alternative is to increase the stretchability and shrinkability of the interword glue.) And there will be no overfull boxes unless of course there's a single unhyphenatable word that by itself is longer than the line width. (LaTeX has a shortcut called \sloppy for achieving basically this, but the name scares people who don't understand the TeX algorithm.) Sometimes I think this should be the default: definitely the worst typesetting I've seen is in documents produced by people who ignored all the overfull box warnings; even the greedy algorithm of Word etc would be vastly preferable to that.)
pcwalton 8y ago
This comes up on every thread related to web typography, and the answer as always is that it's not possible in the general case, at least not with the specs as they are today. The biggest problem is that the CSS specification demands that a float be placed as high as possible (CSS 2.1 section 9.5.1, rule 8 [1]). But float ceilings can be anywhere in the middle of a paragraph. By its nature, Knuth line breaking means that any particular unit (word), and therefore any float ceiling, might not be as high as possible. In fact, the only algorithm that can be used in this case to satisfy the spec is the greedy one. Therefore, Knuth line breaking cannot be used on the Web. It might be possible to use Knuth line breaking in specific circumstances, such as when paragraphs have no floats. But not in general. [1]: https://www.w3.org/TR/CSS2/visuren.html#float-position https://www.w3.org/TR/CSS2/visuren.html#float-position
- jacobolus 8y ago
  There has to be some kind of method that does a better job balancing line widths than the naïve greedy version, and is compatible with whatever requirements browsers are subject to. Can someone hire some grad students to tackle this or something? We are talking about a significant proportion of all reading people do every day, all over the world. A pocket computer that can do hundreds of billions of arithmetic operations per second should be able to make text as pretty as an apprentice typesetter from 1600.
  - pcwalton 8y ago
    As stated before, the only algorithm that satisfies the constraint that floats must be placed as high as possible is the greedy one (or, to be more precise, any such algorithm must match the output of the greedy one).
    - sjwright 8y ago
      Why not just make this algorithm a non-default option (like hyphenation) and accept that when it's enabled floats may not be optimal?
SeanLuke 8y ago
I myself was struck by how ugly the hyphenation looked because the hyphens (and periods, and commas, and semicolons, and quotation marks) didn't poke outside the margin slightly to make the perceived margin straight. Even with a greedy line-by-line model as used in web browsers, LaTeX's \usepackage{microtype} ought to be fairly easy to implement.
nfoz 8y ago
Does anyone know what the relationship is between Knuth/Plass (or similar pretty-line-wrapping algos, if others exist), and Unicode? I know Unicode has their own line-wrap algorithm, but is it possible to use both?
- svat 8y ago
  What Unicode calls the “Unicode line breaking algorithm” (http://unicode.org/reports/tr14/ http://unicode.org/reports/tr14/ see “LB1” to “LB31”) is a method of determining “break opportunities”, the places where it is allowed to break a line of Unicode text. What the Knuth-Plass paper (http://www.eprg.org/G53DOC/pdfs/knuth-plass-breaking.pdf http://www.eprg.org/G53DOC/pdfs/knuth-plass-breaking.pdf) is about is a method of determining, given a paragraph along with its “break opportunities”, a partition of the paragraph into lines such that (a certain function of) the stretching/shrinking of spaces on the lines is minimized. So yes they can be used together. In fact the Unicode TeX engines like XeTeX and LuaTeX do so (I don't know how well they follow the Unicode specification intrinsically versus with the support of language-specific packages, but they seem to do the job).
  - nfoz 8y ago
    Awesome, thanks for the explanation!
- jahewson 8y ago
  Yes, the Unicode line breaking algorithm tells you how to compute where breaks are permitted. But it’s up to you to choose which breaks to actually use. What’s tricky is actually OpenType, because the length of a “word” can vary in complex ways depending on whether or not it is broken - much more complex than simple hyphens.
  - khaled 8y ago
    That happens in TeX as well, the width of “efficient” does not necessarily equal to the width of “ef” + “ficient” due to the presence of ligatures, and TeX deals with it by storing the width of the full ligature as well as the pre and post-line break widths (for all possible line breaks in the middle of paragraphs) and takes them into consideration when calculating line breaks. This can be generalized to any situation where line breaking changes the width of a chunk of the text.
kccqzy 8y ago
It's a solved problem for simple text, but a while ago someone on HN pointed out that (1) with other CSS layout features it has become an NP-complete problem; (2) even just for simple text, sophisticated line breaking algorithms usually have time complexities quadratic in the length of text and cannot be as fast as simple greedy which is linear, and the web is full of people eager to take advantage of this by sending your browser a huge paragraph and locking up your browser.

chrisseaton 8y ago

Knuth/Plass seems to regularly need user input to resolve issues, at least in the TeX implementation - if that’s inherent can it be used in a browser?

misterdoubt 8y ago
For basic hyphenation of text paragraphs, it's been years since I felt the need to intervene in (La)Tex hyphenation. For typesetting more broadly, certainly. For making a clean right edge, no.
svat 8y ago
User intervention is (occasionally) needed in TeX only at its default settings, which are optimized for “rather than typeset any paragraph with a too-loose line, just give up and warn me loudly so I can take a look”. This makes sense for Knuth and his original goal of producing books. But it's not inherent; a combination of \tolerance=9999 (the default is 200) and \emergencystretch=\maxdimen makes it so that TeX will try to produce the best paragraph possible without requiring the user to intervene and rewrite the words. (Another alternative is to increase the stretchability and shrinkability of the interword glue.) And there will be no overfull boxes unless of course there's a single unhyphenatable word that by itself is longer than the line width. (LaTeX has a shortcut called \sloppy for achieving basically this, but the name scares people who don't understand the TeX algorithm.) Sometimes I think this should be the default: definitely the worst typesetting I've seen is in documents produced by people who ignored all the overfull box warnings; even the greedy algorithm of Word etc would be vastly preferable to that.)

pcwalton 8y ago

This comes up on every thread related to web typography, and the answer as always is that it's not possible in the general case, at least not with the specs as they are today. The biggest problem is that the CSS specification demands that a float be placed as high as possible (CSS 2.1 section 9.5.1, rule 8 [1]). But float ceilings can be anywhere in the middle of a paragraph. By its nature, Knuth line breaking means that any particular unit (word), and therefore any float ceiling, might not be as high as possible. In fact, the only algorithm that can be used in this case to satisfy the spec is the greedy one. Therefore, Knuth line breaking cannot be used on the Web. It might be possible to use Knuth line breaking in specific circumstances, such as when paragraphs have no floats. But not in general. [1]: https://www.w3.org/TR/CSS2/visuren.html#float-position https://www.w3.org/TR/CSS2/visuren.html#float-position

jacobolus 8y ago
There has to be some kind of method that does a better job balancing line widths than the naïve greedy version, and is compatible with whatever requirements browsers are subject to. Can someone hire some grad students to tackle this or something? We are talking about a significant proportion of all reading people do every day, all over the world. A pocket computer that can do hundreds of billions of arithmetic operations per second should be able to make text as pretty as an apprentice typesetter from 1600.
- pcwalton 8y ago
  As stated before, the only algorithm that satisfies the constraint that floats must be placed as high as possible is the greedy one (or, to be more precise, any such algorithm must match the output of the greedy one).
  - sjwright 8y ago
    Why not just make this algorithm a non-default option (like hyphenation) and accept that when it's enabled floats may not be optimal?

SeanLuke 8y ago

I myself was struck by how ugly the hyphenation looked because the hyphens (and periods, and commas, and semicolons, and quotation marks) didn't poke outside the margin slightly to make the perceived margin straight. Even with a greedy line-by-line model as used in web browsers, LaTeX's \usepackage{microtype} ought to be fairly easy to implement.

nfoz 8y ago

Does anyone know what the relationship is between Knuth/Plass (or similar pretty-line-wrapping algos, if others exist), and Unicode? I know Unicode has their own line-wrap algorithm, but is it possible to use both?

svat 8y ago
What Unicode calls the “Unicode line breaking algorithm” (http://unicode.org/reports/tr14/ http://unicode.org/reports/tr14/ see “LB1” to “LB31”) is a method of determining “break opportunities”, the places where it is allowed to break a line of Unicode text. What the Knuth-Plass paper (http://www.eprg.org/G53DOC/pdfs/knuth-plass-breaking.pdf http://www.eprg.org/G53DOC/pdfs/knuth-plass-breaking.pdf) is about is a method of determining, given a paragraph along with its “break opportunities”, a partition of the paragraph into lines such that (a certain function of) the stretching/shrinking of spaces on the lines is minimized. So yes they can be used together. In fact the Unicode TeX engines like XeTeX and LuaTeX do so (I don't know how well they follow the Unicode specification intrinsically versus with the support of language-specific packages, but they seem to do the job).
- nfoz 8y ago
  Awesome, thanks for the explanation!
jahewson 8y ago
Yes, the Unicode line breaking algorithm tells you how to compute where breaks are permitted. But it’s up to you to choose which breaks to actually use. What’s tricky is actually OpenType, because the length of a “word” can vary in complex ways depending on whether or not it is broken - much more complex than simple hyphens.
- khaled 8y ago
  That happens in TeX as well, the width of “efficient” does not necessarily equal to the width of “ef” + “ficient” due to the presence of ligatures, and TeX deals with it by storing the width of the full ligature as well as the pre and post-line break widths (for all possible line breaks in the middle of paragraphs) and takes them into consideration when calculating line breaks. This can be generalized to any situation where line breaking changes the width of a chunk of the text.

kccqzy 8y ago

It's a solved problem for simple text, but a while ago someone on HN pointed out that (1) with other CSS layout features it has become an NP-complete problem; (2) even just for simple text, sophisticated line breaking algorithms usually have time complexities quadratic in the length of text and cannot be as fast as simple greedy which is linear, and the web is full of people eager to take advantage of this by sending your browser a huge paragraph and locking up your browser.