FAST TITLE/SUMMARY EXTRACTION FROM LONG DESCRIPTIONS

• US 20120143595A1
• Filed: 12/06/2010
• Published: 06/07/2012
• Est. Priority Date: 12/06/2010
• Status: Active Grant

• Current Assignee: Yahoo Assets LLC
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Zhao, Hongjian, LI, Xin
• Granted Patent: US 9,317,595 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 16/345 Summarisation for human users
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

Techniques are described herein for automatic generation of a title or summary from a long body of text. A grammatical tree representing one or more sentences of the long body of text is generated. One or more nodes from the grammatical tree are selected to be removed. According to one embodiment, a particular node is selected to be removed based on its position in the grammatical tree and its node-type, where the node type represents a grammatical element of the sentence. Once the particular node is selected, a branch of the tree is cut at the node. After branch has been cut, one or more sub-sentences are generated from the remaining nodes in the grammatical tree. The one or more sub-sentences may be returned as a title or summary.

Claims

1. A method comprising:

receiving one or more sentences;

based on the one or more sentences, generating a tree comprising a plurality of nodes representing the one or more sentences;

determining a first set of one or more nodes to remove from the tree;

wherein said determining is based, at least in part, on which nodes in the tree comprises a recognized named entity;

based on said determining, removing said first set of one or more nodes of the plurality of nodes from the tree;

after said removing, reconstructing, from remaining nodes of the plurality of nodes, a first set of one or more sub-sentences of said one or more sentences, wherein the first set of one or more sub-sentences are shorter in length than said one or more sentences;

wherein the method is performed by one or more special-purpose computing devices.

2. The method of claim 1, wherein the tree represents a grammatical structure of the one or more sentences and wherein said step of determining is further based on the grammatical structure of the one or more sentences represented by the tree.

3. The method of claim 2, wherein said step of determining is based, at least in part, on a position in the tree of at least one node of the first set of one or more nodes to remove and a node type associated with the at least one node, wherein the node type is associated with a grammatical element of the grammatical structure of the one or more sentences.

4. The method of claim 3, wherein the node-type of the at least one node is a secondary class node type and said step of determining comprises:

determining a particular node, having a secondary class node type, that is at a lower position within the grammatical tree than any other node having a secondary class node type;

wherein said step of removing comprises;

cutting a branch of the grammatical tree at the particular node;

wherein cutting the branch of the tree at the particular node removes the particular node and all children of the particular node from the grammatical tree.

5. The method of claim 4, wherein the secondary class node type comprises at least one of a node type representing a prepositional phrase, an adjective phrase, an adverbial phrase, or a dependent clause.

6. The method of claim 1, further comprising:

determining whether a size of the first set of one or more sub-sentences exceeds a maximum threshold;

in response to determining that the size of the first set of one or more sub-sentences exceeds the maximum threshold, performing the following;

determining a second set of one or more nodes to remove from the tree;

based on said determining, removing said second set of one or more nodes of the plurality of nodes from the tree;

after said removing, reconstructing, from the remaining nodes of the plurality of nodes, a second set of one or more sub-sentences of said one or more sentences, wherein the second set of one or more sub-sentences are shorter in length than said first set of one or more sentences.

7. The method of claim 6, further comprising:

determining that a size of the second set of one or more sub-sentences is less than a minimum threshold;

in response to determining that the size of the second set of one or more sub-sentences is less than the minimum threshold, determining whether the second set of one or more sub-sentences contains a named entity;

if said second set of one or more sub-sentences contains a recognized named entity, returning the second set of one or more sub-sentences as a title;

if said second set of one or more sub-sentences does not contain a recognized named entity, returning said first set of one or more sub-sentences as a title.

8. The method of claim 1, wherein the at least one node is part of a branch of the tree that does not include a recognized named entity.

9. The method of claim 1, further comprising:

before said step of generating the tree;

determining, based on a filter that identifies words that are not directly related to a story of the one or more sentences, a set of one or more words to remove from the one or more sentences

