Article layout device for automatic column text layout

• US 5,956,738 A
• Filed: 03/04/1997
• Issued: 09/21/1999
• Est. Priority Date: 03/04/1996
• Status: Expired due to Term

• Current Assignee: NEC Personal Computers, Ltd. (Lenovo Group Ltd.)
• Original Assignee: NEC Corporation
• Inventors: Shirakawa, Takahisa
• Primary Examiner(s): Feild, Joseph H.
• Assistant Examiner(s): Kindred, Alford W.
• Application Number:
  US08/810,450
• Time in Patent Office: 931 Days
• Field of Search: 707/517, 707/518, 707/519, 707/529, 707/500, 707/531, 707/521, 707/530, 707/509, 707/520
• US Class Current: 715/273
• CPC Class Codes: G06F 40/106 Display of layout of documents; Previewing

Abstract

An article layout device which comprises an article data input section, a column shape data generation section to divide the article space into a plurality of columns, a column layout order generation section to provide the generated columns with the layout orders, an article layout order generation section to provide the article data with the layout orders, a layout source data synthesis section to newly synthesize the division result of the article space, the column layout order and the article data layout order, an allocation section to allocate the article data to the columns according to the column layout order and the article data layout order, a layout result evaluation section to evaluate the layout results by the allocation section, an optimum layout result retrieval section to detect the layout result according to the evaluation result by the layout result evaluation section and an article output section to lay out and output the article data on the article space according to the layout result detected by the optimum layout result retrieval section.

Claims

1. An article layout device for layout of document on which a plurality of article data with some columns are laid out comprising:

an article data input means for inputting said article data;

a column generation means for dividing the article space to lay out said article data into a plurality of columns with random shapes;

a column layout order generation means for providing the columns generated by said column generation means with the order of layout processing;

an article layout order generation means for providing said article data with the order of layout processing;

a layout source data synthesis means for synthesizing a new division result of said article space by combining a plurality of division results of the article space divided into some columns by said column generation means, synthesizing a new layout order of said columns by combining a plurality of layout orders for said columns generated by said column layout order generation means and also synthesizing a new layout order of said article data by combining a plurality of layout orders for said article data generated by said article layout order generation means;

an allocation means for allocating said article data to said columns according to the layout order for said columns determined by said column layout order generation means or the column layout order for said columns synthesized by said layout source data synthesis means and the layout order for said article data determined by said article layout order generation means or the layout order for said article data synthesized by said layout source data synthesis means;

a layout result evaluation means for evaluating the layout results output from said allocation means and generating the evaluation values;

an optimum layout result retrieval means, according to the evaluation values generated by said layout result evaluation means, for detecting the layout result with the maximum evaluation value from the layout results output from said allocation means; and

an article output means, according to the layout result detected by said optimum layout result retrieval means, for laying out said article data on said article space for output.

2. An article layout device as set forth in claim 1, wherein

said column generation means

divides said article space into a plurality of columns,

generates unit areas by further dividing said plurality of columns,

provides said unit areas with the column combination number and

generates columns by combining said unit areas having the same column number among said unit areas mutually neighboring for either side.

3. An article layout device as set forth in claim 1, wherein

said layout source data synthesis means selects, when synthesizing a new layout order for said columns and a new layout order for said article data in relation to the division result for a new article space, a set serving as a synthesis base for a higher probability in that the set with a high evaluation value generated by said layout result evaluation means is selected from the sets of the existing space division result, the existing column layout order and the existing article data layout order.

4. An article layout device as set forth in claim 1, wherein

said layout source data synthesis means repeatedly synthesizes new division results for the article space by combining a plurality of division results for the article space divided into some columns by said column generation means or division results for said article space synthesized by itself, and repeatedly synthesizes new layout orders for said columns by combining a plurality of layout orders for said columns generated by said column layout order generation means or layout orders for said columns synthesized by itself, and repeatedly synthesizes new layout orders for said article data by combining a plurality of layout orders for said article data generated by said article layout order generation means or layout orders for said article data synthesized by itself.

5. An article layout device as set forth in claim 1, wherein

said layout source data synthesis means repeatedly synthesizes new division results for the article space by combining a plurality of division results for the article space divided into some columns by said column generation means or division results for said article space synthesized by itself, and repeatedly synthesizes new layout orders for said columns by combining a plurality of layout orders for said columns generated by said column layout order generation means or layout orders for said columns synthesized by itself, and repeatedly synthesizes new layout orders for said article data by combining a plurality of layout orders for said article data generated by said article layout order generation means or layout orders for said article data synthesized by itself, and

said optimum layout result retrieval means

starts its operation on condition that said layout source data synthesis means synthesizes the division results for the article space, said column layout order and said article data layout order for the predetermined number.

6. An article layout device as set forth in claim 1, wherein

