Constrained document layout

• US 20070118797A1
• Filed: 08/27/2004
• Published: 05/24/2007
• Est. Priority Date: 08/29/2003
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Layzell, Paul
• Granted Patent: US 7,634,723 B2
• Time in Patent Office: Days
• US Class Current: 715/234
• CPC Class Codes: G06F 40/103 Formatting, i.e. changing of presentation of documents automatic justification G06F40/189; automatic line break hyphenation G06F40/191

Abstract

A description of document elements to be laid out on a page, comprises two or more hierarchical levels; wherein each document element is placed at one of the hierarchical levels; and elements at a lower hierarchical level are associated with a document element at a next higher hierarchical level. Page layout according to such a document description may be optimised discretely at different hierarchical levels without affecting constraints.

Claims

1. A method of laying out a page which is to contain a plurality of discrete document elements, comprising:

receiving a hierarchical page description describing layout of the discrete document elements on the page, wherein the hierarchical page description contains two or more hierarchical levels, each of the discrete document elements is placed at one of the hierarchical levels;

optimising layout of the page described by the hierarchical page description by one or more rearrangement operations, where each rearrangement operation rearranges elements at a single hierarchical level, to minimise the value of a cost function; and

laying out the discrete document elements on the page according to the optimised hierarchical page description layout.

2. A method as claimed in claim 1, wherein a discrete document element may consist either of a representation of a group of document elements associated together at a lower hierarchical level or of a primitive document element.

3. A method as claimed in claim 2, wherein the hierarchical page description is representable as a tree with a primitive document element at each leaf node and with a representation of a group of document elements at each branching node.

5. A method as claimed in claim 1, wherein optimising the hierarchical page description layout comprises repeated use of a stochastic process.

6. A method as claimed in claim 5, wherein the hierarchical page description is describable as one or more genes each comprising a series of document elements and operators, and the stochastic process comprises use of a genetic algorithm.

7. A method as claimed in claim 6, wherein the hierarchical page description comprises one or more repeated genes.

8. A method as claimed in claim 7, wherein one or more classes are determined for document elements, a repeated gene is describable in terms of an ordering of element classes, and each expression of a repeated gene is describable in terms of document elements or groups of document elements corresponding to some or all of the element classes in the repeated gene.

9. A method as claimed in claim 1, wherein the hierarchical page description describes a slicing structure.

10. A method as claimed in claim 1, wherein one or more of the rearrangement operations comprises separating a constrained element from one or more unconstrained elements, rearranging the unconstrained elements, and then combining the rearranged unconstrained elements with the constrained element.

11. A computer comprising a processor programmed to perform the method of claim 1.

12. A data carrier comprising code adapted to program a processor of a computer system, when executed, to perform the method of claim 1.

4. A method as claimed in claim 4, wherein at a hierarchical level rearrangement operations are carried out only on document elements forming part of a group represented as a document element at the next higher hierarchical level.

13. A description of document elements to be laid out on a page, comprising:

two or more hierarchical levels;

wherein

each document element is placed at one of the hierarchical levels; and

elements at a lower hierarchical level are associated with a document element at a next higher hierarchical level,

such that the description is representable as a tree with a primitive document element at each leaf node and with a representation of a group of document elements at each branching node, and wherein each branching node represents a constraint place on the element of the group that is represented at that branching node.

14. A description as claimed in claim 13, wherein each representation of a group of document elements is describable as a gene comprising one or more operators and one or more operands.

15. A description as claimed in claim 14, wherein the hierarchical page description comprises one or more repeated genes.

16. A description as claimed in claim 15, wherein one or more classes are determined for document elements, a repeated gene is describable in terms of an ordering of element classes, and each expression of a repeated gene is describable in terms of document elements or groups of document elements corresponding to some or all of the element classes in the repeated gene.

17. A description as claimed in claim 13, wherein the description of document elements represents a slicing structure.

18. A data carrier having encoded thereon a description of document elements to be laid out on a page as claimed in claim 13.

19. A signal having encoded thereon a description of document elements to be laid out on a page as claimed in claim 13.

20. A method of generating a description of document elements to be laid out on a page, comprising:

identifying primitive document elements to be laid out on the page;

identifying constraints on the layout of the primitive document elements on the page;

constructing a hierarchical page description with a plurality of hierarchical levels, each primitive document element being placed at one of the hierarchical levels, and each document element at a lower hierarchical level being linked by one of the constraints to a document element at a next higher hierarchical level.