Methods and systems for matching records and normalizing names

• US 8,190,538 B2
• Filed: 01/30/2009
• Issued: 05/29/2012
• Est. Priority Date: 01/30/2009
• Status: Active Grant

• Current Assignee: RELX Inc. (RELX PLC)
• Original Assignee: LexisNexis Group Inc. (RELX PLC)
• Inventors: Zhang, Ling Qin, Wasson, Mark, Templar, Valentina
• Primary Examiner(s): Holmes, Michael B
• Application Number:
  US12/363,057
• Publication Number:
  US 20100198756A1
• Time in Patent Office: 1,215 Days
• Field of Search: 706/12
• US Class Current: 706/12
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 40/295 Named entity recognition

Abstract

Methods and systems are provided for normalizing strings and for matching records. In one implementation, a string is tokenized into components. Sequences of tags are generated by assigning tags to the components. A sequence of states is determined based on the sequences of tags. A normalized string is generated by normalizing the sequence of the states. A key record including key fields is extracted from a first data source. A candidate record including candidate fields is extracted from a second data source. A numerical record including numerical fields is computed by comparing the key fields and the candidate fields using comparison functions. Matching functions determined by an additive logistic regression method are applied to the numerical fields. Whether the key record and the candidate record are a match is determined based on a sum of results of the matching functions.

Claims

1. A computer-implemented method of normalizing strings, comprising:

tokenizing a string into a sequence of components;

generating one or more sequences of tags by assigning tags to the components based on lookup tables;

determining, using a processor, a sequence of states of the components based on the one or more sequences of tags; and

generating a normalized string by normalizing the sequence of the states.

2. The method of claim 1, further comprising:

determining a similarity between the normalized string and another normalized string of another string using a similarity function.

3. The method of claim 2, wherein the similarity function applies weights to the components.

4. The method of claim 1, wherein the normalizing comprises:

combining consecutive components with a same state; and

normalizing the components based on the lookup tables including normal forms.

5. The method of claim 1, wherein:

the string is a law firm name; and

the tags and the states include at least one of people, initial, specialty, organization, suffix, and separator.

6. The method of claim 1, wherein determining the sequence of states of the components comprises using a hidden Markov model and a Viterbi algorithm.

40. The method of claim 1, wherein assigning tags to the components based on lookup tables further comprises:

determining that one or more components has not been tagged; and

assigning tags to the one or more untagged components based on a set of rules.

7. A system for normalizing strings, comprising:

a processor;

means for tokenizing a string into a sequence of components;

means for generating one or more sequences of tags by assigning tags to the components based on lookup tables;

means for determining a sequence of states of the components based on the one or more sequences of tags; and

means for generating a normalized string by normalizing the sequence of the states.

8. The system of claim 7, further comprising:

means for determining a similarity between the normalized string and another normalized string of another string using a similarity function.

9. The system of claim 8, wherein the similarity function applies weights to the components.

10. The system of claim 7, wherein the means for generating the normalized string comprises:

means for combining consecutive components with a same state; and

means for normalizing the components based on the lookup tables including normal forms.

11. The system of claim 7, wherein:

the string is a law firm name; and

the tags and the states include at least one of people, initial, specialty, organization, suffix, and separator.

12. The system of claim 7, wherein the means for determining the sequence of states of the components comprises means for using a hidden Markov model and a Viterbi algorithm.

41. The system of claim 7, wherein assigning tags to the components based on lookup tables further comprises:

means for determining that one or more components has not been tagged; and

means for assigning tags to the one or more untagged components based on a set of rules.

13. A computer-readable storage medium including instructions which, when executed by a processor, perform a method of normalizing strings, the method comprising:

tokenizing a string into a sequence of components;

generating one or more sequences of tags by assigning tags to the components based on lookup tables;

determining a sequence of states of the components based on the one or more sequences of tags; and

generating a normalized string by normalizing the sequence of the states.

14. The computer-readable storage medium of claim 13, wherein the method further comprises:

determining a similarity between the normalized string and another normalized string of another string using a similarity function.

15. The computer-readable storage medium of claim 14, wherein the similarity function applies weights to the components.

16. The computer-readable storage medium of claim 13, wherein the normalizing comprises:

combining consecutive components with a same state; and

normalizing the components based on the lookup tables including normal forms.

17. The computer-readable storage medium of claim 13, wherein:

the string is a law firm name; and

the tags and the states include at least one of people, initial, specialty, organization, suffix, and separator.

