Methods and systems for extracting information from text

• US 9,110,852 B1
• Filed: 07/20/2012
• Issued: 08/18/2015
• Est. Priority Date: 07/20/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Lerman, Kevin
• Primary Examiner(s): MCFADDEN, SUSAN IRIS
• Application Number:
  US13/554,427
• Time in Patent Office: 1,124 Days
• Field of Search: 704/9
• US Class Current: 1/1
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: G06F 17/15 Correlation function computation including computation of convolution operations arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/226 Validation
• CPC Class Codes: G06F 40/295 Named entity recognition
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Information may be extracted from a text corpus. The text corpus may be parsed into a parse tree structure based on the parts of speech of the words of the text corpus. A path in the parse tree structure may be identified as linking an entity and a value, and the path may be applied to the same or other text corpuses to extract other instances of entity-value pairs. Extracted information, associated paths, or both may be validated in some instances.

Claims

1. A computer-implemented method for automatically identifying entity-value pairs from text, the method comprising the following operations performed by at least one processor:

receiving an electronic text file including a text corpus comprising a plurality of words;

generating, by parsing the text corpus, a corresponding parse tree structure in memory, including nodes of each of the plurality of words having edges based on the parts of speech of the plurality of words;

identifying a plurality of entity-value pairs in the text corpus that correspond to a predetermined entity and a predetermined value related to the predetermined entity by a predetermined attribute, wherein each of the entity-value pairs comprise an entity and a value;

extracting based on the parse tree structure, a plurality of parse tree paths to traverse the tree structure from a node corresponding the entity to a node corresponding to the value of the plurality of entity-value pairs;

generating a data record including an indication of how accurately the extracted plurality of parse tree paths correspond to the predetermined attribute, based on at least one of the plurality of parse tree paths; and

validating an entity-value pair based on the data record.

2. The method of claim 1, wherein identifying the plurality of entity-value pairs comprises identifying one or more phrases of the text corpus that correspond to the predetermined entity.

3. The method of claim 2, wherein the one or more phrases comprise a plurality of phrases, the method further comprising selecting, by the at least one-processor, one phrase from the plurality of phrases that provides a canonical representation of the entity.

4. The method of claim 1, further comprising recognizing, by the at least one processor, a portion of the text corpus as being equivalent to a text string based on a canonical representation of the portion of the text corpus.

5. The method of claim 1, wherein the plurality of parse tree paths are minimal paths through the parse tree structure that link the respective entities and the corresponding values in the plurality of entity-value pairs.

6. The method of claim 1, wherein the data record further comprises statistical information related to how well at least one of the plurality of parse tree paths maps to the predetermined attribute.

7. The method of claim 1, further comprising identifying, by the at least one processor, a plurality of values in the text corpus corresponding to the predetermined entity and a particular parse tree path of the plurality of parse tree paths, wherein the data record further comprises information associated with how many unique values exist in the plurality of values.

8. The method of claim 1, further comprising identifying, by the at least one processor, a plurality of entities in the text corpus corresponding to the predetermined value and a particular parse tree path of the plurality of parse tree paths, wherein the data record further comprises information associated with a number of unique entities in the plurality of entities.

9. The method of claim 1, wherein the text corpus is from a plurality of sources and wherein the data record further comprises a number of sources from which a given parse tree path of the plurality of parse tree paths was extracted.

10. The method of claim 1, further comprising the following operation performed by the at least one processor:

extracting a second plurality of parse tree paths corresponding to a second plurality of entity-value pairs associated with multiple attributes; and

identifying a common parse tree path in the plurality of parse tree paths and the second plurality of parse tree paths,

wherein the data record further comprises information associated with a percentage of entity-value pairs corresponding to the common parse tree path that have a given attribute.

11. A system for automatically identifying entity-value pairs from text, the system comprising:

a storage device that stores a set of instructions; and

at least one processor that executes the set of instructions to;

receive an electronic text file including a text corpus comprising a plurality of words;

generate by parsing the text corpus, a corresponding parse tree structure in memory, including nodes of each of the plurality of words having edges based on the parts of speech of the plurality of words;

identify a plurality of entity-value pairs in the text corpus that correspond to a predetermined entity and a predetermined value related to the predetermined entity by a predetermined attribute, wherein each of the entity-value pairs comprise an entity and a value;

extract, based on the parse tree structure, a plurality of parse tree paths to traverse the tree structure from a node corresponding the entity to a node corresponding to the value of the plurality of entity-value pairs;

generate a data record including an indication of how accurately the extracted plurality of parse tree paths correspond to the predetermined attribute, based on at least one of the plurality of parse tree paths; and

validating an entity-value pair based on the data record.

12. The system of claim 11, wherein the at least one processor further executes the instructions to identify one or more phrases of the text corpus that correspond to the predetermined entity.

13. The system of claim 12, wherein the one or more phrases comprise a plurality of phrases, and wherein the at least one processor further executes the instructions to select one phrase from the plurality of phrases that provides a canonical representation of the entity.

14. The system of claim 11, wherein the at least one processor further executes the instructions to recognize a portion of the text corpus as being equivalent to a text string based on a canonical representation of the portion of the text corpus.

15. The system of claim 11, wherein the plurality of parse tree paths are minimal paths through the parse tree structure that link the respective entities and the corresponding values in the plurality of entity-value pairs.

