What is the difference between US6510441 and the Knuth-Plass algorithm?

Question

This patent cites Knuth-Plass as a prior art, but doesn't seem to specify how it varies. It must do since this patent was approved, but what is the difference? Is is a difference in implementation only or is is a bigger difference that affects the outcome?

Answer 1

This method looks at a moving window of lines rather than requiring the entire paragraph to be considered as a whole.

The background says:

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.

In the summary of their invention the applicants say:

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 patentability of a method, the actual claimed steps would be looked at for novelty and non-obviousness. The end result being the same or different than a known method is not directly relevant. Also, there is a usefulness requirement to get a patent. Useful does not mean better, just useful.

In this case the inventors do think they have a better method in terms of memory usage and execution time.