removing set of one or more words from the one or more sentences.

10. The method of claim 1, wherein the one or more sentences are from an article associated with an image, the method further comprising:

returning the one or more sub-sentences as a title for said image.

12. The non-transitory computer-readable medium of claim 1, wherein the tree represents a grammatical structure of the one or more sentences and wherein said step of determining is further based on the grammatical structure of the one or more sentences represented by the tree.

13. The non-transitory computer-readable medium of claim 12, wherein said step of determining is based, at least in part, on a position in the tree of at least one node of the first set of one or more nodes to remove and a node type associated with the at least one node, wherein the node type is associated with a grammatical element of the grammatical structure of the one or more sentences.

14. The non-transitory computer-readable medium of claim 13, wherein the node-type of the at least one node is a secondary class node type and instructions for said determining comprise instructions for:

determining a particular node, having a secondary class node type, that is at a lower position within the grammatical tree than any other node having a secondary class node type;

wherein instructions for said removing comprise instructions for;

cutting the grammatical tree at the particular node;

wherein cutting the tree at the particular node removes the particular node and all children of the particular node from the grammatical tree.

15. The non-transitory computer-readable medium of claim 14, wherein the secondary class node type comprises at least one of a node type representing a prepositional phrase, an adjective phrase, an adverbial phrase, or a dependent clause.

11. A non-transitory computer-readable storage medium that stores instructions which, when executed by one or more processors, cause the one or more processors to perform steps comprising:

receiving one or more sentences;

based on the one or more sentences, generating a tree comprising a plurality of nodes representing the one or more sentences;

determining a first set of one or more nodes to remove from the tree;

wherein said determining is based, at least in part, on which nodes in the tree comprises a recognized named entity;

based on said determining, removing said first set of one or more nodes of the plurality of nodes from the tree;

after said removing, reconstructing, from remaining nodes of the plurality of nodes, a first set of one or more sub-sentences of said one or more sentences, wherein the first set of one or more sub-sentences are shorter in length than said one or more sentences;

wherein the method is performed by one or more special-purpose computing devices.

16. The non-transitory computer-readable medium of claim 11, further comprising instructions which, when executed by one or more processors, cause the one or more processors to perform steps comprising:

determining whether a size of the first set of one or more sub-sentences exceeds a maximum threshold;

in response to determining that the size of the first set of one or more sub-sentences exceeds the maximum threshold, performing the following;

determining a second set of one or more nodes to remove from the tree;

based on said determining, removing said second set of one or more nodes of the plurality of nodes from the tree;

after said removing, reconstructing, from the remaining nodes of the plurality of nodes, a second set of one or more sub-sentences of said one or more sentences, wherein the second set of one or more sub-sentences are shorter in length than said first set of one or more sentences.

17. The non-transitory computer-readable medium of claim 16, further comprising which, when executed by one or more processors, cause the one or more processors to perform steps comprising:

determining that a size of the second set of one or more sub-sentences is less than a minimum threshold;

in response to determining that the size of the second set of one or more sub-sentences is less than the minimum threshold, determining whether the second set of one or more sub-sentences contains a named entity;

if said second set of one or more sub-sentences contains a recognized named entity, returning the second set of one or more sub-sentences as a title;

if said second set of one or more sub-sentences does not contain a recognized named entity, returning said first set of one or more sub-sentences as a title.

18. The non-transitory computer-readable medium of claim 11, wherein the at least one node is part of a branch of the tree that does not include a recognized named entity.

19. The non-transitory computer-readable medium of claim 11, further comprising instructions for performing:

before said generating the tree;

determining, based on a filter that identifies words that are not directly related to a story of the one or more sentences, a set of one or more words to remove from the one or more sentences

removing set of one or more words from the one or more sentences.

20. The non-transitory computer-readable medium of claim 11, wherein the one or more sentences are from an article associated with an image, the instructions further causing the one or more processors to perform:

returning the one or more sub-sentences as a title for said image.