Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-12-11
2003-01-21
Hong, Stephen S. (Department: 2122)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06510441
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to methods and apparatus for breaking text into lines.
One operation commonly performed in preparing text materials for printing or displaying is to divide paragraphs into individual lines. When done well, readers hardly notice that the words have been arbitrarily broken into a plurality of lines. When done poorly, readers notice awkward line breaks that interrupt their train of thought, requiring more time and effort to read the text.
A conventional method for breaking a paragraph into lines determines appropriate line breaks by analyzing one line at a time. Words are added to a line until a suitable length is obtained, at which point a break is made and a new line is started. Although this method is relatively simple and fast, it fails to take into consideration that the final appearance of the paragraph as a whole and how the appearance of a given line is influenced by preceding and succeeding lines.
As discussed in Donald E. Knuth and Michael F. Plass's article entitled “Breaking Paragraph Into Lines,” Software-Practice and Experience, Vol II, pp. 1119-1184 (1981), optimal line breaks may be selected by considering all feasible line breaks for one paragraph. The articles describes a method that evaluates all combinations of line breaks for a given paragraph and selects an optimal set of line breaks for the paragraph. This method was designed to operate in a batch-processing environment on a mainframe or minicomputer and not in an interactive environment of modem personal computers.
SUMMARY OF THE INVENTION
In general, in one aspect, the invention features methods and apparatus for dividing a paragraph into lines. The method includes the steps of selecting a first line break to define the end of a first line by evaluating possible line breaks for multiple possible lines in a first portion of the paragraph; and selecting a second line break to define the end of a second line following the first line by evaluating possible line breaks for multiple possible lines in a second portion of the paragraph, where the second portion overlaps the first portion but does not include words before the first line break.
Among the advantages of the invention are the following. The invention determines optimal line breaks in a paragraph by considering feasible line breaks for a portion of the paragraph covering multiple lines. The invention requires less memory space and processing time even for a long paragraph because only a portion of the paragraph at a time is analyzed to determine optimal line breaks. This is particularly important when processing a long paragraph since possible combinations of line breaks grow exponentially for a linear increase of feasible line breaks. The invention therefore is advantageous in a real-time editing environment with memory, processing resource and time constraints.
For a fuller understanding of the nature and further advantages of the invention, reference should be made to the detailed description taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 5438512 (1995-08-01), Mantha et al.
patent: 5625773 (1997-04-01), Bespalko et al.
patent: 5835920 (1998-11-01), Horton
patent: 5978819 (1999-11-01), Berstis
patent: 6018749 (2000-01-01), Rivette et al.
patent: 6044383 (2000-03-01), Suzuki et al.
patent: 6189020 (2001-02-01), Shimizu
patent: 6279018 (2001-08-01), Kudrolli et al.
Rod Stephens, “Ready-to-Run, Visual Basic Algorithms,” Second Edition,Wiley Computer Publishing, pp. 117-185.
URW hz-program, “Micro-typography for advanced typesetting,”URW Software&TypeGmbH, Hamburg, Germany, 1993, 1-38.
Knuth et al., “Breaking Paragraphs into Lines,”Software-Practice and Experience, vol. 11,, pp. 1119-1184, Feb. 1981.
Adobe Systems Incorporated
Fish & Richardson P.C.
Hong Stephen S.
LandOfFree
Optimal line break determination does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimal line break determination, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal line break determination will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3051472