Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-02-12
2001-04-24
Feild, Joseph H. (Department: 2776)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06223191
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to electronic word processing devices, and in particular to the formatting of textual material for printing, display, or the like.
BACKGROUND OF THE INVENTION
Word processing involves the creation, editing, storage, and output of textual documents. Word processing is frequently performed using a general-purpose digital computer, executing an applications program having word processing function. Such a general purpose computer may be anything from a large mainframe connected to hundreds of individual terminals, to a stand alone personal computer. Word processing may also be performed using single-purpose electronic word processing devices. As used herein, the term “word processor” shall encompass any of the above implementations.
One of the major tasks of any word processor is to format the document for output. Output can take many forms, but most frequently output will be either printed on paper or displayed on a computer screen.
When formatting a document for output, the word processor must determine where to end each line of text. Typically, a user will input parameters such as the location of margins, size of font, whether or not to hyphenate, etc., and the word processor will automatically determine where to end each line based on these parameters. Most word processors follow a simple “maximum fit” algorithm, attempting to cram as much as possible onto each line before going on to the next line. I.e., they sequentially examine each line of text, attempting to fit as many words or word segments as possible on the current line consistent with the formatting parameters. Once the determination is made with respect to a line, the formatter moves on to the next line. The formatter never reconsiders the formatting of a previous line. If hyphenation is specified by the user, the word processor will attempt to place a portion of the word on the current line if the entire word will not fit.
The maximum fit algorithm may be implemented in any of several ways. If full left/right justification is used, the fit may be determined initially assuming a minimum spacing between words, which is then expanded as necessary to fill available space. Alternatively, the fit may be determined initially assuming a nominal word spacing, which may be reduced by no more than a predetermined amount if doing so will make it possible to squeeze the last word segment onto the line, or expanded if the final segment will not fit in any case. Where ragged right justification is used, the nominal word spacing will typically be used, which is not subsequently modified.
The “maximum fit” algorithm described above has the advantage of formatting the output in the fewest possible number of lines (given the constraints of margins, fonts, etc.). However, it can lead to undesirably formatted output.
The problems with the “maximum fit” algorithm are particularly acute where full left/right justification is specified, and the column width (between margins) is relatively narrow. This is, for example, the norm used by newspapers and magazines. Where full justification is used, the amount of space between each word is adjusted in order to make each line of words exactly the same length. Sometimes, the amount of extra space is so great that letterspacing is required, i.e., small spaces must be placed between individual letters. Letterspacing gives the formatted output a strange appearance, and can make it more difficult to read. Letterspacing can be reduced if hyphenation is used, but excessive hyphenation can also make the output difficult to read.
Readability can be improved if hyphenation is prohibited. However, this causes the textual material to occupy a larger number of lines. In a newspaper and many other applications, space is at such a premium that this is generally considered an unacceptable solution.
This use of letterspacing and/or excessive hyphenation is now so familiar to most people that it has become accepted as a necessary annoyance that any newspaper reader has to put up with. However, an unrecognized need exists for improved general readability and appearance of newspapers and other formatted documents, without use of additional document space or reduction in type size. The present invention is directed toward this goal.
SUMMARY OF THE INVENTION
It is, therefore, an object of the present invention to provide an enhanced word processing method and apparatus.
Another object of this invention is to improve the appearance of formatted output of a word processor.
Another object of this invention is to make the formatted text output of a word processing device more readable to a human.
Another object of this invention is to reduce the occurrences of undesirable formatting characteristics in formatted text, such as hyphenation or letterspacing, without increasing the number of lines required to format the output.
A text formatter formats text by considering groups of words, a group being more than a single line at a time. A determination is made as to the minimum number of lines required to hold the formatted group. In general, each line contains the maximum number of words that will fit, consistent with the applicable formatting parameters such as margins, font size, etc. However, the formatter may override this and move a word or portion of a word onto a subsequent line, even though it would fit on the original line, provided that the minimum number of lines required to format the group is not thereby exceeded. This is done in order to reduce hyphenation, letterspacing, or other undesirable formatting effects.
In the preferred embodiment, an entire paragraph is formatted as a group. The formatter generates multiple permutations of possible formatted text lines, assigning a weighted value to each permutation. With each successive line of text, undesirable permutations are pruned. A permutation is pruned if it appears that it would cause the paragraph to format in more than the minimum number of lines; or if letterspacing has exceeded a given threshold; or if the weighted score is worse than the weighted score of another permutation which ends with the same word or word segment. The unpruned permutations are used to generate permutations of the next succeeding line of text. The set of permuted lines having the most desirable cumulative weighted value within the predetermined minimum number of lines is chosen as the best formatting.
In the preferred embodiment, the text formatter is one of the functions of a word processing program executing on a general purpose computer system.
In general, the resulting formatted text will be both easier to read and more aesthetically appealing because it will have fewer hyphenated words, letterspaced words, or related undesirable formatting characteristics. At the same time, the resulting formatted text will occupy a minimum number of lines (i.e., the same number of lines as text formatted with a maximum fit algorithm).
REFERENCES:
patent: 4575813 (1986-03-01), Bartlett et al.
patent: 4608664 (1986-08-01), Bartlett et al.
patent: 5784008 (1998-07-01), Raguseo
“Eliminating Optical Effects in Computer Printing.” IBM Technical Disclosure Bulletin, vol. 31 No. 12. Published May 1, 1989. pp. 35-39.
“Right Margin Controls.” IBM Technical Disclosure Bulletin, vol. 27 No. 1A. Published Jun. 1, 1984. pp. 126-128.
Feild Joseph H.
International Business Machines - Corporation
Perkins Michael J.
Truelson Roy W.
LandOfFree
Method and apparatus for automatically formatting multiple... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for automatically formatting multiple..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for automatically formatting multiple... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2511178