2
$\begingroup$

I have seen a few standard hyphenation algorithms for non-monospaced fonts, where you are free to squeeze and separate words and letters, but I haven't seen any related to monospaced fonts specifically. Wondering if there are any good resources on the topic. Such as how to best properties to use when hyphenating a monospaced word, etc.

$\endgroup$
  • 2
    $\begingroup$ Presumably, the input to all of those algorithms is the text to be split, the dimensions of the page, and a table of character widths, "squeezabilities" and "stretchabilities". Why can't you just use that algorithm with the character widths all equal, and squeezing and stretching set to zero? Is it because they'd still intrinsically use variable-width spaces between words, and you can't set that to integer multiples of the character width? $\endgroup$ – David Richerby Jan 11 at 12:00
2
$\begingroup$

I assume you are asking about algorithms to decide where to split lines when formatting paragraphs, not about algorithms for deciding where it is legal to insert hyphens into a word?

All algorithms for this kind of problem go back to Knuth, Donald E.; Plass, Michael F. (1981), "Breaking paragraphs into lines", Software: Practice and Experience 11 (11): 1119–1184, doi:10.1002/spe.4380111102, which is also described in this entry on tex.stackexchange: https://tex.stackexchange.com/a/109818/28084.

The key is to define an objective function and then come up with an efficient algorithm for optimizing the objective function. Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 3/e, 2009 gives a super-simplified version in problem 15-4 (page 405) that asks you to minimize the objective function "sum of cubes of number of extra spaces required on each line" using an efficient dynamic programming formulation.

In Knuth and Plass they demonstrate that a bunch of variants of the objective function (including adding a linear penalty for each hyphenation break that is added, and accounting for the extra space consumed by the hyphen) don't require you to go beyond the efficient dynamic programming formulation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.