Re: Flexible lyric alignment

[Jean Abou Samra]

Le 16/11/2022 à 10:05, Werner LEMBERG a écrit :
> I draw my idea from LaTeX, for example handling multi-page tables (see
> the 'longtable' package).


I looked at the documentation
(https://distrib-coffee.ipsl.jussieu.fr/pub/mirrors/ctan/macros/latex/required/tools/longtable.pdf).
The footnote on the first page says

  The new algorithm for aligning ‘chunks’ of a table used in
  version 4 of this package was devised coded and documented
  by David Kastrup.

LOL.

Obviously, David will be able to comment better than me.
But skimming the documentation of the package, it looked
more like the package had to use this technique to work
around the limitations of the extremely limited TeX
programming environment than to implement a smart
algorithm. Am I wrong here?



> * In the first pass, typeset everything without stuff marked for a
>    follow-up pass.


Namely, typeset all notes? But how do you take into account
the constraints from lyrics here? That is the whole problem.


----


For what it's worth, the optimization problem can be formulated
as a springs&rods problem:

Add a problem variable for each lyric word.

For each lyric word W, if C is W's column, add a rod
from C to W to ensure W is not too far on the left of
W. Also add a rod from W to C to ensure W does not go
too far to the right.

Add all other rods in the usual way (with skylines). Now
rods may involve both column variables and lyric variables.

Leave springs as they are (between columns only).

Issue: this is not a springs&rods problem that the existing
Simple_spacer will be able to solve (I didn't try, but I'm
pretty sure). Simple_spacer's algorithm starts by stretching
the line a lot, and iteratively compresses it. This implicitly
assumes that stretching the line a lot will make rod constraints
satisfied, i.e., there are no "reverse rods" (columns are
ordered, and all rods are from a column to a column with a
higher rank). The problems in the form above do have reverse
rods.

So the problem is essentially finding a method to solve
springs&rods problems with this kind of reverse rods
allowed.

Now, springs&rods optimization is close to quadratic
programming, which is well-studied, but in my understanding
so far, it is not exactly quadratic programming (?) due to
the fact that springs are allowed to have different strengths
for stretching and compressing.

Maybe one can find a different algorithm for Simple_spacer.
Potentially, its start could be stretching the columns and
putting each lyric word exactly on the column. Then what?
That remains to be seen.

Maybe one can adapt existing QP algorithms (caveat: a comment
in simple-spacer.cc claims that it's "much simpler and much
much faster than full-scale constrained QP").

Maybe there are papers that I haven't read that provide solutions
or ideas for this problem.

Maybe I am just being blind to an obvious solution, too.

Another idea: instead of using two rods for describing
the relationship between a lyric word and its column,
use a spring with a somewhat large force, which allows
lyrics to be completely "disconnected" from their column
but makes it unlikely.

I may well have said wrong things and I am not seeing clearly
in the frame of the problem yet. Also, adding variables for
lyrics would be a deep change in the C++ core.

Jean

OpenPGP_signature
Description: OpenPGP digital signature