Managing an archive for approximate string matching

• US 9,563,721 B2
• Filed: 07/07/2014
• Issued: 02/07/2017
• 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:
  US14/325,007
• Publication Number:
  US 20150066862A1
• Time in Patent Office: 946 Days
• Field of Search: None
• 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;

for each of at least some of the string representations in the set,

generating a plurality of close representations for that string representation, wherein each of the plurality of close representations is generated from at least some of the same characters in at least one of the strings occurring in at least one of the records processed to determine that string representation;

comparing first close representations that are each generated from at least some characters in at least a first one of the strings occurring in at least one of the records processed to determine a first one of the string representations to second close representations that are each generated from at least some characters in at least a second one of the strings occurring in at least one of the records processed to determine a second one of the string representations, wherein the first close representations are for the first one of the string representations, and wherein the second close representations are for the second one of the string representations;

identifying which one of the first close representations that are each generated from at least some characters in at least the first one of the strings occurring in at least one of the records processed to determine the first one of the string representations corresponds to which one of the second close representations that are each generated from at least some characters in at least the second one of the strings occurring in at least one of the records processed to determine the second one of the string representations; and

based on identified correspondences between close representations, 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 a close representation includes a substring of the string representation.

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:

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

for each of at least some of the string representations in the set,

generate a plurality of close representations for that string representation, wherein each of the plurality of close representations is generated from at least some of the same characters in at least one of the strings occurring in at least one of the records processed to determine that string representation;

compare first close representations that are each generated from at least some characters in at least a first one of the strings occurring in at least one of the records processed to determine a first one of the string representations to second close representations that are each generated from at least some characters in at least a second one of the strings occurring in at least one of the records processed to determine a second one of the string representations, wherein the first close representations are for the first one of the string representations, and wherein the second close representations are for the second one of the string representations;

identify which one of the first close representations that are each generated from at least some characters in at least the first one of the strings occurring in at least one of the records processed to determine the first one of the string representations corresponds to which one of the second close representations that are each generated from at least some characters in at least the second one of the strings occurring in at least one of the records processed to determine the second one of the string representations; and

based on identified correspondences between close representations, 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;

for each of at least some of the string representations in the set,

means for generating a plurality of close representations for that string representation, wherein each of the plurality of close representations is generated from at least some of the same characters in at least one of the strings occurring in at least one of the records processed to determine that string representation;

means for comparing first close representations that are each generated from at least some characters in at least a first one of the strings occurring in at least one of the records processed to determine a first one of the string representations to second close representations that are each generated from at least some characters in at least a second one of the strings occurring in at least one of the records processed to determine a second one of the string representations, wherein the first close representations are for the first one of the string representations, and wherein the second close representations are for the second one of the string representations;

means for identifying which one of the first close representations that are each generated from at least some characters in at least the first one of the strings occurring in at least one of the records processed to determine the first one of the string representations corresponds to which one of the second close representations that are each generated from at least some characters in at least the second one of the strings occurring in at least one of the records processed to determine the second one of the string representations; and

based on identified correspondences between close representations, 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 records to determine a set of string representations that correspond to strings occurring in the records;

for each of at least some of the string representations in the set,

generate a plurality of close representations for that string representation, wherein each of the plurality of close representations is generated from at least some of the same characters in at least one of the strings occurring in at least one of the records processed to determine that string representation;

compare first close representations that are each generated from at least some characters in at least a first one of the strings occurring in at least one of the records processed to determine a first one of the string representations to second close representations that are each generated from at least some characters in at least a second one of the strings occurring in at least one of the records processed to determine a second one of the string representations, wherein the first close representations are for the first one of the string representations, and wherein the second close representations are for the second one of the string representations;

identify which one of the first close representations that are each generated from at least some characters in at least the first one of the strings occurring in at least one of the records processed to determine the first one of the string representations corresponds to which one of the second close representations that are each generated from at least some characters in at least the second one of the strings occurring in at least one of the records processed to determine the second one of the string representations; and

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