Managing an archive for approximate string matching

• US 8,775,441 B2
• Filed: 01/16/2008
• Issued: 07/08/2014
• Est. Priority Date: 01/16/2008
• Status: Active Grant

• Current Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Original Assignee: Ab Initio Technology LLC (Ab Initio Software Corporation)
• Inventors: Anderson, Arlen
• Primary Examiner(s): GOFMAN, ALEX N
• Application Number:
  US12/015,085
• Publication Number:
  US 20090182728A1
• Time in Patent Office: 2,365 Days
• Field of Search: 707/802, 707/999.5, 707/750, 707/749
• US Class Current: 707/749
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/90344 by using string matching techniques

Abstract

In one aspect, in general, a method is described for managing an archive. The archive is used for determining approximate matches associated with strings occurring in records. The method includes processing records to determine a set of string representations that correspond to strings occurring in the records. The method also includes generating, for each of at least some of the string representations in the set, a plurality of close representations that are each generated from at least some of the same characters in the string. The method also includes storing entries in the archive. Each stored entry represents a potential approximate match between at least two strings based on their respective close representations.

Claims

1. A method for managing an archive for determining approximate matches associated with strings occurring in records, the method including:

determining a set of strings occurring in the records, the set of strings including a first string;

generating, for each of the strings in the set, a plurality of deletion variants that are each generated by deleting one or more characters from the corresponding string;

for the first string, identifying one or more potentially matching strings in the set of strings, each potentially matching string of the potentially matching strings identified in response to determining that any deletion variant of the first string matches any deletion variant of the potentially matching string;

for each of the potentially matching strings, calculating a corresponding match score;

for at least some of the potentially matching strings, storing a record in the archive identifying the first string, the potentially matching string, and the match score;

determining a count of occurrences of the first string in the records;

for each of the potentially matching strings, determining a count of occurrences of the respective potentially matching string in the records; and

generating a significance value for the first string based on a sum of at least the count of occurrences of the string and the count of occurrences of each of the one or more potentially matching strings.

2. The method of claim 1, wherein generating the plurality of deletion variants for a given string in the set includes generating deletion variants that each have a different character deleted from the given string.

3. The method of claim 2, wherein generating the plurality of deletion variants for a given string in the set includes generating deletion variants that each have a single character deleted from the given string.

4. The method of claim 3, wherein generating the plurality of deletion variants for a given string in the set includes generating deletion variants at least some of which have multiple characters deleted from the given string.

5. The method of claim 2, wherein generating deletion variants that each have a different character deleted from the given string includes generating deletion variants that each have a single character deleted from the given string if the given string is shorter than a predetermined length, and generating deletion variants at least some of which have multiple characters deleted from the given string if the given string is longer than the predetermined length.

6. The method of claim 1, wherein the significance value is based on an inverse of the sum.

7. The method of claim 1, further including determining whether different phrases that include multiple strings correspond to an approximate match by determining whether strings within the phrases correspond to an approximate match, wherein the strings within the phrases are selected based on their corresponding significance values.

8. The method of claim 7, wherein the significance value of a string within a phrase is based on the sum, and is based on at least one of a length of the string, a position of the string in the phrase, a field of a record in which the string occurs, and a source of a record in which the field occurs.

9. The method of claim 1, further including generating, for each of at least some of the potentially matching strings, a score that quantifies a quality of the potential approximate match between the first string and the respective potentially matching string.

10. The method of claim 9, further including determining whether the first string and the respective potentially matching string are an approximate match by comparing the score associated with the entry to a threshold.

11. The method of claim 9, wherein the score is based on a correspondence between the respective deletion variants used to determine the potential approximate match between the first string and the respective potentially matching string.

12. The method of claim 9, further including identifying potential approximate matches which are probable false positives.

13. The method of claim 12, wherein a probable false positive potential approximate match between the first string and a second string of the potentially matching strings is identified based on a frequency of occurrence of the first string in the records and a frequency of occurrence of the second string in the records.

