Techniques for Extracting Unstructured Data

• US 20120078950A1
• Filed: 09/29/2010
• Published: 03/29/2012
• Est. Priority Date: 09/29/2010
• Status: Abandoned Application

• Current Assignee: Nvest, Inc. (Washington)
• Original Assignee: Nvest, Inc. (Washington)
• Inventors: Conrad, Parker, Arora, Tarun
• Application Number:
  US12/894,134
• Publication Number:
  US 20120078950A1
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

A technique for extracting unstructured data includes receiving a plurality of regular expressions and a given document. The regular expressions include a plurality of extensible grammar expressions for searching for a set of information. The regular expressions are then used to search the given document to determine if the unstructured data matches one or more of the extensible grammar expressions. If a match is determined, one or more set of information is extracted from the unstructured data using one or more heuristics.

Claims

1. A method comprising:

receiving a plurality of extensible grammar expressions, wherein each extensible grammar expression includes a regular expression that searches for a set of information;

receiving a given document including unstructured data;

tokenizing the given document;

searching the tokenized given document using the regular expressions to determine if the unstructured data in the document matches one or more of the extensible grammar expressions;

extracting one or more sets of information from the unstructured data using one or more heuristics; and

outputting the one or more sets of extracted information.

2. The method according to claim 1, wherein the regular expressions comprise a comprehensive list of sentences abstracted into a plurality of grammatical structures based on allowed forms and variances of the sentences.

3. The method according to claim 1, wherein each extensible grammar expression includes a plurality of variables and one or more regular expression operands arranged in an allowed form of a grammatical structure.

4. The method according to claim 3, wherein the regular expressions of the set of extensible grammar expressions can identify the contexts within a sentence to determine which variable a given word fits under.

5. The method according to claim 1, wherein tokenizing the given document comprises replacing each of one or more words with corresponding potential word tokens.

6. The method according to claim 5, wherein one or more of the plurality of variables comprise a word substitution variable including a plurality of functionally equivalent words.

7. The method according to claim 1, further comprising:

receiving information to be extracted;

receiving a plurality of candidate documents including unstructured data;

generating a plurality of extensible grammar expressions for the information from the unstructured data of the plurality of candidate documents; and

outputting the plurality of extensible grammar expressions.

12. The one or more computing device readable media of claim 1 including a fourth plurality of computing device executable instructions that when executed by the processing unit implement a plurality of potential word tokens, wherein each word token includes a regular expression comprising one or more words, one or more phrases and one or more regular expression operands.

8. One or more computing device readable media including a first plurality of computing device executable instructions that when executed by a processing unit implement a plurality of extensible grammar expressions, wherein each extensible grammar expression includes a regular expression to match corresponding unstructured data in a document.

9. The one or more computing device readable media of claim 8, wherein each extensible grammar expression comprises a plurality of variables and a plurality of regular expression operands.

10. The one or more computing device readable media of claim 9, including a third plurality of computing device executable instructions that when executed by the processing unit implement the plurality of variables, wherein each variable comprises a variable identifier and one or more from the group of one or more words, one or more phrases, and one or more variables.

11. The one or more computing device readable media of claim 10, wherein one or more of said plurality of variables further includes one or more regular expression operands.

13. One or more computing device readable media including a plurality of computing device executable instructions which when executed by a processing unit implement a method comprising:

receiving a plurality of extensible grammar expressions, wherein each extensible grammar expression includes a regular expression that searches for a set of information;

receiving a given document including unstructured data;

pre-processing the given document;

tokenizing the given document;

searching the pre-processed and tokenized document using the regular expressions to determine if the unstructured data in the document matches one or more of the extensible grammar expressions;

extracting one or more sets of information from the unstructured data using one or more heuristics; and

outputting the one or more sets of extracted information.

14. The one or more computing device readable media including the plurality of computing device executable instructions which when executed by the processing unit implement the method of claim 13, wherein the regular expressions comprise a comprehensive list of sentences abstracted into a plurality of extensible grammar expressions based on allowed forms and variances of the sentences.

15. The one or more computing device readable media including the plurality of computing device executable instructions which when executed by the processing unit implement the method of claim 13, wherein each extensible grammar expression includes calls to a plurality of variables joined by one or more regular expression operands.

16. The one or more computing device readable media including the plurality of computing device executable instructions which when executed by the processing unit implement the method of claim 13, wherein each variable includes one or more functionally equivalent words joined by one or more regular expression operands.

17. The one or more computing device readable media including the plurality of computing device executable instructions which when executed by the processing unit implement the method of claim 16, wherein each variable further includes one or more functionally equivalent phrases joined by one or more regular expression operands.

18. The one or more computing device readable media including the plurality of computing device executable instructions which when executed by the processing unit implement the method of claim 17, wherein each variable further includes one or more calls to other variables joined by one or more regular expression operands.

19. The one or more computing device readable media including the plurality of computing device executable instructions which when executed by the processing unit implement the method of claim 17, wherein:

pre-processing the given document includes replacing each of one or more parameters with corresponding parameter tokens; and

tokenizing the given document includes replacing each of one or more words with corresponding potential word tokens.

20. The one or more computing device readable media including the plurality of computing device executable instructions which when executed by the processing unit implement the method of claim 13, further comprising:

identifying the information to be extracted;

receiving a plurality of candidate documents including unstructured data;

generating the plurality of extensible grammar expressions for the information from the unstructured data of the plurality of candidate documents; and

outputting the one or more regular expressions.