COMPARING STRINGS OF CHARACTERS

• US 20130325884A1
• Filed: 05/29/2012
• Published: 12/05/2013
• Est. Priority Date: 05/29/2012
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: Sap Portals Israel Ltd (SAP SE)
• Inventors: Gorenchteine, Dmitry, Cohen, Udi, Soel, Shachar
• Granted Patent: US 8,732,183 B2
• Time in Patent Office: Days
• US Class Current: 707/758
• CPC Class Codes: G06F 40/194 Calculation of difference between files

Abstract

Techniques for comparing character strings include identifying a first character string having a first string length, and a second character string having a second string length greater than the first string length; parsing the first character string into one or more first sub-groups of characters; parsing the second character string into one or more second sub-groups of characters; comparing each of the one or more first sub-groups of characters against the one or more second sub-groups of characters; determining a ratio of a number of characters in the one or more first sub-groups of characters that match the one or more second sub-groups of characters and the second string length; and based on the ratio being greater or equal to a threshold, preparing at least one of the first or second character strings for display, the threshold including a variable value based on the first string length.

Claims

1. A computer-implemented method for comparing character strings, the method comprising:

identifying a first character string having a first string length, and a second character string having a second string length greater than the first string length;

parsing the first character string into one or more first sub-groups of characters;

parsing the second character string into one or more second sub-groups of characters;

comparing each of the one or more first sub-groups of characters against the one or more second sub-groups of characters;

determining a ratio of a number of characters in the one or more first sub-groups of characters that match the one or more second sub-groups of characters and the second string length; and

based on the ratio being greater or equal to a threshold, preparing at least one of the first or second character strings for display, the threshold comprising a variable value based on the first string length.

2. The method of claim 1, further comprising based on the ratio being less than the threshold,

matching the first character string to at least a first sub-group of the one or more second sub-groups of characters of the second character string;

and

based on a ratio of first string length and the second string length that is greater or equal to the threshold, preparing at least one of the first or second character strings for display.

3. The method of claim 1, further comprising based on the ratio being less than the threshold,

matching a first sub-group of the first character string with a first sub-group of the second character string;

matching a last sub-group of the first character string with a last sub-group of the second character string; and

based on a ratio of a combined length of the first and last sub-groups of the first character string and the second string length that is greater or equal to the threshold, preparing at least one of the first or second character strings for display.

4. The method of claim 1, further comprising based on the ratio being less than the threshold,

determining that the characters of the first character string match first characters of at least a subset of the one or more second sub-groups of characters;

determining a number of matched characters being equal to a sum of a number of characters in the subset of the one or more second sub-groups of characters;

determining a number of unmatched characters being equal to the second string length minus the number of matched characters; and

based on a ratio of the number of matched characters and the number of unmatched characters that is greater or equal to the threshold, preparing at least one of the first or second character strings for display.

5. The method of claim 1, further comprising, based on the ratio being less than the threshold, parsing the first character string into one or more first groups of trigrams, each of the first groups of trigrams comprising three characters of the first character string;

parsing the second character string into one or more second groups of trigrams, each of the second groups of trigrams comprising three characters of the second character string;

determining a number of trigram matches between the one or more first groups of trigrams and the one or more second groups of trigrams; and

based on a ratio of the number of trigram matches and a sum of the first and second groups of trigrams that is greater or equal to the threshold, preparing at least one of the first or second character strings for display.

6. The method of claim 5, further comprising, based on the ratio of the number of trigram matches and a sum of the first and second groups of trigrams being less than the threshold,

determining an edit distance value between the first character string and the second character string, the edit distance comprising a number of edits to the first character string so that the first character string matches the second character string;

determining a similarity of the first and second character strings based on a ratio of the edit distance of the first string distance; and

based on the similarity being greater or equal to the threshold, preparing at least one of the first or second character strings for display.

7. The method of claim 1, further comprising:

determining the variable value based on the first string length, a upper limit of the threshold, a lower limit of the threshold, and a growth rate of the threshold.

8. The method of claim 7, wherein determining the variable value comprises:

determining a complement of the threshold that is equal to a sum of (a) a value that equals the first string length multiplied by a function that equals 1 minus the upper limit of the threshold, and (b) a value that equals a log of a ratio of the first string length and the growth rate of the threshold; and

determining the variable value based on a value equal to 1 minus a ratio of the complement and the first string length.

9. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

identifying a first character string having a first string length, and a second character string having a second string length greater than the first string length;

parsing the first character string into one or more first sub-groups of characters;

parsing the second character string into one or more second sub-groups of characters;

comparing each of the one or more first sub-groups of characters against the one or more second sub-groups of characters;

determining a ratio of a number of characters in the one or more first sub-groups of characters that match the one or more second sub-groups of characters and the second string length; and

based on the ratio being greater or equal to a threshold, preparing at least one of the first or second character strings for display, the threshold comprising a variable value based on the first string length.

10. The computer storage medium of claim 9, wherein the operations further comprise, based on the ratio being less than the threshold,

matching the first character string to at least a first sub-group of the one or more second sub-groups of characters of the second character string;

and

based on a ratio of first string length and the second string length that is greater or equal to the threshold, preparing at least one of the first or second character strings for display.

11. The computer storage medium of claim 9, wherein the operations further comprise, based on the ratio being less than the threshold,

matching a first sub-group of the first character string with a first sub-group of the second character string;

matching a last sub-group of the first character string with a last sub-group of the second character string; and

based on a ratio of a combined length of the first and last sub-groups of the first character string and the second string length that is greater or equal to the threshold, preparing at least one of the first or second character strings for display.

