Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Example

Suppose we are given a sequence of n=5 words, tex2html_wrap_inline67863 having lengths tex2html_wrap_inline67865, respectively, which are to be typeset in a paragraph of width D=60. Assume that the normal width of an inter-word space is s=10.

We begin by computing the lengths of all the subsequences of W using Equation gif. The lengths of all n(n-1)/2 subsequences of W are tabulated in Table gif.

 

 

tex2html_wrap_inline67811

i

tex2html_wrap_inline67881j=1 2 3 4 5
1 10 10 20 30 42 92
2 10 10 20 32 82
3 10 10 22 72
4 12 12 62
5 50 50
Table: Typesetting problem.

Given tex2html_wrap_inline67811, D, and s, it is a simple matter to apply tex2html_wrap_inline67891 to obtain the one-line penalties, tex2html_wrap_inline67837, which measure the amount of stretching or compressing needed to set all the words in a given subsequence on a single line. These are tabulated in Table gif.

 

 

tex2html_wrap_inline67837 tex2html_wrap_inline67629

i

j=1 2 3 4 5 j=1 2 3 4 5
1 50 30 10 12 tex2html_wrap_inline67905 50 30 10 12 22
2 50 30 8 tex2html_wrap_inline67905 50 30 8 18
3 50 28 tex2html_wrap_inline67905 50 28 38
4 48 tex2html_wrap_inline67905 48 58
5 10 10
Table: Penalties.

Given the one-line penalties tex2html_wrap_inline67837, we can use Equation gif to find for each subsequence of W the minimum total penalty, tex2html_wrap_inline67629, associated with forming a paragraph from the words in that subsequence. These are tabulated in Table gif.

The tex2html_wrap_inline67919 entry in Table gif gives the minimum total cost of typesetting the entire paragraph. The value 22 was obtained as follows:

eqnarray33084

This indicates that the optimal solution is to set words tex2html_wrap_inline67307, tex2html_wrap_inline67925, tex2html_wrap_inline67927, and tex2html_wrap_inline67929 on the first line of the paragraph and leave tex2html_wrap_inline67931 by itself on the last line of the paragraph. Figure gif illustrates this result.

   figure33099
Figure: Typesetting a paragraph.

This formulation of the typesetting problem seems like overkill. Why not just typeset the lines of text one-by-one, minimizing the penalty for each line as we go? In other words why don't we just use a greedy strategy? Unfortunately, the obvious greedy solution strategy does not work!

For example, the greedy strategy begins by setting the first line of text. To do so it must decide how many words to put on that line. The obvious thing to do is to select the value of k for which tex2html_wrap_inline67969 is the smallest. From Table gif we see that tex2html_wrap_inline67971 has the smallest penalty. Therefore, the greedy approach puts three words on the first line as shown in Figure gif.

Since the remaining two words do not both fit on a single line, they are set on separate lines. The total of the penalties for the paragraph typeset using the greedy algorithm is tex2html_wrap_inline67973. Clearly, the solution is not optimal (nor is it very pleasing esthetically).


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.