System and method for summarization combining natural language generation with structural analysis

• US 7,305,336 B2
• Filed: 08/30/2002
• Issued: 12/04/2007
• Est. Priority Date: 08/30/2002
• Status: Expired due to Fees

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Polanyi, Livia, van den Berg, Martin H.
• Primary Examiner(s): Dorvil; Richemond
• Assistant Examiner(s): SAINT CYR, LEONARD
• Application Number:
  US10/231,732
• Publication Number:
  US 20040044519A1
• Time in Patent Office: 1,922 Days
• Field of Search: 704/9, 704/1
• US Class Current: 704/9
• CPC Class Codes: G06F 16/345 Summarisation for human users
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation

Abstract

A system and method of summarizing text comprising performing structural summarization of a source text and compressing at least one relationship in the structural summarization.

Claims

1. A method of summarizing source text, comprising:

ranking two or more nodes in a discourse tree, wherein the ranking is based on the depth of the node, wherein the depth of a node (N) is calculated from the number of subordinated edges of subordination subtree nodes plus one between N and the root, and including removing all nodes having a depth greater than a specified depth;

performing structural summarization based on the ranking of nodes of the source text; and

compressing at least one relationship in the structural summarization.

2. The method of claim 1 wherein:

the structural summarization is based on one of Linguistic Discourse Model, Rhetorical Structure Theory, Discourse Structures Theory, and Structured Discourse Representation Theory.

3. The method of claim 1 wherein:

the source text is represented as a discourse structure comprised of one or more discourse units.

4. The method of claim 3 wherein:

compressing the at least one relationship is based on default unification, wherein default unification involves ordering of discourse units from most specific to most general.

5. The method of claim 1 wherein:

the at least one relationship expresses a coordination relationship between a plurality of discourse units.

6. The method of claim 1, further comprising:

generating a text summary based on the structural summarization and the at least one compressed relationship.

7. The method of claim 6 wherein:

portions of the generated text summary that are based on the at least one compressed relationship are distinguished from other portions of the generated text summary.

8. The method of claim 6 wherein:

the source text underlying the at least one compressed relationship in the generated text summary can be accessed.

9. The method of claim 1 wherein:

compressing the at least one relationship is based on unification, wherein the relationships are unified if there is a substitution that makes them identical.

10. The method of claim 1 wherein:

compressing the at least one relationship is based on default unification, wherein default unification involves ordering of discourse units from most specific to most general.

11. The method of claim 1 wherein:

the source text underlying the at least one compressed relationship in the generated text summary can be accessed.

12. A method of summarizing source text, comprising:

applying default unification to at least one coordination-type relationship in a structural representation of the source text to create at least one compressed representation, wherein default unification involves ordering of expressions of the text from most specific to most general; and

performing structural summarization of the source text, the structural summarization to be accomplished by ranking two or more nodes in a discourse tree, wherein the ranking is based on the depth of the node, wherein the depth of a node (N) is calculated from the number of subordinated edges of subordination subtree nodes plus one between N and the root, and including removing all nodes having a depth greater than a specified depth.

13. The method of claim 12 wherein:

a coordination-type relationship expresses a symmetric relationship between a plurality of discourse units.

14. The method of claim 12 wherein:

the structural representation is based on one of Linguistic Discourse Model, Rhetorical Structure Theory, Discourse Structures Theory, and Structured Discourse Representation Theory.

15. The method of claim 12 wherein:

the source text is represented as a discourse structure comprised of one or more discourse units.

16. The method of claim 12, further comprising:

generating a text summary based on the structural representation and the at least one compressed representation.

17. The method of claim 16 wherein:

portions of the generated text summary that are based on the at least one compressed representation are distinguished from other portions of the generated text summary.

18. The method of claim 16 wherein:

the source text underlying the at least one compressed representation in the generated text summary can be accessed.

19. The method of claim 16 wherein:

generating a text summary based on the at least one compressed representation uses natural language generation.

20. The method of claim 12 wherein:

the at least one relationship is directly ascertainable.

21. The method of claim 12 wherein:

the at least one relationship includes at least one other relationship that can be compressed.

22. A method for selecting coordination relationships for compression in a discourse, the method comprising:

automatically segmenting the discourse into units, wherein the segmenting is based on a technique selected from the group consisting of statistical methods, shallow parsing and deep parsing, wherein the discourse can be represented by two or more nodes in a discourse tree;

ranking two or more discourse units, wherein the ranking is based on the depth of the node, wherein the depth of a node (N) is calculated from the number of subordinated edges of subordination subtree nodes plus one between N and the root;

pruning to remove all nodes having a depth greater than a specified depth;

structurally summarizing based on the ranking of the discourse units, wherein the discourse units segments are small enough for the structural summarization to extract semantic meaning from the discourse; and

selecting at least one coordination relationship in the representation, wherein the at least one coordination relationship is susceptible to compression.

23. The method of claim 22 wherein:

a coordination relationship is susceptible to compression if it is directly ascertainable.

24. The method of claim 22 wherein:

a coordination relationship is susceptible to compression if it includes at least one other relationship that is susceptible to compression.

25. A system for summarizing source text comprising:

a means for ranking two or more nodes in a discourse tree, wherein the ranking is based on the depth of the node, wherein the depth of a node (N) is calculated from the number of subordinated edges of subordination subtree nodes plus one between N and the root;

a means for performing structural summarization on the ranking of nodes of the source text, including means for pruning to remove all nodes having a depth greater than a specified depth;

a means for compressing at least one coordination relationship in the structural summarization; and

a means for generating a text summary based on the structural summarization and the at least one compressed coordination relationship, wherein by selecting the text summary the source text underlying the at least one compressed relationship can be accessed.

26. The system of claim 25 further comprising:

a means for generating a text summary.

27. The system of claim 26 wherein:

the means for generating a text summary includes a natural language generator.

28. The method of claim 26 wherein:

portions of the generated text summary that are based on the at least one compressed relationship are distinguished from other portions of the generated text summary.

29. A machine readable medium having instructions stored thereon to generate a text summary that when executed by a processor cause a system to:

represent a source text as discourse units;

generate a discourse tree based on the discourse units;

rank nodes in the discourse tree, wherein the ranking is based on the depth of the node, wherein the depth of a node (N) is calculated from the number of subordinated edges of subordination subtree nodes plus one between N and the root;

prune to remove all nodes having a depth greater than a specified depth;

perform structural summarization based on the pruned ranking of the discourse units;

compress at least one relationship in the structural summarization; and

generate a text summary based on the structural summarization and the at least one compressed relationship, wherein by selecting the text summary the source text underlying the at least one compressed relationship can be accessed.

30. The machine readable medium of claim 29 wherein:

the structural summarization is based on one of Linguistic Discourse Model, Rhetorical Structure Theory, Discourse Structures Theory, and Structured Discourse Representation Theory.

31. The machine readable medium of claim 29 wherein:

the source text is represented as a discourse structure comprised of one or more discourse units.

32. The machine readable medium of claim 31 wherein:

the at least one relationship expresses a coordination-type relationship between a plurality of discourse units.

33. The machine readable medium of claim 29 wherein:

portions of the generated text summary that are based on the at least one compressed relationship are distinguished from other portions of the generated text summary.

34. The machine readable medium of claim 29 wherein:

compressing the at least one relationship is based on default unification.

35. The machine readable medium of claim 29 wherein:

the at least one relationship is directly ascertainable.

36. The machine readable medium of claim 29 wherein:

the at least one relationship includes at least one other relationship that can be compressed.