14. The method of claim 12, wherein a probable false positive potential approximate match is identified based on n-gram frequencies.

15. The method of claim 12, further including adjusting the score associated with the entry representing a potential approximate match in response to identification of the potential approximate match as a probable false positive.

16. The method of claim 1, further including modifying a string occurring in at least one record to generate a modified string to include in the set of strings.

17. The method of claim 16, wherein modifying the string includes removing or replacing punctuation.

18. The method of claim 16, wherein modifying the string includes encoding the string into a different representation.

19. The method of claim 18, wherein modifying the string includes encoding the string into a numerical representation.

20. The method of claim 19, wherein encoding the string into a numerical representation includes mapping each character in the string to a prime number and representing the string as the product of the prime numbers mapped to the characters in the string.

21. The method of claim 1, wherein the generating the significance value for the first string includes calculating the inverse of the sum of:

the frequency of occurrence of the corresponding string in the records, and

the frequency of occurrence of a string represented in the archive as a potential approximate match to the corresponding string in the records.

22. A computer program, stored on a non-transitory computer-readable medium, for managing an archive for determining approximate matches associated with strings occurring in records, the computer program including instructions for causing a computer to:

determine a set of s strings occurring in the records, the set of strings including a first string;

generate, for each of the strings in the set, a plurality of deletion variants that are each generated by deleting one or more characters from the corresponding string;

for the first string, identify one or more potentially matching strings in the set of strings, each potentially matching string of the potentially matching strings identified in response to determining that any deletion variant of the first string matches any deletion variant of the potentially matching string;

for each of the potentially matching strings, calculate a corresponding match score;

for at least some of the potentially matching strings, store a record in the archive identifying the first string, the potentially matching string, and the match score;

determine a count of occurrences of the first string in the records;

for each of the potentially matching strings, determine a count of occurrences of the respective potentially matching string in the records; and

generate a significance value for the first string based on a sum of at least the count of occurrences of the string and the count of occurrences of each of the one or more potentially matching strings.

23. The computer program of claim 22, wherein generating the plurality of deletion variants for a given string in the set includes generating deletion variants that each have a different character deleted from the given string.

24. The computer program of claim 23, wherein generating the plurality of deletion variants for a given string in the set includes generating deletion variants that each have a single character deleted from the given string.

25. The computer program of claim 24, wherein generating the plurality of deletion variants for a given string in the set includes generating deletion variants at least some of which have multiple characters deleted from the given string.

26. The computer program of claim 23, wherein generating deletion variants that each have a different character deleted from the given string includes generating deletion variants that each have a single character deleted from the given string if the given string is shorter than a predetermined length, and generating deletion variants at least some of which have multiple characters deleted from the given string if the given string is longer than the predetermined length.

27. The computer program of claim 22, wherein the significance value is based on an inverse of the sum.

28. The computer program of claim 22, further including determining whether different phrases that include multiple strings correspond to an approximate match by determining whether strings within the phrases correspond to an approximate match, wherein the strings within the phrases are selected based on their corresponding significance values.

29. The computer program of claim 28, wherein the significance value of a string within a phrase is based on the sum, and is based on least one of a length of the string, a position of the string in the phrase, a field of a record in which the string occurs, and a source of a record in which the field occurs.

30. A system for managing an archive for determining approximate matches associated with strings occurring in records, the system including:

means for determining a set strings occurring in the records, the set of strings including a first string;

means for generating, for each of the strings in the set, a plurality of deletion variants that are each generated by deleting one or more characters from the corresponding string;

means for identifying, for the first string, one or more potentially matching strings in the set of strings, each potentially matching string of the potentially matching strings identified in response to determining that any deletion variant of the first string matches any deletion variant of the potentially matching string;

means for calculating, for each of the potentially matching strings, a corresponding match score;

