Method and apparatus for summarizing multiple documents using a subsumption model

• US 7,398,196 B1
• Filed: 09/07/2000
• Issued: 07/08/2008
• Est. Priority Date: 09/07/2000
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Liu, Weiquan, Zhou, Joe F
• Primary Examiner(s): Edouard; Patrick N.
• Assistant Examiner(s): Wozniak; James S.
• Application Number:
  US10/018,517
• Time in Patent Office: 2,861 Days
• Field of Search: 704/1, 704 8- 10, 715/277
• US Class Current: 704/1
• CPC Class Codes: G06F 40/258 Heading extraction; Automatic titling; Numbering

Abstract

A method and apparatus for parsing a plurality of documents, selecting paragraphs from the documents through subsuming relation calculation, and rewriting the selected paragraphs into a summary is disclosed.

Claims

1. A computer-implemented method comprising:

parsing a plurality of paragraphs in a plurality of computer documents stored on a computer-readable medium, each document with one or more of the paragraphs;

selecting paragraphs from the documents through a subsuming relation calculation including,

creating a link from terms in each paragraph to identical terms in substantially all of the other paragraphs, wherein terms include noun phrases, verb phrases or entity names,

counting for each paragraph the number of links from the terms in the paragraph to the terms in other paragraphs,

denoting for each paragraph the number of links counted for that paragraph as the significant score of that paragraph,

ranking the paragraphs by the significant score,

selecting paragraphs based on the ranking, wherein paragraphs in the ranking that subsume the highest number of other paragraphs are selected prior to other paragraphs in the ranking, and wherein a first paragraph subsumes a second paragraph if all noun phrases verb phrases, and entity names contained in the second paragraph are also contained in the first paragraph;

aggregating the selected paragraphs into a summary and outputting the summary.

2. The method of claim 1 wherein parsing further comprises:

extracting noun phrases and verb phrases from the documents;

categorizing the noun phrases that are entity names; and

converting the entity names into canonical form.

3. The method of claim 1 further comprising:

applying a co-reference resolution algorithm to the selected paragraphs; and

replacing pronouns in the selected paragraphs with their full entity name antecedents.

4. The method of claim 1 wherein the documents have a common topic independent of domain.

5. The method of claim 1 wherein the documents are composed in English or in a language other than English.

6. A computer-readable medium having stored thereon sequences of instructions which are executable by a processor, and which, when executed by the processor, cause the processor to perform operations comprising:

parsing a plurality of paragraphs in a plurality of computer documents, each document with one or more of the paragraphs;

selecting paragraphs from the documents through a subsuming relation calculation including,

creating a link from terms in each paragraph to identical terms in substantially all of the other paragraphs, wherein terms include noun phrases, verb phrases or entity names,

counting for each paragraph the number of links from the terms in the paragraph to the terms in other paragraphs,

denoting for each paragraph the number of links counted for that paragraph as the significant score of that paragraph,

ranking the paragraphs by the significant score,

selecting paragraphs based on the ranking, wherein paragraphs in the ranking that subsume the highest number of other paragraphs are selected prior to other paragraphs in the ranking, and wherein a first paragraph subsumes a second paragraph if all noun phrases, verb phrases, and entity names contained in the second paragraph are also contained in the first paragraph;

aggregating the selected paragraphs into a summary; and

outputting the summary.

7. The medium of claim 6 wherein parsing further comprises:

extracting noun phrases and verb phrases from the documents;

categorizing the noun phrases that are entity names; and

converting the entity names into canonical form.

8. The medium of claim 6 further comprising instructions for:

applying a co-reference resolution algorithm to the selected paragraphs; and

replacing pronouns in the selected paragraphs with their full entity name antecedents.

9. The medium of claim 6 wherein the documents have a common topic independent of domain.

10. The medium of claim 6 wherein the documents are composed in English or in a language other than English.

11. A system comprising:

a processor;

a bus coupled to the processor; and

a unit coupled to the bus to;

parse a plurality of paragraphs in a plurality of computer documents, each document including one or more of the paragraphs,

select paragraphs from the documents through a subsuming relation calculation including;

creating a link from terms in each paragraph to identical terms in substantially all of the other paragraphs, wherein terms include noun phrases, verb phrases or entity names,

counting for each paragraph the number of links from the terms in the paragraph to the terms in other paragraphs,

denoting for each paragraph the number of links counted for that paragraph as the significant score of that paragraph,

ranking the paragraphs by the significant score,

selecting paragraphs based on the ranking, wherein paragraphs in the ranking that subsume the highest number of other paragraphs are selected prior to other paragraphs in the ranking, and wherein a first paragraph subsumes a second paragraph if all noun phrases, verb phrases, and entity names contained in the second paragraph are also contained in the first paragraph;

aggregate the selected paragraphs into a summary; and

outputting the summary.

12. The system of claim 11 wherein the unit further extracts noun phrases and verb phrases from the documents, categorizes the noun phrases that are entity names, and converts the entity names into canonical form.

13. The system of claim 11 wherein the unit further applies a co-reference resolution algorithm to the paragraphs, and replaces pronouns in the paragraphs with their full entity name antecedents.

14. The system of claim 11 wherein the documents have a common topic independent of domain.

15. The system of claim 11 wherein the documents are composed in English or in a language other than English.