Re: Paragraph Wrapping

Path	csiph.com!news.mixmin.net!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.programming
Subject	Re: Paragraph Wrapping
Date	Fri, 27 Jan 2023 01:22:19 +0000
Organization	A noiseless patient Spider
Lines	20
Message-ID	<87o7qkwz3o.fsf@bsb.me.uk> (permalink)
References	<wrap-20230126195034@ram.dialup.fu-berlin.de>
MIME-Version	1.0
Content-Type	text/plain
Injection-Info	reader01.eternal-september.org; posting-host="60014a0063bb2d5830bbe2489c026e03"; logging-data="1497578"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18OYSJBojVELvS9aiNG7vmTA8AU8pySwX8="
User-Agent	Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux)
Cancel-Lock	sha1:od94sYCWNOuQu9VrB5diaB+KWvM= sha1:Q+zdROLHV5HuLaa/5ataglCwNE4=
X-BSB-Auth	1.04305b3b24603825f755.20230127012219GMT.87o7qkwz3o.fsf@bsb.me.uk
Xref	csiph.com comp.programming:16351

Show key headers only | View raw

ram@zedat.fu-berlin.de (Stefan Ram) writes:

>   To wrap a paragraph, I wrote a Python script that searched for
>   the best wrap, given a quality function that included penalties
>   for interpunction near the end of a line (but not at the end)
>   or adjacent lines that differed greatly in length.
>
>   It worked, but as the number of lines approached ten, it became
>   painfully slow.
>
>   By an incredible twist of fate, I came across a chapter of
>   a book that explained dynamic programming and how to use it
>   to reduce the complexity of global paragraph wrapping from
>   exponential to quadratic!

The TeX Book describes two-level algorithm to calculate optimal line
breaks in paragraphs and the optimal page breaks.

-- 
Ben.

Back to comp.programming | Previous | Next | Find similar

Thread

Re: Paragraph Wrapping Ben Bacarisse <ben.usenet@bsb.me.uk> - 2023-01-27 01:22 +0000

csiph-web