16. The system of claim 11, wherein the at least one processor further executes the instructions to determine statistical information related to how well at least one of the plurality of parse tree paths maps to the predetermined attribute.

17. The system of claim 11, wherein the at least one processor further executes the instructions to:

identify a plurality of values in the text corpus corresponding to the predetermined entity and a particular parse tree path of the plurality of parse tree paths; and

wherein the data record further includes information indicating how many unique values exist in the plurality of values.

18. The system of claim 11, wherein the at least one processor further executes the instructions to:

identify a plurality of entities in the text corpus corresponding to the predetermined value and a particular parse tree path of the plurality of parse tree paths; and

wherein the data record further includes information indicating a number of unique entities in the plurality of entities.

19. The system of claim 11, wherein the text corpus is from a plurality of sources and wherein the at least one processor further executes the instructions to determine a number of sources from which a given parse tree path of the plurality of parse tree paths was extracted.

20. The system of claim 11, wherein the at least one processor further executes the instructions to:

extract a second plurality of parse tree paths corresponding to a second plurality of entity-value pairs associated with multiple attributes; and

identify a common parse tree path in the plurality of parse tree paths and the second plurality of parse tree paths; and

wherein the data record further includes information indicating a percentage of entity-value pairs corresponding to the common parse tree path that have a given attribute.

21. A computer-implemented method for automatically identifying entity-value pairs from text, the method comprising the following operations performed by at least one processor:

receiving an electronic text file including a text corpus comprising a plurality of words;

generating, by parsing the text corpus, a corresponding parse tree structure in memory, including nodes of each of the plurality of words having edges based on the parts of speech of the plurality of words;

determining whether the parse tree structure includes a predetermined parse tree path corresponding to an attribute, the predetermined parse tree path traversing the parse tree structure from a node corresponding an entity to a node corresponding to a value of an entity-value pairs;

identifying a portion of the text corpus corresponding to the predetermined parse tree path when the parse tree structure includes the predetermined parse tree path;

extracting an entity-value pair from the portion of the text corpus, wherein the entity-value pair comprises an entity and a value corresponding to the entity, and wherein the entity-value pair corresponds to an entity-attribute-value relationship; and

validating the entity-value pair.

22. The method of claim 21, wherein validating the entity-value pair comprises:

comparing the entity and the corresponding value to one or more reference entities and corresponding values; and

determining whether the attribute corresponding to the predetermined parse tree path is indicative of an attribute associated with the extracted entity-value pair based on the comparison.

23. The method of claim 21, further comprising extracting, by the at least one processor, a plurality of entity-value pairs from the text corpus, wherein validating the entity-value pair comprises analyzing the plurality of entity-value pairs to determine how many values correspond to the value in the entity-value pair.

24. The method of claim 21, wherein validating the entity-value pair comprises comparing the entity-value to one or more entity and value text patterns.

25. The method of claim 21, further comprising invalidating, by the at least one processor, the predetermined parse tree path based on the validation of the entity-value pair.

26. The method of claim 21, wherein the predetermined parse tree path comprises an intermediate node corresponding to a portion of a word in the text corpus.

27. The method of claim 21, further comprising identifying, by the at least one processor, one or more characteristics of the text corpus prior to identifying the portion of the text corpus.

28. A system for automatically identifying entity-value pairs from text, the system comprising:

a storage device that stores a set of instructions; and

at least one processor that executes the set of instructions to;

receive an electronic text file including a text corpus comprising a plurality of words;

generating, with a processor, by parsing the text corpus, a corresponding parse tree structure in memory, including nodes of each of the plurality of words having edges based on the parts of speech of the plurality of words;

determine whether the parse tree structure includes a predetermined parse tree path corresponding to an attribute, the predetermined parse tree path traversing the parse tree structure from a node corresponding an entity to a node corresponding to a value of an entity-value pairs;

identify a portion of the text corpus corresponding to the predetermined parse tree path when the parse tree structure includes the predetermined parse tree path;

extract an entity-value pair from the portion of the text corpus, wherein the entity-value pair comprises an entity and a value corresponding to the entity, and wherein the entity-value pair corresponds to an entity-attribute-value relationship; and

validating the entity-value pair.

29. The system of claim 28, wherein the at least one processor further executes the instructions to:

compare the entity-value pair to one or more reference entities and corresponding values related to the one or more reference entities by corresponding reference attributes.

30. The system of claim 28, wherein the at least one processor further executes the instructions to:

extract a plurality of entity-value pairs from the text corpus; and

analyze the plurality of entity-value pairs to determine how many values correspond to the value in the entity-value pair.

31. The system of claim 28, wherein the at least one processor further executes the instructions to compare the entity-value to one or more entity and value text patterns.

32. The system of claim 28, wherein the at least one processor further executes the instructions to invalidate the predetermined parse tree path based on the validation of the entity-value pair.

33. The system of claim 28, wherein the predetermined parse tree path comprises an intermediate node corresponding to a portion of a word in the text corpus.

34. The system of claim 28, wherein the at least one processor further executes the instructions to identify one or more characteristics of the text corpus prior to identifying the portion of the text corpus.

35. The system of claim 28, further comprising memory configured to store a plurality of parse tree paths, wherein the plurality of parse tree paths comprise the predetermined parse tree path.