said layout source data synthesis means repeatedly synthesizes new division results for the article space by combining a plurality of division results for the article space divided into some columns by said column generation means or division results for said article space synthesized by itself, and repeatedly synthesizes new layout orders for said columns by combining a plurality of layout orders for said columns generated by said column layout order generation means or layout orders for said columns synthesized by itself, and repeatedly synthesizes new layout orders for said article data by combining a plurality of layout orders for said article data generated by said article layout order generation means or layout orders for said article data synthesized by itself, and

said optimum layout result retrieval means starts its operation on condition that said layout source data synthesis means executes its processing for the predetermined time.

7. An article layout device as set forth in claim 1, wherein

said layout source data synthesis means repeatedly synthesizes new division results for the article space by combining a plurality of division results for the article space divided into some columns by said column generation means or division results for said article space synthesized by itself, and repeatedly synthesizes new layout orders for said columns by combining a plurality of layout orders for said columns generated by said column layout order generation means or layout orders for said columns synthesized by itself, and repeatedly synthesizes new layout orders for said article data by combining a plurality of layout orders for said article data generated by said article layout order generation means or layout orders for said article data synthesized by itself, and

said optimum layout result retrieval means starts its operation on condition that said layout result evaluation means provides an evaluation value exceeding the predetermined evaluation value for said layout result.

8. An article layout device as set forth in claim 1, wherein

said layout source data synthesis means repeatedly synthesizes new division results for the article space by combining a plurality of division results for the article space divided into some columns by said column generation means or division results for said article space synthesized by itself, and repeatedly synthesizes new layout orders for said columns by combining a plurality of layout orders for said columns generated by said column layout order generation means or layout orders for said columns synthesized by itself, and repeatedly synthesizes new layout orders for said article data by combining a plurality of layout orders for said article data generated by said article layout order generation means or layout orders for said article data synthesized by itself, and

said optimum layout result retrieval means counts the processing where the evaluation value given by said layout result evaluation means for the set of newly synthesized division result for the article space, said column layout order and said article data layout order does not update the maximum evaluation value before that and starts its operation when the number of such processing exceeds the predetermined number.

9. An article layout device as set forth in claim 1, wherein

said layout source data synthesis means repeatedly synthesizes new division results for the article space by combining a plurality of division results for the article space divided into some columns by said column generation means or division results for said article space synthesized by itself, and repeatedly synthesizes new layout orders for said columns by combining a plurality of layout orders for said columns generated by said column layout order generation means or layout orders for said columns synthesized by itself, and repeatedly synthesizes new layout orders for said article data by combining a plurality of layout orders for said article data generated by said article layout order generation means or layout orders for said article data synthesized by itself, and

said optimum layout result retrieval means detects the processing where the evaluation value given by said layout result evaluation means for the set of newly synthesized division result for the article space, said column layout order and said article data layout order does not update the maximum evaluation value before that and, starts its operation on condition that the time of continued processing exceeds the predetermined processing time.

10. An article layout device as set forth in claim 1, wherein

said column generation means normalizes the column combination numbers appearing for the first time so that the numbers are incremented by one in the same direction according to the appearance order.

11. An article layout device for layout of document on which a plurality of article data with some columns are laid out comprising:

an article data input means for inputting said article data;

a column generation means for dividing the article space to lay out said article data into a plurality of columns with random shapes;

a column layout order generation means for providing the columns generated by said column generation means with the order of layout processing;

an article layout order generation means for providing said article data with the order of layout processing;

a layout source data synthesis means for synthesizing a new division result of said article space by combining a plurality of division results of the article space divided into some columns by said column generation means, synthesizing a new layout order of said columns by combining a plurality of layout orders for said columns generated by said column layout order generation means and also synthesizing a new layout order of said article data by combining a plurality of layout orders for said article data generated by said article layout order generation means;

an allocation means for allocating said article data to said columns according to the layout order for said columns determined by said column layout order generation means or the column layout order for said columns synthesized by said layout source data synthesis means and the layout order for said article data determined by said article layout order generation means or the layout order for said article data synthesized by said layout source data synthesis means;

a layout result evaluation means for evaluating the layout results output from said allocation means and generating the evaluation values;

an optimum layout result retrieval means, according to the evaluation values generated by said layout result evaluation means, for detecting the set having the maximum evaluation value among those containing the article space division result generated by said column generation means and said column layout order generated by said column layout order generation means and said article data layout order generated by said article layout order generation means;

an optimum layout allocation means, according to the set of article space division result and said column layout order and said article data layout order detected by said optimum layout result retrieval means, for allocating said article data to said columns; and

an article output means for laying out and outputting said article data on said article space according to the layout result output by said optimum layout allocation means.

12. An article layout device as set forth in claim 11, wherein said allocation means also serves as said optimum layout allocation means.

13. An article layout device as set forth in claim 11, wherein

said column generation means

divides said article space into a plurality of columns,

generates unit areas by further dividing said plurality of columns,

provides said unit areas with the column combination number and

generates columns by combining said unit areas having the same column number among said unit areas mutually neighboring for either side.

14. An article layout device as set forth in claim 11, wherein

