System and method for variant string matching

• US 8,209,268 B2
• Filed: 01/26/2009
• Issued: 06/26/2012
• Est. Priority Date: 01/24/2008
• Status: Active Grant

• Current Assignee: SRA International, Inc. (General Dynamics Corporation)
• Original Assignee: SRA International, Inc. (General Dynamics Corporation)
• Inventors: Zelenko, Dmitry
• Primary Examiner(s): FERNANDEZ RIVAS, OMAR F
• Application Number:
  US12/359,924
• Publication Number:
  US 20090216689A1
• Time in Patent Office: 1,247 Days
• Field of Search: None
• US Class Current: 706/12
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 40/129 Handling non-Latin characters, e.g. kana-to-kanji conversion

Abstract

A method, computer program product, and system for variant string matching. A computer implemented method for variant string matching may comprise comparing with a computing device two unidentical strings in a training variant string pair. The two unidentical strings may represent the same item from training data, which may be stored in a memory. The two unidentical strings may be compared to determine if they include an identical substring pair, and a first unidentical substring pair. The computer implemented method may also determine if the first unidentical substring pair includes a first unidentical substring and a second unidentical substring. The computer implemented method may further determine if the first unidentical substring pair is in the training data. The first unidentical substring pair may be entered into the training data as a first variant string pair if it is not in the training data.

Claims

1. A computer implemented method for variant string matching, comprising:

comparing with a computing device two unidentical strings in a training variant string pair, the two unidentical strings representing the same item from training data in a memory, to determine if they include an identical substring pair and a first unidentical substring pair including a first unidentical substring and a second unidentical substring;

determining if the first unidentical substring pair is in the training data;

entering the first unidentical substring pair into the training data as a first variant string pair if it is not in the training data;

comparing with the computing device the two unidentical strings to determine if they include an interchangeable substring pair and a second unidentical substring pair including a third unidentical substring and a fourth unidentical substring;

determining if the second unidentical substring pair is in the training data; and

entering the second unidentical substring pair into the training data as a second variant string pair if it is not in the training data.

2. The computer implemented method of claim 1 further comprising incrementing with the computing device at least one of:

a first pair counter configured to increment if the first unidentical substring pair is in the training data;

a first substring counter configured to increment if the first unidentical substring is in the training data;

a second substring counter configured to increment if the second unidentical substring is in the training data;

a second pair counter configured to increment if the second unidentical substring pair is in the training data;

a third substring counter configured to increment if the third unidentical substring is in the training data; and

a fourth substring counter configured to increment if the fourth unidentical substring is in the training data.

3. The computer implemented method of claim 2 further comprising:

generating with the computing device a matching score for at least one variant string pair in the training data, based upon, at least in part, at least one of the first pair counter, the first substring counter, the second substring counter, the second pair counter, the third substring counter, and the fourth substring counter.

4. The computer implemented method of claim 3 further comprising:

generating with the computing device a string distance for at least one variant string pair in the training data, based upon, at least in part, a matching score generated for at least one of the first unidentical substring pair and the second unidentical substring pair.

5. The computer implemented method of claim 4 further comprising:

searching with the computing device for a string having at least one substring, the at least one substring having at least one variant string included in the training data; and

generating with the computing device at least one result including the at least one variant string.

6. The computer implemented method of claim 5 further comprising:

merging a plurality of strings from at least two sources into one source based upon, at least in part, the matching score for at least one variant string pair having a first substring in a first source and a second substring in a second source.

7. The computer implemented method of claim 6 further comprising:

dynamically displaying a variant display string in a graphical user interface, based upon, at least in part, a variant display string pair including the variant display string and a string in the graphical user interface.

8. A computer program product residing on a non-transitory computer readable medium having a plurality of instructions stored thereon, which, when executed by a processor, cause the processor to perform operations comprising:

comparing two unidentical strings in a training variant string pair, the two unidentical strings representing the same item from training data in a memory, to determine if they include an identical substring pair and a first unidentical substring pair including a first unidentical substring and a second unidentical substring;

determining if the first unidentical substring pair is in the training data; and

entering the first unidentical substring pair into the training data as a first variant string pair if it is not in the training data

comparing the two unidentical strings to determine if they include an interchangeable substring pair and a second unidentical substring pair including a third unidentical substring and a fourth unidentical substring;

determining if the second unidentical substring pair is in the training data; and

entering the second unidentical substring pair into the training data as a second variant string pair if it is not in the training data.

9. The computer program product of claim 8 further comprising instructions for incrementing at least one of:

a first pair counter configured to increment if the first unidentical substring pair is in the training data;

a first substring counter configured to increment if the first unidentical substring is in the training data;

a second substring counter configured to increment if the second unidentical substring is in the training data;

a second pair counter configured to increment if the second unidentical substring pair is in the training data;

a third substring counter configured to increment if the third unidentical substring is in the training data; and

a fourth substring counter configured to increment if the fourth unidentical substring is in the training data.

10. The computer program product of claim 9 further comprising instructions for:

generating a matching score for each variant string pair in the training data, based upon, at least in part, at least one of the first pair counter, the first substring counter, the second substring counter, the second pair counter, the third substring counter, and the fourth substring counter.

11. The computer program product of claim 10 further comprising instructions for:

generating with the computing device a string distance for at least one variant string pair in the training data, based upon, at least in part, a matching score generated for at least one of the first unidentical substring pair and the second unidentical substring pair.

12. The computer program product of claim 11 further comprising instructions for:

searching for a string having at least one substring, the at least one substring having at least one variant string included in the training data; and

generating at least one result including the at least one variant string.

13. The computer program product of claim 12 further comprising instructions for:

merging a plurality of strings from at least two sources into one source based upon, at least in part, the matching score for at least one variant string pair having a first substring in a first source and a second substring in a second source.

14. The computer program product of claim 13 further comprising instructions for:

dynamically displaying a variant display string in a graphical user interface, based upon, at least in part, a variant display string pair including the variant display string and a string in the graphical user interface.