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 excerpt:
<-- 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]