said layout source data synthesis means selects, when synthesizing a new layout order for said columns and a new layout order for said article data in relation to the division result for a new article space, a set serving as a synthesis base for a higher probability in that the set with a high evaluation value generated by said layout result evaluation means is selected from the sets of the existing space division result, the existing column layout order and the existing article data layout order.

15. An article layout device as set forth in claim 11, wherein

said layout source data synthesis means repeatedly synthesizes new division results for the article space by combining a plurality of division results for the article space divided into some columns by said column generation means or division results for said article space synthesized by itself, and repeatedly synthesizes new layout orders for said columns by combining a plurality of layout orders for said columns generated by said column layout order generation means or layout orders for said columns synthesized by itself, and repeatedly synthesizes new layout orders for said article data by combining a plurality of layout orders for said article data generated by said article layout order generation means or layout orders for said article data synthesized by itself.

16. An article layout device as set forth in claim 11 wherein

said layout source data synthesis means repeatedly synthesizes new division results for the article space by combining a plurality of division results for the article space divided into some columns by said column generation means or division results for said article space synthesized by itself, and repeatedly synthesizes new layout orders for said columns by combining a plurality of layout orders for said columns generated by said column layout order generation means or layout orders for said columns synthesized by itself, and repeatedly synthesizes new layout orders for said article data by combining a plurality of layout orders for said article data generated by said article layout order generation means or layout orders for said article data synthesized by itself, and

said optimum layout result retrieval means

starts its operation on condition that said layout source data synthesis means synthesizes the division results for the article space, said column layout order and said article data layout order for the predetermined number.

17. An article layout device as set forth in claim 11, wherein

said layout source data synthesis means repeatedly synthesizes new division results for the article space by combining a plurality of division results for the article space divided into some columns by said column generation means or division results for said article space synthesized by itself, and repeatedly synthesizes new layout orders for said columns by combining a plurality of layout orders for said columns generated by said column layout order generation means or layout orders for said columns synthesized by itself, and repeatedly synthesizes new layout orders for said article data by combining a plurality of layout orders for said article data generated by said article layout order generation means or layout orders for said article data synthesized by itself, and

said optimum layout result retrieval means starts its operation on condition that said layout source data synthesis means executes its processing for the predetermined time.

18. An article layout device as set forth in claim 11, wherein

said layout source data synthesis means repeatedly synthesizes new division results for the article space by combining a plurality of division results for the article space divided into some columns by said column generation means or division results for said article space synthesized by itself, and repeatedly synthesizes new layout orders for said columns by combining a plurality of layout orders for said columns generated by said column layout order generation means or layout orders for said columns synthesized by itself, and repeatedly synthesizes new layout orders for said article data by combining a plurality of layout orders for said article data generated by said article layout order generation means or layout orders for said article data synthesized by itself, and

said optimum layout result retrieval means starts its operation on condition that said layout result evaluation means provides an evaluation value exceeding the predetermined evaluation value for said layout result.

19. An article layout device as set forth in claim 11, wherein

said layout source data synthesis means repeatedly synthesizes new division results for the article space by combining a plurality of division results for the article space divided into some columns by said column generation means or division results for said article space synthesized by itself, and repeatedly synthesizes new layout orders for said columns by combining a plurality of layout orders for said columns generated by said column layout order generation means or layout orders for said columns synthesized by itself, and repeatedly synthesizes new layout orders for said article data by combining a plurality of layout orders for said article data generated by said article layout order generation means or layout orders for said article data synthesized by itself, and

said optimum layout result retrieval means counts the processing where the evaluation value given by said layout result evaluation means for the set of newly synthesized division result for the article space, said column layout order and said article data layout order does not update the maximum evaluation value before that and starts its operation when the number of such processing exceeds the predetermined number.

20. An article layout device as set forth in claim 11, wherein

said layout source data synthesis means repeatedly synthesizes new division results for the article space by combining a plurality of division results for the article space divided into some columns by said column generation means or division results for said article space synthesized by itself, and repeatedly synthesizes new layout orders for said columns by combining a plurality of layout orders for said columns generated by said column layout order generation means or layout orders for said columns synthesized by itself, and repeatedly synthesizes new layout orders for said article data by combining a plurality of layout orders for said article data generated by said article layout order generation means or layout orders for said article data synthesized by itself, and

said optimum layout result retrieval means detects the processing where the evaluation value given by said layout result evaluation means for the set of newly synthesized division result for the article space, said column layout order and said article data layout order does not update the maximum evaluation value before that and, starts its operation on condition that the time of continued processing exceeds the predetermined processing time.

21. An article layout device as set forth in claim 11, wherein

said column generation means normalizes the column combination numbers appearing for the first time so that the numbers are incremented by one in the same direction according to the appearance order.

22. An article layout device as set forth in claim 11, wherein

said layout data group storage means deletes data with the corresponding evaluation value data, when required to store more sets than predetermined, starting from the sets with lower evaluation values given by said layout result evaluation means among the sets of the article space division result, said column layout order and said article data layout order so as to store a new set of data.