FYI, I now have the Knuth books "Digital Typography" and the 5-volume
"Computers & Typesetting", and have perused the relevant sections. The h & j
algorithm that I have been looking for can be found in Chapter 3 of "Digital
Typography". A brief history of line-breaking is included, as well as a
discussion of the theory, and the algorithm laid out in pretty good detail.
The mathematics of the solution will appeal to Rhett and probably several
others. The performance penalty is not so great as I thought. Here is an

<-- Start -->
But how is the computer to solve such a problem efficiently? When a given
paragraph has n optional breakpoints, there are 2^n ways to break it into
lines, and even the fastest conceivable computers could not run through all
such possibilities in a reasonable amount of time. In fact, the job of
breaking a paragraph into equal-sized lines as nicely as possible sounds
suspiciously like the infamous bin-packing problem, which is well known to
be NP-complete. Fortunately, however, each line will consist of contiguous
information from the paragraph, so the line-breaking problem is amenable to
the techniques of discrete dynamic programming; hence there is a reasonably
efficient way to attack it. We shall see that the optimum breakpoints can be
found in practice with only about twice as much computation as needed by the
traditional algorithm; the new method is sometimes even faster than the old,
when we consider the time saved by not needing to hyphenate so often....
<-- End -->

For any who are interested in line-breaking, I highly recommend at least
reading through this material. The book has a lot of other interesting
things as well, including a chapter (4) on bidi.

I'm hoping to be back into doing real work within a few days.

Victor Mote

To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, email: [EMAIL PROTECTED]

Reply via email to