METHOD AND SYSTEM FOR GENERATING A DOCUMENT SUMMARY

• US 20030079185A1
• Filed: 12/18/1998
• Published: 04/24/2003
• Est. Priority Date: 10/09/1998
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: KATARIYA, SANJEEV, JONES, WILLIAM P.
• Granted Patent: US 6,789,230 B2
• Time in Patent Office: Days
• US Class Current: 715/530
• CPC Class Codes: G06F 16/345 Summarisation for human users
• CPC Class Codes: G06F 40/20 Natural language analysis semantic analysis of natural language G06F40/30
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30

Abstract

A method and system for generating a summary of a document. The summary generating system generates the summary from the sentences that form the document. The summary generating system calculates a weight for each of the sentences in the document. The weight indicates the importance of the sentence to the document. The summary generating system then selects sentences based on their calculated weights. The summary generating system creates a summary of the selected sentences such that selected sentences are ordered in the created summary in the same relative order as in the document. In one embodiment, the summary generating system identifies sets of sentences whose total length of the sentences in the set is less than a maximum length. The summary generating system then selects an identified set of sentences whose total of the calculated weights of the sentences is greatest as the generated summary. The length of a sentence may be measured in characters or words. In an alternate embodiment, the summary generating system selects the sentences with the highest calculated weights whose total length of the selected sentences is less than a maximum length as the summary.

Claims

1. A method in a computer system for generating a summary of a document, the document having sentences, the sentences being ordered, the method comprising:

providing a weight for each of a plurality of the sentences, the weight indicating importance of the sentence to the document;

selecting sentences based on the provided weights of the sentences; and

creating a summary of the selected sentences such that selected sentences are ordered in the created summary in the same relative order as in the document.

2. The method of claim 1 wherein each sentence has a length and wherein the selecting of the sentences includes selecting a set of sentences whose total of the provided weights of the sentences in the set is greatest among those sets of sentences whose total length is less than a predefined length.

3. The method of claim 2 wherein the length is measured in words.

4. The method of claim 2 wherein the length is measured in characters.

5. The method of claim 1 wherein the created summary includes an indication of sentences of the document that are omitted from the selected sentences.

6. The method of claim 5 wherein the indication of sentences of the document that are omitted is an ellipsis.

7. The method of claim 1 wherein the selecting of the sentences includes selecting those sentences with the highest provided weights.

8. The method of claim 7 wherein each sentence has length and wherein the selecting includes selecting sentences with a total length that is less than a maximum length.

9. The method of claim 8 wherein the length is measured in words.

10. The method of claim 8 wherein the length is measured in characters.

11. The method of claim 1 wherein the providing of the weights includes calculating the weight of each sentence based on term frequencies of terms in the sentence.

12. The method of claim 1 wherein the created summary is stored as a property of the document.

13. The method of claim 7 wherein the created summary is stored as a binary representation.

14. The method of claim 1 wherein the document is one of a plurality of documents, wherein the sentence has component terms, and wherein the providing of the weight of a sentence includes:

estimating a number of the plurality of documents that contain the sentence based on term frequencies of the component terms, a term frequency of a term being a number of occurrences of that term in a document;

estimating a total number of times the sentence occurs in the plurality of documents based on the term frequencies of the component terms; and

combining the estimated number of documents that contain the sentence and the estimated total number of times that the sentence occurs in the plurality of documents to generate the weight for the sentence.

15. The method of claim 1 wherein the document is one of a plurality of documents, wherein each document comprises terms, wherein each sentence comprises component terms, and wherein the providing of a weight of a sentence includes:

for each term, providing a term frequency that represents the number of occurrences of that term in the plurality of documents;

estimating a document frequency for the sentence based on an estimated sentence probability of the sentence, the document frequency being the number of the plurality of the documents that contain the sentence, the estimated sentence probability being an estimation of the probability that any sentence in documents that contain each component term is the sentence, the sentence probability being derived from term probabilities of the component terms, the term probability of a component term being a ratio of an average of the provided term frequencies for the component terms per document that contains that component term to an average number of terms per document;

estimating a total sentence frequency for the sentence based on an average sentence frequency for the sentence times the estimated document frequency for the sentence, the average sentence frequency being derived from the sentence probability of the sentence and the average number of terms per document; and

