Document layout processing method and device for carrying out the same

• US 5,379,373 A
• Filed: 06/12/1991
• Issued: 01/03/1995
• Est. Priority Date: 06/15/1990
• Status: Expired due to Term

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Hayashi, Naoki, Saito, Kazuo
• Primary Examiner(s): Herndon, Heather R.
• Assistant Examiner(s): Vo, Cliff N.
• Application Number:
  US07/714,264
• Time in Patent Office: 1,301 Days
• Field of Search: 395/148, 395/145, 395/146, 395/149, 395/150, 364/419
• US Class Current: 715/235
• 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 document layout processing device involving the generation of a layout structure of a particular document based on a limitation of a layout structure common to a plurality of documents, an intermediate data structure generating unit generates a minimum layout structure common to all specific layout structures which can be generated from the layout structure common to the plurality of documents and an intermediate data structure indicating a data structure related to a layout which represents information about a manipulation indicating whether addition or deletion of a specific structure to or from the minimum layout structure is possible. The intermediate data structure is held in the intermediate data structure holding unit. In document processing, an intermediate data altering unit alters the intermediate data structure held in the intermediate data structure holding unit, on the basis of the content of a particular document to be laid out and the information about the manipulation which is included in the intermediate data structure itself held in the intermediate data structure holding unit. A specific layout structure extracting unit extracts a layout structure corresponding to the particular document to be laid out, from a newest intermediate data structure held in the intermediate data structure generating unit.

Claims

1. A document layout processing method in which a suitable layout structure is selected in accordance with a document content from a layout template specifying constraints for generating layout structures and, a layout structure in which the document content is laid out is generated, the method comprising the steps of:

generating a tree structure as an intermediate data structure, when said constraints specified in the layout template are represented by generation rules of grammar from which hierarchal structures are derived, and

making corresponding non-terminal symbols and terminal symbols including operators, which appear on the generation rules of grammar, with the nodes of the tree structure;

holding in a node among the plurality of nodes, which is being generated in association with the operator included in the generation rules of grammar, operator type information indicative of a type of the operator and manipulation history information indicative of a history of addition or deletion of an immediately subordinate node to or from the node being generated; and

adding or deleting the node to or from the tree structure based on the operator type information and the manipulation history information.

2. A document layout processing device in which a suitable layout structure is selected from a layout template specifying attributes for generating layout structures in accordance with a document content and a layout structure in which the document content is laid out is generated, the system comprising:

intermediate data structure generating means for generating an intermediate data structure in the form of a tree structure, said tree structure having a plurality of nodes including an immediately subordinate node, said tree structure representing simultaneously both the attributes specified in the layout template and a layout structure being generated;

intermediate data structure holding means for holding the intermediate data structure generated by the intermediate data structure generating means;

intermediate data structure altering means for altering the intermediate data structure held in the intermediate data structure holding means, based on the document content and the attributes represented by the intermediate data structure held in the intermediate data structure holding means;

specific layout structure extracting means for extracting a layout structure in which the document content is laid out, from a newest intermediate data structure held in the intermediate data structure holding means;

the constraints specified in the layout template being represented by generation rules of grammar from which hierarchal structures are derived;

non-terminal symbols and terminal symbols including operators, which appear on the generation rules of grammar, are made to correspond with the nodes of the tree structure;

operator type information indicative of an operator type and manipulation history information indicative of a history of addition or deletion of an immediately subordinate node to or from a node being generated are held in the node being generated among the plurality of nodes in association with the operator included in the generation rules of grammar; and

a node is added or deleted to or from the tree structure based on the operator type information and the manipulation history information.

3. A document layout processing method in which when a structure representing logical divisions of a document content is defined as a logical structure and a structure representing layout divisions of a document is defined as a layout structure, a layout structure corresponding to a logical structure of a specific document is generated on the basis of a template specifying constraints for generating a plurality of layout structures and a generation history of a layout structure and also for selectively generating a suitable layout structure from among the plurality of layout structures, the method comprising the steps of:

generating an intermediate data structure which is a structure representing simultaneously both template information corresponding to the template and generation history information indicative of said generation history of a layout structure based on the template and also generating as an initial state of an intermediate data structure a structure corresponding to a minimum layout structure common to the plurality of layout structures generatable based on the template;

updating the intermediate data structure by referring to the template information and the generation history information in the intermediate data structure of the initial state so that the logical structure of the specific document conforms to the template;

generating a final intermediate data structure; and

generating a layout structure corresponding to the logical structure of the specific document on the basis of the final intermediate data structure.

