Managing an Archive for Approximate String Matching

• US 20090182728A1
• Filed: 01/16/2008
• Published: 07/16/2009
• 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
• Granted Patent: US 8,775,441 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 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; 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; and storing entries in the archive that each represent 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:

processing records to determine a set of string representations that correspond to strings occurring in the records;

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; and

storing entries in an archive that each represent a potential approximate match between at least two strings based on their respective close representations.

2. The method of claim 1, wherein each string representation comprises a string.

3. The method of claim 2, wherein each close representation consists of at least some of the same characters in the string.

4. The method of claim 3, wherein generating the plurality of close strings for a given string in the set includes generating close strings that each have a different character deleted from the given string.

5. The method of claim 4, wherein generating the plurality of close strings for a given string in the set includes generating close strings that each have a single character deleted from the given string.

6. The method of claim 5, wherein generating the plurality of close strings for a given string in the set includes generating close strings at least some of which have multiple characters deleted from the given string.

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

8. The method of claim 1, further including determining, for each of at least some of the string representations in the set, a frequency of occurrence of the corresponding string in the records.

9. The method of claim 8, further including generating, for each of at least some of the string representations in the set, a significance value that represents a significance of the corresponding string based on a sum that includes the frequency of occurrence of the string and the frequencies of occurrence of at least some strings represented in the archive as a potential approximate match to the string.

10. The method of claim 9, wherein the significance value is generated based on an inverse of the sum.

11. The method of claim 9, 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.

12. The method of claim 11, 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.

13. The method of claim 1, further including generating, for each of at least some of the entries in the archive, a score associated with the entry that quantifies a quality of the potential approximate match between at least two strings.

14. The method of claim 13, further including determining whether strings associated with an entry correspond to an approximate match by comparing the score associated with the entry to a threshold.

15. The method of claim 13, wherein the score is based on a correspondence between the respective close representations used to determine the potential approximate match between the at least two strings.

16. The method of claim 1, wherein processing the records to determine a set of string representations that correspond to strings occurring in the records includes modifying a string occurring in at least one record to generate a modified string to include in the set of string representations.

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 archive includes at least some entries that represent a potential approximate match between at least two strings based on input from a user.

25. The method of claim 1 wherein each of the entries includes the strings between which there is a potential approximate match and a score that quantifies a quality of the potential approximate match between the strings.

26. The method of claim 1, further including generating, for each of at least some of the string representations in the set, a significance value that represents a significance of the corresponding string based on a frequency of occurrence of the corresponding string.

27. The method of claim 13, further including identifying potential approximate matches which are probable false positives using the entries in the archive.

28. The method of claim 27, wherein a probable false positive potential approximate match between a first string and a second string 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.

29. The method of claim 27, wherein a probable false positive potential approximate match is identified based on n-gram frequencies stored in the archive.

30. The method of claim 27, 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.

22. A computer program, stored on a 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:

process records to determine a set of string representations that correspond to strings occurring in the records;

generate, 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; and

store entries in an archive that each represent a potential approximate match between at least two strings based on their respective close representations.

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

means for processing records to determine a set of string representations that correspond to strings occurring in the records;

means for 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; and

means for storing entries in an archive that each represent a potential approximate match between at least two strings based on their respective close representations.

24. 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

process the records in the data source to determine a set of string representations that correspond to strings occurring in the records, and

generate, 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; 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 based on their respective close representations.