18. The computer-readable storage medium of claim 13, wherein determining the sequence of states of the components comprises using a hidden Markov model and a Viterbi algorithm.

42. The computer-readable storage medium of claim 13, wherein assigning tags to the components based on lookup tables further comprises:

determining that one or more components has not been tagged; and

assigning tags to the one or more untagged components based on a set of rules.

19. A computer-implemented method of matching records, comprising:

extracting a key record including key fields from a first data source;

retrieving a candidate record including candidate fields from a second data source, the candidate fields corresponding to the key fields;

computing, using a processor, a numerical record including numerical fields by comparing the key fields and the candidate fields using comparison functions, the numerical fields being result values of the comparison functions;

applying matching functions to the numerical fields, the matching functions being determined by an additive logistic regression method; and

determining whether the key record and the candidate record are a match based on a sum of results of the matching functions.

20. The method of claim 19, further comprising adding an additional numerical field to the numerical record by comparing a combination of two or more key fields with a combination of two or more candidate fields using a comparison function.

21. The method of claim 19, wherein the additive logistic regression method includes a plurality of training iterations.

22. The method of claim 21, wherein:

the training iterations produce decision functions; and

the matching function is determined based on the produced decision functions.

23. The method of claim 19, wherein the comparison functions include at least one of string comparison, word vector, and normalized similarity function.

24. The method of claim 19, wherein:

multiple candidate records are retrieved; and

if multiple candidate records are determined as matches, then the candidate record with the greatest sum of the result of the matching functions is determined to be the match.

25. The method of claim 19, wherein:

the key record and the candidate record are attorney records;

the first data source is a case law document; and

the second data source is an authority attorney directory.

26. A system for matching records, comprising:

a processor;

means for extracting a key record including key fields from a first data source;

means for retrieving a candidate record including candidate fields from a second data source, the candidate fields corresponding to the key fields;

means for computing a numerical record including numerical fields by comparing the key fields and the candidate fields using comparison functions, the numerical fields being result values of the comparison functions;

means for applying matching functions to the numerical fields, the matching functions being determined by an additive logistic regression method; and

means for determining whether the key record and the candidate record are a match based on a sum of results of the matching functions.

27. The system of claim 26, further comprising means for adding an additional numerical field to the numerical record by comparing a combination of two or more key fields with a combination of two or more candidate fields using a comparison function.

28. The system of claim 26, wherein the additive logistic regression method includes a plurality of training iterations.

29. The system of claim 28, wherein:

the training iterations produce decision functions; and

the matching function is determined based on the produced decision functions.

30. The system of claim 26, wherein the comparison functions include at least one of string comparison, word vector, and normalized similarity function.

31. The system of claim 26, wherein:

the means for retrieving retrieves multiple candidate records; and

if multiple candidate records are determined as matches, then the candidate record with the greatest sum of the result of the matching functions is determined to be the match.

32. The system of claim 26, wherein:

the key record and the candidate record are attorney records;

the first data source is a case law document; and

the second data source is an authority attorney directory.

33. A computer-readable storage medium including instructions which, when executed by a processor, perform a method of matching records, the method comprising:

extracting a key record including key fields from a first data source;

retrieving a candidate record including candidate fields from a second data source, the candidate fields corresponding to the key fields;

computing a numerical record including numerical fields by comparing the key fields and the candidate fields using comparison functions, the numerical fields being result values of the comparison functions;

applying matching functions to the numerical fields, the matching functions being determined by an additive logistic regression method; and

determining whether the key record and the candidate record are a match based on a sum of results of the matching functions.

34. The computer-readable storage medium of claim 33, wherein the additive logistic regression method includes a plurality of training iterations.

35. The computer-readable storage medium of claim 34, wherein the method further comprises adding an additional numerical field to the numerical record by comparing a combination of two or more key fields with a combination of two or more candidate fields using a comparison function.

36. The computer-readable storage medium of claim 34, wherein:

the training iterations produce decision functions; and

the matching function is determined based on the produced decision functions.

37. The computer-readable storage medium of claim 34, wherein the comparison functions include at least one of string comparison, word vector, and normalized similarity function.

38. The computer-readable storage medium of claim 34, wherein:

multiple candidate records are retrieved; and

if multiple candidate records are determined as matches, then the candidate record with the greatest sum of the result of the matching functions is determined to be the match.

39. The computer-readable storage medium of claim 34, wherein:

the key record and the candidate record are attorney records;

the first data source is a case law document; and

the second data source is an authority attorney directory.