combining the estimated document frequency with the estimated total sentence frequency to generate the weight of the sentence.

16. A method in a computer system for generating a summary of a document, the document having sentences, each sentence having a length, the method comprising:

providing a weight for each of a plurality of the sentences, the weight indicating importance of the sentence to the document;

identifying sets of sentences whose total length of the sentences in the set is less than a maximum length; and

selecting an identified set of sentences whose total of the provided weights of the sentences is greatest as the generated summary.

17. The method of claim 16 wherein the sentences are ordered in the document and wherein sentences in the generated summary are ordered in the same relative order as in the document.

18. The method of claim 16 wherein the length is measured in words.

19. The method of claim 16 wherein the length is measured in characters.

20. The method of claim 16 wherein the generated summary includes an indication of sentences of the document that are omitted from the selected sentences.

21. The method of claim 20 wherein the indication of sentences of the document that are omitted is an ellipsis.

22. The method of claim 16 wherein the created summary is stored as a property of the document.

23. The method of claim 16 wherein the document is one of a plurality of documents, wherein the sentence has component terms, and wherein the providing of the weights of a sentence includes:

estimating a number of the plurality of documents that contain the sentence based on term frequencies of the component terms, a term frequency of a term being a number of occurrences of that term in a document;

estimating a total number of times the sentence occurs in the plurality of documents based on the term frequencies of the component terms; and

combining the estimated number of documents that contain the sentence and the estimated total number of times that the sentence occurs in the plurality of documents to generate the weight for the sentence.

24. The method of claim 16 wherein the document is one of a plurality of documents, wherein each document comprises terms, wherein each sentence comprises component terms, and wherein the providing of a weight of a sentence includes:

for each term, providing a term frequency that represents the number of occurrences of that term in the plurality of documents;

estimating a document frequency for the sentence based on an estimated sentence probability of the sentence, the document frequency being the number of the plurality of the documents that contain the sentence, the estimated sentence probability being an estimation of the probability that any sentence in documents that contain each component term is the sentence, the sentence probability being derived from term probabilities of the component terms, the term probability of a component term being a ratio of an average of the provided term frequencies for the component terms per document that contains that component term to an average number of terms per document;

estimating a total sentence frequency for the sentence based on an average sentence frequency for the sentence times the estimated document frequency for the sentence, the average sentence frequency being derived from the sentence probability of the sentence and the average number of terms per document; and

combining the estimated document frequency with the estimated total sentence frequency to generate the weight of the sentence.

25. The method of claim 16 wherein the provided weights of a sentence are sums of weights of component terms of the sentences.

26. A method in a computer system for generating a summary of a document, the document having sentences, each sentence having a length, the method comprising:

providing a weight for each of a plurality of the sentences, the weight indicating importance of the sentence to the document; and

selecting the sentences with the highest provided weights wherein the total length of the selected sentences is less than a maximum length as the summary.

27. The method of claim 26 wherein the sentences are ordered and wherein sentences in the generated summary are ordered in the same relative order as in the document.

28. The method of claim 26 wherein the length is measured in words.

29. The method of claim 26 wherein the length is measured in characters.

30. The method of claim 26 wherein the generated summary includes an indication of sentences of the document that are omitted from the selected sentences.

31. The method of claim 26 wherein the indication of sentences of the document that are omitted is an ellipsis.

32. The method of claim 26 wherein the generated summary is stored as a property of the document.

33. The method of claim 27 wherein the provided weights of a sentence are a sum of weights of component terms of the sentence.

34. The method of claim 26 wherein the document is one of a plurality of documents, wherein the sentence has component terms, and wherein the providing of the weights of a sentence includes:

estimating a number of the plurality of documents that contain the sentence based on term frequencies of the component terms, a term frequency of a term being a number of occurrences of that term in a document;

estimating a total number of times the sentence occurs in the plurality of documents based on the term frequencies of the component terms; and

combining the estimated number of documents that contain the sentence and the estimated total number of times that the sentence occurs in the plurality of documents to generate the weight for the sentence.

35. The method of claim 26 wherein the document is one of a plurality of documents, wherein each document comprises terms, wherein each sentence comprises component terms, and wherein the providing of a weight of a sentence includes:

for each term, providing a term frequency that represents the number of occurrences of that term in the plurality of documents;

