Named entity recognition using compiler methods

• US 20060047500A1
• Filed: 08/31/2004
• Published: 03/02/2006
• Est. Priority Date: 08/31/2004
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Powell, Kevin R., Humphreys, Kevin W.
• Application Number:
  US10/930,131
• Publication Number:
  US 20060047500A1
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/295 Named entity recognition

Abstract

Methods of identifying named entities in natural language text using machine or computer compiler tools are provided. A lexical analyzer generator such as Flex or Lex or an equivalent tool can be used to generate a recognizer for named entities, such as digits, date expressions, and email or web addresses. Alternatively, a parser generator, such as Yacc or Bison or an equivalent tool can be used to generate a recognizer for other named entities, such as person and company names. Further, a lexical analyzer generated by Flex, Lex, or its equivalent is used in combination with a parser generated by Yacc, Bison, or its equivalent to identify named entities. Multiple lexical analyzers and/or parsers identify one or more classes of named entities, such as email addresses or person names. In many embodiments, recognized named entities can be used to construct at least one index of web pages or documents including named entities that can be accessed by a natural language processing application.

Claims

1. A method of identifying named entities in natural language text comprising the steps of:

receiving natural language text;

specifying regular expression rules corresponding to patterns of named entities in the natural language text;

applying the regular expression rules to the natural language text using a lexical analyzer generated by a lexical analyzer generator to identify named entities in the natural language text.

2. The method of identifying named entities of claim 1, wherein specifying regular expression rules comprises specifying a set of regular expression rules for each class of named entities, wherein each class of named entity corresponds with a pattern in the natural language text.

3. The method of identifying named entities of claim 1, wherein applying the regular expression rules comprises using a lexical analyzer generated by one of Lex, Flex, Jlex, Jflex, or an equivalent tool.

4. The method of identifying named entities of claim 1, and further comprising generating annotations corresponding to the identified named entities.

5. The method of identifying named entities of claim 4, wherein generating annotations comprises generating a named entity class identifier and a position indicator for each identified named entity.

6. The method of identifying named entities of claim 1, wherein specifying regular expression rules comprises specifying regular expression rules for patterns corresponding to at least one of the following classes of named entities:

a digit class, a currency class, a percentage class, a date expression class, a time expression class, a filename class, a file path class, an email address class, a web address class, and a URL class.

7. The method of identifying named entities of claim 1, wherein specifying regular expression rules comprises specifying regular expression rules for patterns corresponding to at least one of the following classes of named entities:

day name class and month name class.

8. The method of identifying named entities of claim 1, and further comprising word breaking to identify words in the natural language text.

28. The computer readable medium of claim 1, wherein the full parser recognizes each named entity string as a single token.

29. The computer readable medium of claim 28, wherein the full parser parses the annotated text into grammatical structures.

9. A method of recognizing named entities in natural language text comprising the steps of:

receiving natural language text;

specifying possible named entities using grammar rules; and

processing the natural language text using a parser generated by a parser generator to identify the possible named entities based on the set of grammar rules.

10. The method of identifying named entities of claim 9, wherein processing the natural language text comprising using a parser generated by one of Yacc, Bison, or an equivalent tool.

11. The method of identifying named entities of claim 9, wherein specifying possible named entities comprises using sets of grammar rules corresponding to classes of named entities in the natural language text.

12. The method of identifying named entities of claim 11, wherein processing the natural language text comprises:

recognizing possible named entities in at least one class of named entities; and

identifying the named entities from among the possible named entities based on probability.

13. The method of identifying named entities of claim 12, wherein identifying the named entities from among the possible named entities comprises using a Linguistic Service Platform lattice and statistical language model to calculate probabilities for at least some of the possible named entities.

14. A method of recognizing named entities from natural language input text comprising the steps of:

receiving natural language text;

accessing at least one named entity lexicon using a parser generated by a parser generator designed to parse computer programs; and

identifying named entities based on look up in at least one named entity lexicon.

15. A method of identifying named entities in natural language text comprising the steps of:

receiving natural language text;

applying regular expression rules to the natural language text to generate annotations corresponding to named entities or named entity constituent strings; and

applying grammar rules to the annotations to identify named entities in the natural language text.

16. The method of claim 15, wherein applying regular expression rules comprises using a lexical analyzer generated by a lexical analyzer generator and wherein applying the grammar rules comprises using a parser generated by a parser generator.

17. A computer readable medium including computer executable instructions performing the steps of:

receiving text in a natural language;

generating annotations using at least one lexical analyzer applying a set of regular expression rules, each annotation corresponding to a named entity or constituent character string of a named entity; and

generating annotations using at least one parser applying a set of grammar rules, each annotation corresponding to a named entity.

18. The computer readable medium of claim 17, wherein individual annotations generated by the at least one lexical analyzer correspond to a named entity or constituent character string classified in at least one of the following classes of named entities:

a digit class, a currency class, a date expression class, a time expression class, a filename class, a file path class, an email address class, and a web address class.

19. The computer readable medium of claim 17, wherein the at least one lexical analyzer applies regular expression rules to generate annotations classified in at least one of the following classes:

day name, month name, person title, currency name, number word, and company designator.

20. The computer readable medium of claim 17, wherein the at least one parser applies grammar rules to generate named entity annotations classified in at least one of the following classes of named entities:

a number class, a date class, a time class, a person name class, a location name class, and an organization name class.

21. The computer readable medium of claim 17, and further comprising using one of the parsers to access a lexicon of person name constituents to generate named entity annotations classified in the person name class.

22. The computer readable medium of claim 17, and further comprising using one of the parsers to access a lexicon of location name constituents to generate named entity annotations classified in the location name class.

23. The computer readable medium of claim 17, and further comprising accessing a lexicon of organization name constituents to generate named entity annotations classified in the organization name class.

24. The computer readable medium of claim 17, wherein the steps further comprise constructing at least one web/document index including named entities corresponding to annotations generated by the lexical analyzers and parsers.

25. A method of generating a web/document index comprising the steps of:

using a named entity recognizer generated from a tool used to parse computer programs to identify named entities in web pages/documents; and

constructing a web/document index of web pages/documents based in part on the named entities identified within the web pages/documents.

26. A computer readable medium having stored thereon computer readable instructions which, when read by the computer cause the computer to perform steps of:

receiving a natural language input through an application programming interface (API);

providing the natural language input to one or more natural language processing (NLP) components, including a named entity recognizer to perform named entity analysis operations on the natural language input using a compiler tool designed to parse computer programs, the named entity analysis operations selected from a plurality of different possible NLP analysis operations selectable through the API; and

returning analysis results from the named entity operations through the API.

27. A computer readable medium including computer executable instructions performing the steps of:

receiving natural language text;

processing the natural language text using a lexical analyzer and a parser to generate named entity annotated text, wherein the lexical analyzer and the parser are generated from tools used to parse computer programs; and

processing the named entity annotated text using a full parser to generate fully parsed text.

30. The computer readable medium of claim 27, wherein the lexical analyzer is generated by Flex or its equivalent lexical analyzer generator, and wherein the parser is generated by Yacc or its equivalent parser generator.