Natural language parsers to normalize addresses for geocoding

• US 8,868,479 B2
• Filed: 09/29/2008
• Issued: 10/21/2014
• Est. Priority Date: 09/28/2007
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Telogis Incorporated (Verizon Communications Inc.)
• Inventors: Mitchell, David John, Morris, Arthur Newth IV, Mason, Ralph James
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): COUGHLAN, PETER D
• Application Number:
  US12/240,853
• Publication Number:
  US 20090248605A1
• Time in Patent Office: 2,213 Days
• Field of Search: 434/130
• US Class Current: 706/46
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/295 Named entity recognition

Abstract

The present invention provides a technique for building natural language parsers by implementing a country and/or jurisdiction specific set of training data that is automatically converted during a build phase to a respective predictive model, i.e., an automated country specific natural language parser. The predictive model can be used without the training data to quantify any input address. This model may be included as part of a larger Geographic Information System (GIS) data-set or as a stand alone quantifier. The build phase may also be run on demand and the resultant predictive model kept in temporary storage for immediate use.

Claims

1. A method for normalizing an input address comprising the steps of:

under control of a computer system comprising computer hardware;

receiving an input address indicative of a physical address;

parsing the input address into components;

classifying each component with a preliminary address field classification according to;

one or more predetermined regular expressions and a lexicon of known tokens, thereby generating classified components, wherein said classifying each component is performed by matching each component to the one or more predetermined regular expressions only when there is no match between that component and the lexicon of known tokens;

determining which of at least one of a plurality of countries and jurisdictions corresponds to the address input;

selecting a predictive model corresponding to the address input from a plurality of predictive models, each of the plurality of predictive models being an automated country-specific natural language parser uniquely defined for a corresponding one of the plurality of countries and jurisdictions, the selected predictive model comprising a graph having address field nodes and edges connecting the address field nodes, each address field node comprising an address field and a corresponding set of one or more address field classifications each assigned a first probability value, and each edge assigned a second probability value; and

executing the selected predictive model to update the preliminary address field classification of at least some of the classified components with one of the address fields in the graph based at least partly on the first and second probability values of the address field nodes and the edges that correspond to the preliminary address field classification of each component.

2. The method of claim 1, further comprising the step of executing the predictive model to generate a probability associated with each unique address field.

3. The method of claim 1, further comprising the step of generating the predictive model from a training file comprising the one or more predetermined regular expressions and exemplary tokens.

4. The method of claim 3, wherein the training file is associated with a particular country or jurisdiction.

5. The method of claim 1, wherein the predictive model comprises a table of probabilities associated with the unique address fields.

6. A method of constructing a natural language parser comprising the steps of:

loading a training file defining an acceptable format for one or more regular expressions and comprising selected address field and token pairs;

parsing the training file into a number of tokens;

classifying the tokens with preliminary address field classifications according to a lexicon of known tokens and the regular expressions, wherein said classifying the tokens is performed by matching each of the tokens to one of the regular expressions only when there is no match between the token and the lexicon of known tokens; and

generating a plurality of predictive models so as to be uniquely defined for a corresponding unique country or jurisdiction and so as to define a probability for each of one or more address fields that may be associated with a given token, each of the predictive models being an automated country-specific natural language parser comprising a graph having address field nodes and edges connecting the address field nodes, each address field node comprising an address field and a corresponding set of one or more address field classifications each assigned a first probability value, and each edge assigned a second probability value,

wherein the predictive models are each configured to associate components of an input address with unique address fields by assigning each of the components one of the address fields in the graph based at least partly on the first and second probability values of the address field nodes and the edges that correspond to the preliminary address field classifications of the tokens;

wherein at least said generating is implemented by a computer system comprising computer hardware.

7. The method of claim 6, further comprising the step of identifying the most likely address field for each of the classified tokens.

8. The method of claim 6, wherein the training file is specific to a unique country or jurisdiction.

9. The method of claim 6, further comprising the step of calculating the probability based on a number of times each classified token ends up in a given address field.

10. The method of claim 6, wherein the training file indicates the relative positions of each exemplary token.

11. A non-transitory computer readable medium encoded with computer readable program code, the program code comprising the instructions of:

parsing an input address into components;

classifying each component with a preliminary classification according to;

one or more predetermined regular expressions and a lexicon of known tokens, thereby generating classified components, wherein said classifying each component is performed by matching a component to the one or more predetermined regular expressions only when there is no match between that component and the lexicon of known tokens; and

executing a selected one of a plurality of different predictive models to associate each classified component with a unique address field, wherein the predictive models are respectively associated with particular countries or jurisdictions, the selected predictive model being an automated country-specific natural language parser comprising a graph having address field nodes and edges connecting the address field nodes, each address field node comprising an address field and a corresponding set of one or more address field classifications each assigned a first probability value, and each edge assigned a second probability value;

said executing the selected predictive model to associate each classified component with a unique address field by updating the preliminary address field classification of each of the classified components with one of the address fields in the graph based at least partly on the first and second probability values of the nodes and the edges that correspond to the preliminary address field classification of each component.

12. The non-transitory computer readable medium of claim 11, further comprising the instruction of executing the predictive model to generate a probability associated with each unique address field.

13. The non-transitory computer readable medium of claim 11, further comprising the instruction of generating the predictive model from a training file comprising the one or more predetermined regular expressions and exemplary tokens.

14. The non-transitory computer readable medium of claim 13, wherein the training file is associated with a particular country or jurisdiction.

15. The non-transitory computer readable medium of claim 11, wherein the predictive model comprises a table of probabilities associated with the unique address fields.

16. The non-transitory computer readable medium of claim 11, in combination with a computer system comprising computer hardware.