12. The computer storage medium of claim 9, wherein the operations further comprise, based on the ratio being less than the threshold,

determining that the characters of the first character string match first characters of at least a subset of the one or more second sub-groups of characters;

determining a number of matched characters being equal to a sum of a number of characters in the subset of the one or more second sub-groups of characters;

determining a number of unmatched characters being equal to the second string length minus the number of matched characters; and

based on a ratio of the number of matched characters and the number of unmatched characters that is greater or equal to the threshold, preparing at least one of the first or second character strings for display.

13. The computer storage medium of claim 9, wherein the operations further comprise, based on the ratio being less than the threshold,

parsing the first character string into one or more first groups of trigrams, each of the first groups of trigrams comprising three characters of the first character string;

parsing the second character string into one or more second groups of trigrams, each of the second groups of trigrams comprising three characters of the second character string;

determining a number of trigram matches between the one or more first groups of trigrams and the one or more second groups of trigrams; and

based on a ratio of the number of trigram matches and a sum of the first and second groups of trigrams that is greater or equal to the threshold, preparing at least one of the first or second character strings for display.

14. The computer storage medium of claim 13, wherein the operations further comprise, based on the ratio of the number of trigram matches and a sum of the first and second groups of trigrams being less than the threshold,

determining an edit distance value between the first character string and the second character string, the edit distance comprising a number of edits to the first character string so that the first character string matches the second character string;

determining a similarity of the first and second character strings based on a ratio of the edit distance of the first string distance; and

based on the similarity being greater or equal to the threshold, preparing at least one of the first or second character strings for display.

15. The computer storage medium of claim 9, wherein the operations further comprise:

determining the variable value based on the first string length, a upper limit of the threshold, a lower limit of the threshold, and a growth rate of the threshold.

16. The computer storage medium of claim 15, wherein determining the variable value comprises:

determining a complement of the threshold that is equal to a sum of (a) a value that equals the first string length multiplied by a function that equals 1 minus the upper limit of the threshold, and (b) a value that equals a log of a ratio of the first string length and the growth rate of the threshold; and

determining the variable value based on a value equal to 1 minus a ratio of the complement and the first string length.

17. A system of one or more computers configured to perform operations comprising:

identifying a first character string having a first string length, and a second character string having a second string length greater than the first string length;

parsing the first character string into one or more first sub-groups of characters;

parsing the second character string into one or more second sub-groups of characters;

comparing each of the one or more first sub-groups of characters against the one or more second sub-groups of characters;

determining a ratio of a number of characters in the one or more first sub-groups of characters that match the one or more second sub-groups of characters and the second string length; and

based on the ratio being greater or equal to a threshold, preparing at least one of the first or second character strings for display, the threshold comprising a variable value based on the first string length.

18. The system of claim 17, wherein the operations further comprise, based on the ratio being less than the threshold,

matching the first character string to at least a first sub-group of the one or more second sub-groups of characters of the second character string;

and

based on a ratio of first string length and the second string length that is greater or equal to the threshold, preparing at least one of the first or second character strings for display.

19. The system of claim 17, wherein the operations further comprise, based on the ratio being less than the threshold,

matching a first sub-group of the first character string with a first sub-group of the second character string;

matching a last sub-group of the first character string with a last sub-group of the second character string; and

based on a ratio of a combined length of the first and last sub-groups of the first character string and the second string length that is greater or equal to the threshold, preparing at least one of the first or second character strings for display.

20. The system of claim 17, wherein the operations further comprise, based on the ratio being less than the threshold,

determining that the characters of the first character string match first characters of at least a subset of the one or more second sub-groups of characters;

determining a number of matched characters being equal to a sum of a number of characters in the subset of the one or more second sub-groups of characters;

determining a number of unmatched characters being equal to the second string length minus the number of matched characters; and

based on a ratio of the number of matched characters and the number of unmatched characters that is greater or equal to the threshold, preparing at least one of the first or second character strings for display.

21. The system of claim 17, wherein the operations further comprise, based on the ratio being less than the threshold,

parsing the first character string into one or more first groups of trigrams, each of the first groups of trigrams comprising three characters of the first character string;

parsing the second character string into one or more second groups of trigrams, each of the second groups of trigrams comprising three characters of the second character string;

determining a number of trigram matches between the one or more first groups of trigrams and the one or more second groups of trigrams; and

based on a ratio of the number of trigram matches and a sum of the first and second groups of trigrams that is greater or equal to the threshold, preparing at least one of the first or second character strings for display.

22. The system of claim 21, wherein the operations further comprise, based on the ratio of the number of trigram matches and a sum of the first and second groups of trigrams being less than the threshold,

determining an edit distance value between the first character string and the second character string, the edit distance comprising a number of edits to the first character string so that the first character string matches the second character string;

determining a similarity of the first and second character strings based on a ratio of the edit distance of the first string distance; and

based on the similarity being greater or equal to the threshold, preparing at least one of the first or second character strings for display.

23. The system of claim 17, wherein the operations further comprise:

determining the variable value based on the first string length, a upper limit of the threshold, a lower limit of the threshold, and a growth rate of the threshold.

24. The system of claim 23, wherein determining the variable value comprises:

determining a complement of the threshold that is equal to a sum of (a) a value that equals the first string length multiplied by a function that equals 1 minus the upper limit of the threshold, and (b) a value that equals a log of a ratio of the first string length and the growth rate of the threshold; and

determining the variable value based on a value equal to 1 minus a ratio of the complement and the first string length.