4 ms·

"The algorithm uses language-specific patterns in order to decide the preferred position for hyphenation. The engine then selects line breaks so as to make para

• dmlorenzetti 17y ago
  TeX (and hence LaTeX) does this.
  • gjm11 17y ago
    Either you're confused or I am. TeX and LaTeX are not aware of rivers. (Nor of lakes, though I would guess that the TeX line-breaking algorithm makes lakes very rare.) The comment you were replying to was saying that TeX does do hyphenation and line-breaking cleverly but doesn't detect rivers and lakes; it looks like maybe you thought it was saying that TeX doesn't do any of those things.
    • dmlorenzetti 17y ago
      I wasn't confused. I was wrong. I have an old TeX reference which suggests TeX pays attention to rivers. But based on your challenge, I skimmed through the description of the line-break algorithm in Knuth's "The TeXbook," and found nothing about rivers. (There is a bit of attention paid to making sure adjacent lines are compatible in terms of how squashed or spread out they are, but apparently nothing that tries to catch rivers.)
      • gjm11 17y ago
        Right. I think the TeXbook explicitly says that TeX doesn't know about rivers, but I forget; anyway, I've read the code, and there is no river detection in TeX.
• vault_ 17y ago
  Are there any software packages out there that do? Word doesn't, and I don't think that InDesign does.
  • by 17y ago
    I learned the terms from somebody who is involved in book publishing. I do not know much about publishing software. It struck me that it might be an interesting unsolved problem to automatically reduce the incidence of lakes and rivers.
• Silhouette 17y ago
  There is no explicit check, but a natural consequence of the mathematical optimisation problem that this algorithm solves is that rivers are unlikely.
  • by 17y ago
    I tried to read the paper, but it's behind a paywall so I am unable to confirm whether it gives any possible mechanism for solving rivers. But it seems highly unlikely because the alignment of word gaps from one line to the next, the cause of rivers, is entirely unrelated to getting nice word spacing on the lines themselves. The abstract makes no mention of trying to solve the problem of rivers or lakes. How does the algorithm solve rivers?
    • Silhouette 17y ago
      As I mentioned before, there is nothing explicit about "solving" rivers in the algorithm. The rarity of rivers is just a welcome side-effect of the mathematical formulation. The kind of river that is distracting is typically caused by an unfortunate combination of two things: having wide spaces between words, and having them aligned closely enough from one line to the next that the white space they cause joins up visually. TeX's hyphenation and justification algorithm is, in simple terms, trying to optimise for even spacing throughout a paragraph, with a bias towards using the natural spacing or as close to it as possible. Notably, it can do this by increasing or decreasing the space between words. In this environment, you are much less likely to get wide spaces in the first place than if you have a typical word processor algorithm that justifies line-by-line and only by increasing space. If the spaces aren't as wide, then they are less distracting in themselves, and there is less scope for them to overlap for several lines to form the long rivers that are so distracting to the reader. This doesn't mean that rivers are impossible using a TeX-style algorithm. It is just less likely to happen, and probably less noticeable if it does, than with a line-based H&J algorithm.
      • by 17y ago
        I see, thank you.