estimating a document frequency for the sentence based on an estimated sentence probability of the sentence, the document frequency being the number of the plurality of the documents that contain the sentence, the estimated sentence probability being an estimation of the probability that any sentence in documents that contain each component term is the sentence, the sentence probability being derived from term probabilities of the component terms, the term probability of a component term being a ratio of an average of the provided term frequencies for the component terms per document that contains that component term to an average number of terms per document;

estimating a total sentence frequency for the sentence based on an average sentence frequency for the sentence times the estimated document frequency for the sentence, the average sentence frequency being derived from the sentence probability of the sentence and the average number of terms per document; and

combining the estimated document frequency with the estimated total sentence frequency to generate the weight of the sentence.

36. A computer-readable medium containing instructions for causing a computer system to generate a summary of a document, the document having sentences, the sentences being ordered, by selecting sentences based on weights of the sentences, the weight of a sentence indicating importance of the sentence to the document, and by creating a summary of the selected sentences such that selected sentences are ordered in the created summary in the same relative order as in the document.

37. The computer-readable medium of claim 36 wherein each sentence has a length and wherein the selecting of the sentences includes selecting a set of sentences whose total of the weights of the sentences in the set is greatest among those sets of sentences whose total length is less than a predefined length.

38. The computer-readable medium of claim 37 wherein the length is measured in words.

39. The computer-readable medium of claim 37 wherein the length is measured in characters.

40. The computer-readable medium of claim 36 wherein the generated summary includes an indication of sentences of the document that are omitted from the selected sentences.

41. The computer-readable medium of claim 40 wherein the indication of sentences of the document that are omitted is an ellipsis.

42. The computer-readable medium of claim 36 wherein the selecting of the sentences includes selecting those sentences with the highest weights.

43. The computer-readable medium of claim 42 wherein each sentence has length and wherein the selecting includes selecting sentences with a total length that is less than a maximum length.

44. The computer-readable medium of claim 43 wherein the length is measured in words.

45. The computer-readable medium of claim 43 wherein the length is measured in characters.

46. The computer-readable medium of claim 36 including calculating the weight of each sentence based on term frequencies of terms in the sentence.

47. The computer-readable medium of claim 36 wherein the created summary is stored as a property of the document.

48. The computer-readable medium of claim 36 wherein the created summary is stored as a binary representation.

49. The computer-readable medium of claim 36 wherein the weights of a sentence are sums of the weights of component terms of the sentence.

50. A computer system for generating a summary of a document, the document having sentences, each sentence having a length, comprising:

a component that calculates a weight for each of a plurality of the sentences;

a component that identifies sets of sentences whose total length of the sentences in the set is less than a maximum length; and

a component that selects an identified set of sentences whose total of the calculated weights of the sentences is greatest.

51. The computer system of claim 50 wherein the sentences are ordered in the document and wherein sentences in the created summary are ordered in the same relative order as in the document.

52. The computer system of claim 50 wherein the length is measured in words.

53. The computer system of claim 50 wherein the length is measured in characters.

54. The computer system of claim 50 wherein the generated summary includes an indication of sentences of the document that are omitted from the selected sentences.

55. The computer system of claim 54 wherein the indication of sentences of the document that are omitted is an ellipsis.

56. The computer system of claim 50 wherein the generated summary is stored as a property of the document.

57. A computer system for generating a summary of a document, the document having sentences, each sentence having a length, comprising:

a component for calculating a weight for each of a plurality of the sentences; and

a component for selecting the sentences with the highest calculated weights wherein the total length of the selected sentences is less than a maximum length.

58. The computer system of claim 57 wherein the sentences are ordered and wherein sentences in the generated summary are ordered in the same relative order as in the document.

59. The computer system of claim 57 wherein the length is measure in number of words.

60. The computer system of claim 57 wherein the length is measured in number of characters.

61. The computer system of claim 57 wherein the generated summary includes an indication of sentences of the document that are omitted from the selected sentences.

62. The computer system of claim 57 wherein the indication of sentences of the document that are omitted is an ellipsis.

63. The computer system of claim 57 wherein the generated summary is stored as a property of the document.

64. The method of claim 57 wherein the calculated weights of a sentence are a sum of weights of component terms of the sentence.