The Knuth-Plass algorithm is a line-breaking algorithm created by Donald Knuth and Michael Plass in 1981 for Knuth's TeX typesetting system. Rather than treating line breaking and hyphenation as separate problems, it unifies them by representing a paragraph as a sequence of boxes, glue and penalties, and searches for the set of break points that minimizes a measure of visual unattractiveness called badness. Its classic dynamic programming solution runs in quadratic time in the worst case, though it is typically much faster in practice, and later research has shown the problem can be solved in linear time with specialized algorithms such as SMAWK. The algorithm is prized for producing paragraphs with more even spacing than simple line-by-line methods.
Facts
Time Complexity
Time Complexity (category)Quadratic Time -- O(n^2) 1 Classification
Design Technique Connections
Sources
1. Wikipedia: Knuth-Plass line-breaking algorithm
entity record, description (design-technique)Quote, entity record, description (design-technique)
Its classic dynamic programming solution runs in quadratic time in the worst case, though it is typically much faster in practice, and later research has shown the problem can be solved in linear time with specialized algorithms such as SMAWK.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.