Patent og Knuth og TeX?

[Carsten Svaneborg <sslug@sslug>]

Hej!

EP0205082 er et patent på at indsætte mellemrum i linier
således at højre og venstremargins er lige.
http://v3.espacenet.com/textclam?PN=EP0205082&DB=EPODOC&IDX=EP0205082

Helt præcist er det beskrevet neden under. Mit spørgsmål er om
Donald Knuth anvendte denne algoritme i TeX før dette patent
blev ansøgt i 1985?


What is claimed is:

1. An automated method of performing text justification to expand text
within a line to produce flush left and right margins on an output medium
comprising the steps of: A. determining the number of expandable interword
positions within the line (SPACES); B. determining the number of expandable
intercharacter positions within the line (CHARS); C. determining the amount
of expansion required within the line to a justified margin (EXPAND) by
subtracting the width of the text from the total line width, the width of
the text and the total line width being expressed in terms of horizontal
granular units which correspond to the smallest horizontal distance the
printhead of the output device can traverse along a line under control of
the justification process, the value of a horizontal granular unit not
being known to the justification process; D. if both CHARS and SPACES are
greater than 0: (1) compute portion of EXPAND which is to go between
characters and distribute it in expandable intercharacter positions; and
(2) compute portion of EXPAND which is to go between words and distribute
it in expandable interword positions; E. If CHARS is equal to 0, distribute
EXPAND into expandable interword positions; F. If SPACES is equal to 0,
distribute EXPAND into expandable intercharacter positions;

2. The method of claim 1, step A, where determining expandable interword
positions is done by counting expandable space characters in the line.

3. The method of claim 1, step B, where determining expandable
intercharacter positions is done by counting the number of non-space
characters that are not at the end of a word and subtract the number of
characters that have a composite flag set.

4. The method of claim 1, step C, where the amount of expansion is
determined by subtracting the width of the text from the total line width.

5. The method of claim 4 where the width of text and the total line width
are expressed in terms of horizontal granular units which correspond to the
smallest horizontal distance the printhead of the output device can
traverse along a line under the control of the justification process.

6. The method of claim 1 wherein a defined ratio is used to determine the
portion of the total expansion to be done by intercharacter expansion and
the portion of the total expansion to be done by interword expansion.

7. The method of claim 1 wherein intercharacter expansion is limited to some
defined maximum so that too much expansion does not occur between
characters within a word.

8. The method of claim 1, steps D(1) and D(2), wherein any expansion
remainder which cannot be uniformly distributed in a line is distributed at
alternating ends of consecutive lines to reduce the appearance of rivers in
justified text.

9. The method of claim 1 wherein distribution of the expansion is done by
augmenting a horizontal position count associated with each character that
is to be moved during the justification process.

10. The method of claim 9 wherein the horizontal position count is
maintained in horizontal granular units.



-- 
  Mvh. Carsten Svaneborg
http://www.softwarepatenter.dk