4. A document layout processing method in which when a hierarchal structure representing logical divisions of a document content is defined as a logical structure and a hierarchal structure representing layout divisions of a document is defined as a layout structure, a structured document containing at least a logical structure of a specific document content and a template specifying constraints for generating a plurality of layout structures said plurality of layout structures being stored, and also for selectively generating a suitable layout structure from among the stored plurality of layout structures, and a layout structure corresponding to the logical structure of the specific document content is generated on the basis of the template, the method comprising the steps of:

generating an intermediate data structure which is a hierarchal structure representing simultaneously both template information corresponding to the template and generation history information indicative of a generation history of a layout structure based on the template and also generating as an initial state of the intermediate data structure a hierarchal structure corresponding to a minimum layout structure common to the plurality of layout structures generatable based on the template;

updating the intermediate data structure by referring to the template information and the generation history information in the intermediate data structure of the initial state so that the logical structure of the specific document content conforms to the template generating a final intermediate data structure; and

generating a layout structure corresponding to the logical structure of the specific document content on the basis of the final intermediate data structure.

5. A method according to claim 4, wherein the intermediate data structure is a tree structure, said tree structure having a plurality of nodes, including an immediately subordinate node and wherein

on the basis of the template, manipulation possibility information indicative of addition or deletion of the immediately subordinate node and manipulation history information indicative of addition or deletion of the immediately subordinate node and manipulation history information indicative of addition or deletion of the immediately subordinate node are held in the plurality of nodes;

and

the layout processing is executed by adding or deleting a node to or from the tree structure on the basis of the manipulation possibility information and the manipulation history information so that the logical structure of the specific document content conforms to the template.

6. A method according to claim 4, wherein

when the template is represented by generation rules of a grammar from which hierarchal structures are derived,

nodes including an immediately subordinate node are generated in correspondence with non-terminal symbols which appear on the generation rules and terminal symbols including operators and also a tree structure configured by said nodes is generated as the intermediate data structure;

in a node among the nodes, which is being generated in association with the operator, operator type information indicative of a type of the operator and manipulation history information indicative of a history of addition or deletion of the immediately subordinate node to or from the node being generated are held; and

the layout processing is executed by adding or deleting the node to or from the tree structure based on the operator type information and the manipulation history information so that the logical structure of the specific document content conforms to the template.

7. A document layout processing device in which when a hierarchal structure representing logical divisions of a document content is defined as a logical structure and a hierarchal structure representing layout divisions of a document is defined as a layout structure, a structured document containing at least a logical structure of a specific document content and a template specifying constraints for generating a plurality of layout structures means for storing the plurality of layout structures and also for selectively generating a desired layout structure from among the plurality of stored layout structures, and a layout structure corresponding to the logical structure of the specific document content is generated on the basis of the template, the device comprising:

intermediate data structure generating means for generating an intermediate data structure which is a hierarchal structure representing simultaneously both template information corresponding to the template and generation history information indicative of a generation history of a layout structure based on the template and also for generating as an initial state of the intermediate data structure a hierarchal structure corresponding to a minimum layout structure common to the plurality of layout structures generatable based on the template;

intermediate data structure holding means for holding the intermediate data structure generated by the intermediate data structure generating means;

intermediate data structure altering means for altering the intermediate data structure held in the intermediate data structure holding means by referring to the template information and the generation history information held in the intermediate data structure holding means so that the logical structure of the specific document content conforms to the template; and

specific layout structure extracting means for extracting a layout structure corresponding to the logical structure of the specific document content from a latest intermediate data structure held in the intermediate data structure holding means.

8. A device according to claim 7, wherein

the intermediate data structure generating means generates a tree structure as the intermediate data structure, said tree structure constituted by a plurality of nodes and at east one immediately subordinate node, and, on the basis of the template, stores in the intermediate data structure holding means manipulation possibility information indicative of addition or deletion of an immediately subordinate node to or from the plurality of nodes and manipulation history information indicative of addition or deletion of the immediately subordinate node;

and

the intermediate data structure altering means executes the addition or deletion of a node to or from the tree structure on the basis of the manipulation possibility information and the manipulation history information so that the logical structure of the specific document content conforms to the template.

9. A device according to claim 7, wherein

the intermediate data structure generating means, when the template is represented by generation rules of a grammar from which hierarchal structures are derived, generates nodes in association with non-terminal symbols which appear in the generation rules and terminal symbols including operators and also generates as the intermediate data structure a tree structure configured by the nodes said nodes including an immediately subordinate node;

the intermediate data structure holding means, in a node among the nodes, which is being generated in association with the operator, holds operator type information indicative of an operator type and manipulation history information indicative of a history of addition or deletion of the immediately subordinate node to or from the node being generated; and

the intermediate data structure altering means executes the addition or deletion of a node to or from the tree structure based on the operator type information and the manipulation history information so that the logical structure of the specific document content conforms to the template.