means for storing, for at least some of the potentially matching strings, a record in the archive identifying the first string, the potentially matching string, and the match score;

means for determining a count of occurrences of the first string in the records;

means for determining, for each of the potentially matching strings, a count of occurrences of the respective potentially matching string in the records; and

means for generating a significance value for the first string based on a sum of at least the count of occurrences of the string and the count of occurrences of each of the one or more potentially matching strings.

31. The system of claim 30, wherein generating the plurality of deletion variants for a given string in the set includes generating deletion variants that each have a different character deleted from the given string.

32. The system of claim 31, wherein generating the plurality of deletion variants for a given string in the set includes generating deletion variants that each have a single character deleted from the given string.

33. The system of claim 32, wherein generating the plurality of deletion variants for a given string in the set includes generating deletion variants at least some of which have multiple characters deleted from the given string.

34. The system of claim 31, wherein generating deletion variants that each have a different character deleted from the given string includes generating deletion variants that each have a single character deleted from the given string if the given string is shorter than a predetermined length, and generating deletion variants at least some of which have multiple characters deleted from the given string if the given string is longer than the predetermined length.

35. The system of claim 30, wherein the significance value is based on an inverse of the sum.

36. The system of claim 30, further including determining whether different phrases that include multiple strings correspond to an approximate match by determining whether strings within the phrases correspond to an approximate match, wherein the strings within the phrases are selected based on their corresponding significance values.

37. The system of claim 36, wherein the significance value of a string within a phrase is based on the sum, and is based on least one of a length of the string, a position of the string in the phrase, a field of a record in which the string occurs, and a source of a record in which the field occurs.

38. A system for managing an archive for determining approximate matches associated with strings occurring in records, the system including:

a data source storing records;

a computer system configured to

determine a set of strings occurring in the records, the set of strings including a first string;

generate, for each of the strings in the set, a plurality of deletion variants that are each generated by deleting one or more characters from the corresponding string;

for the first string, identify one or more potentially matching strings in the set of strings, each potentially matching string of the potentially matching strings identified in response to determining that any deletion variant of the first string matches any deletion variant of the potentially matching string;

for each of the potentially matching strings, calculate a corresponding match score;

for at least some of the potentially matching strings, store a record in the archive identifying the first string, the potentially matching string, and the match score;

determine a count of occurrences of the first string in the records;

determine, for each of the potentially matching strings, a count of occurrences of the respective potentially matching string in the records; and

generate a significance value for the first string based on a sum of at least the count of occurrences of the string and the count of occurrences of each of the one or more potentially matching strings; and

a data store coupled to the computer system to store an archive including entries that each represent a potential approximate match between at least two strings.

39. The system of claim 38, wherein generating the plurality of deletion variants for a given string in the set includes generating deletion variants that each have a different character deleted from the given string.

40. The system of claim 39, wherein generating the plurality of deletion variants for a given string in the set includes generating deletion variants that each have a single character deleted from the given string.

41. The system of claim 40, wherein generating the plurality of deletion variants for a given string in the set includes generating deletion variants at least some of which have multiple characters deleted from the given string.

42. The system of claim 39, wherein generating deletion variants that each have a different character deleted from the given string includes generating deletion variants that each have a single character deleted from the given string if the given string is shorter than a predetermined length, and generating deletion variants at least some of which have multiple characters deleted from the given string if the given string is longer than the predetermined length.

43. The system of claim 38, wherein the significance value is based on an inverse of the sum.

44. The system of claim 38, further including determining whether different phrases that include multiple strings correspond to an approximate match by determining whether strings within the phrases correspond to an approximate match, wherein the strings within the phrases are selected based on their corresponding significance values.

45. The system of claim 44, wherein the significance value of a string within a phrase is based on the sum, and is based on least one of a length of the string, a position of the string in the phrase, a field of a record in which the string occurs, and a source of a record in which the field occurs.