Re: [Groff] Formatting algorithm, an experiment

[Ulrich Lauther]

On Wed, May 28, 2014 at 01:49:58PM +0200, Ulrich Lauther wrote:
> On Mon, Mar 31, 2014 at 07:44:07PM -0400, Peter Schaffter wrote:
> > Here's the bare bones version of the algorithm I was thinking of
> > when I proposed improving line formatting by getting groff to
> > shoulder the burden for some of the work we do manually.  It's
> > written out in brute-force pseudo-code; should be pretty clear.
> > 
> To get a feeling for formating alternatives I implemented
> a simplified version of the Knuth-Plass algorithm.
> 

Peter Schaffter did a first evaluation of my code and his response was quite 
positive.
He asked me to post the stuff to the list, to get more feedback, criticism, and
suggetions for improvement.

Please find below his message (together with my comments) and attached my code.

Cheers,

  ulrich
-------------------------------------------------------

On Fri, Jun 20, 2014 at 12:23:45PM -0400, Peter Schaffter wrote:
> Ulrich --
> 
> On Thu, Jun 19, 2014, Ulrich Lauther wrote:
> > Did you look at the code? Any comments?
> 
> Once again, apologies for the lag in getting back to you.  I have
> indeed looked at and run the code.  The results on my system confirm
> that runtime is no issue.  grepping 'out' returns "cpu time for
> solution 0.001".  Hard to complain about that!
> 
> Using a greedy algorithm to establish the upper bound for any gap in
> the dynamic programming solution strikes me as efficient, and would,
> I think, make good (partial?) use of existing groff code.  The
> actual formatter is much leaner than I imagined it would have to be,
> and the results are good.
> 
> For the fun of it, I converted the output of 'out' to real HR
> formatted text at .ll \w'\ 'u*100u and studied the output of groff's
> native formatting against the greedy algorithm output and the output
> of the dynamic programming solution, both rag right and justified
> (replacing 'out' .br's with .brp's for the latter).  The uniformity
> of wordspacing, even with your stripped down formatter and the
> artificiality of the tests, is impressive.
> 
> Mind you, as a typesetter, I can't help but feel the uniformity
> is actually too much; one of the list members--I forget who--once
> complained of the "painted on the page" look of TeX-formatted
> documents, and I guess we're of the same opinion.  

Well, I am by education an engineer and later on autodidactic mathematician,
so the fine points of typesetting are beyond me and I have to trust you there.

> Truth is, at
> screen-readable sizes, the KP final solution (sorry about joining
> those two words together, given the historical connotation) does,
> in fact, significantly enhance readability of the text.  Conjoining
> KP with the basic intra-/inter-word spacing heuristic I proposed
> a while ago would, I think, resolve the problem of excessive
> uniformity by introducing the kind of tiny aesthetic variations that
> make text sing rather than merely march across the page.
> 
Combining the two approaches was my initial idea when I started this.
I guess, the combined code would still be less complex than the original
KP-algorithm.

> I really do recommend you post this to the list and get other
> opinions. 

Yes, I can do that. Do you allow to include your mail in the posting,
to whet people appetite?

> And I'm wondering how far you want to go with this.  From
> the discussions of several months ago, it's clear that implementing
> KP in groff is top-of-the-list stuff for groffers, but we need
> someone with your obvious coding creativity to, if not implement the
> whole thing, at least head up that side of things.
> 
As I am retired, I could spend some time on this. However, I have no idea 
of the inner workings of groff and so far never looked at the code.
So if someone would provide a clean interface where my code could be plugged in 
...

> Cheers.
> 
        ulrich lauther

distribute.tgz
Description: application/tar-gz