Fast title/summary extraction from long descriptions

• US 9,317,595 B2
• Filed: 12/06/2010
• Issued: 04/19/2016
• Est. Priority Date: 12/06/2010
• Status: Active Grant

• Current Assignee: Yahoo Assets LLC
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Li, Xin, Zhao, Hongjian
• Primary Examiner(s): Serrou, Abdelali
• Application Number:
  US12/960,828
• Publication Number:
  US 20120143595A1
• Time in Patent Office: 1,961 Days
• Field of Search: 704 1- 10, 704/E11.001, 704/9, 704/E17.119, 704/769, 704/999.107
• US Class Current: 1/1
• 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 for generating shorter versions of one or more sentences, the method comprising:

receiving, by a computing device, the one or more sentences from a text;

based on the one or more sentences, generating, by the computing device within a memory of the computing device, a tree comprising a plurality of nodes;

wherein the tree represents the one or more sentences;

wherein each node, of the plurality of nodes, represents a grammatical element of the one or more sentences;

using a named entity recognizer, automatically recognizing which nodes, of the plurality of nodes, represent grammatical elements that correspond to recognized named entities;

selecting a particular node from the tree based, at least in part, on (a) which nodes in the tree correspond to recognized named entities, (b) a position of the particular node within the tree, and (c) a node type of the particular node;

wherein the particular node has no children within the tree that correspond to recognized named entities identified by the named entity recognizer;

after said selecting, modifying the tree within the memory of the computing device by removing the particular node and children of the particular node from the tree;

after removing, from the tree, the particular node and the children of the particular node, generating, from remaining nodes of the tree a first set of one or more sub-sentences;

wherein the first set of one or more sub-sentences are shorter in length than said one or more sentences;

causing display of at least one sub-sentence generated from remaining nodes of the tree to a user.

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

3. The method of claim 2, 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 selecting comprises:

determining which node has 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.

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, 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 the set of one or more words from the one or more sentences.

9. 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.

19. The method of claim 1, further comprising comparing a length of the first set of one or more sub-sentences with a threshold value.

20. The method of claim 1, wherein the at least one sub-sentence includes the first set of one or more sub-sentences.

10. 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 for generating shorter versions of one or more sentences comprising:

receiving, by a computing device, the one or more sentences from a text;

based on the one or more sentences, generating, by the computing device within a memory of the computing device, a tree comprising a plurality of nodes;

wherein the tree represents representing the one or more sentences;

wherein each node, of the plurality of nodes, represents a grammatical element of the one or more sentences;

using a named entity recognizer, automatically recognizing which nodes, of the plurality of nodes, represent grammatical elements that correspond to recognized named entities;

selecting a particular node from the tree based, at least in part, on (a) which nodes in the tree correspond to recognized named entities, (b) a position of the particular node within the tree, and (c) a node type of the particular node;

wherein the particular node has no children within the tree that correspond to recognized named entities identified by the named entity recognizer;

after said selecting, modifying the tree within the memory of the computing device by removing the particular node and children of the particular node from the tree;

after removing, from the tree, the particular node and the children of the particular node, generating, from remaining nodes of the tree, a first set of one or more sub-sentences;

wherein the first set of one or more sub-sentences are shorter in length than said one or more sentences;

causing display of at least one sub-sentence generated from remaining nodes of the tree to a user.

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

12. The non-transitory computer-readable medium of claim 11, wherein the node type is associated with a grammatical element of the grammatical structure of the one or more sentences.

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

determining which node has 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.

14. The non-transitory computer-readable medium of claim 13, 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.

15. The non-transitory computer-readable medium of claim 10, 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.

16. The non-transitory computer-readable medium of claim 15, 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.

17. The non-transitory computer-readable medium of claim 10, 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 the set of one or more words from the one or more sentences.

18. The non-transitory computer-readable medium of claim 10, 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.