Hybrid Comparison for Unicode Text Strings Consisting Primarily of ASCII Characters

• US 20200134254A1
• Filed: 12/24/2019
• Published: 04/30/2020
• Est. Priority Date: 11/06/2016
• Status: Active Grant

• Current Assignee: Tableau Software Incorporated (Salesforce.com, Inc.)
• Original Assignee: Tableau Software Incorporated (Salesforce.com, Inc.)
• Inventors: Neumann, Thomas, Leis, Viktor, Kemper, Alfons
• Granted Patent: US 10,789,416 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 40/126 Character encoding
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: H03M 7/02 Conversion to or from weighted codes, i.e. the weight given to a digit depending on the position of the digit within the block or code word
• CPC Class Codes: H03M 7/14 Conversion to or from non-weighted codes
• CPC Class Codes: H03M 7/705 Unicode

Abstract

A method compares text strings having Unicode encoding. The method receives a first string S=s₁s₂ . . . s_n and a second string T=t₁t₂ . . . t_m, where s₁, s₂, . . . , s_n and t₁, t₂, . . . , t_m are Unicode characters. The method computes a first string weight for the first string S according to a weight function ƒ. When S consists of ASCII characters, ƒ(S)=S. When S consists of ASCII characters and some accented ASCII characters that are replaceable by ASCII characters, ƒ(S)=g(s₁)g(s₂) . . . g(s_n), where g(s_i)=s_i when s_i is an ASCII character and g(s_i)=s′_i when s_i is an accented ASCII character that is replaceable by the corresponding ASCII character s′_i. The method also computes a second string weight for the second text string T. Equality of the strings is tested using the string weights.

Claims

1. A method of comparing text strings having Unicode encoding, comprising:

at a computer having one or more processors, and memory storing one or more programs configured for execution by the one or more processors;

receiving a first text string S=s₁s₂ . . . s_n, having Unicode encoding and a second text string T=t₁t₂ . . . t_m having Unicode encoding, wherein n and m are positive integers, and s₁, s₂, . . . , s_n and t₁, t₂, . . . , t_m are Unicode characters;

computing, for the first text string S, a first string weight ƒ

(S) according to a weight function ƒ

, computed according to;

when it is determined that S consists entirely of ASCII characters, ƒ

(S)=S; and

when it is determined that S consists of ASCII characters and one or more accented ASCII characters that are replaceable by corresponding ASCII characters, ƒ

(S)=g(s₁)g(s₂) . . . g(s_n), wherein g(s_i)=s_i when s_i is an ASCII character and g(s_i)=s′

_i when s_i is an accented ASCII character that is replaceable by the corresponding ASCII character s_i;

computing, a second string weight ƒ

(T), for the second text string T, according to the weight function ƒ

; and

determining whether the first text string and the second text string are equal by comparing the first string weight to the second string weight.

2. The method of claim 1, wherein comparing the first text string S to the second text string T uses a hash function h, and the first text string S is determined to be not equal to the second text string T when h(ƒ

(S))≠

h(ƒ

(T)).

3. The method of claim 1, wherein computing the first string weight comprises:

subdividing the first text string S into one or more r-byte contiguous blocks, wherein r is a predefined integer greater than or equal to 4; and

processing the r-byte blocks sequentially beginning on the left, including applying a first bitwise operator to each r-byte block to determine whether the respective block consists of ASCII characters.

4. The method of claim 3, wherein comparison is designated as case-insensitive, and computing the first string weight further comprises applying a sequence of bitwise operators to convert upper-case ASCII characters to corresponding lower-case ASCII characters.

5. The method of claim 3, wherein r=8.

6. The method of claim 3, further comprising padding the first text string on the right so that a total length of the first text string is an integer multiple of r.

7. The method of claim 6, wherein padding the first text string comprises adding ASCII null characters.

8. A computing device, comprising:

one or more processors;

memory; and

one or more programs stored in the memory and configured for execution by the one or more processors, the one or more programs comprising instructions for;

receiving a first text string S=s₁s₂ . . . s_n having Unicode encoding and a second text string T=t₁t₂ . . . t_m having Unicode encoding, wherein n and m are positive integers, and s₁, s₂, . . . , s_n and t₁, t₂, t_m are Unicode characters;

computing, for the first text string S, a first string weight ƒ

(S) according to a weight function ƒ

, computed according to;

when it is determined that S consists entirely of ASCII characters, ƒ

(S)=S; and

when it is determined that S consists of ASCII characters and one or more accented ASCII characters that are replaceable by corresponding ASCII characters, ƒ

(S)=g(s₁)g(s₂) . . . g(s_n), wherein g(s_i)=s_i when s_i is an ASCII character and g(s_i)=s′

_i when s_i is an accented ASCII character that is replaceable by the corresponding ASCII character s′

_i;

computing, a second string weight ƒ

(T), for the second text string T, according to the weight function ƒ

; and

determining whether the first text string and the second text string are equal by comparing the first string weight to the second string weight.

9. The computing device of claim 8, wherein comparing the first text string S to the second text string T uses a hash function h, and the first text string S is determined to be not equal to the second text string T when h(ƒ

(S))≠

h(ƒ

(T)).

10. The computing device of claim 8, wherein computing the first string weight comprises:

subdividing the first text string S into one or more r-byte contiguous blocks, wherein r is a predefined integer greater than or equal to 4; and

processing the r-byte blocks sequentially beginning on the left, including applying a first bitwise operator to each r-byte block to determine whether the respective block consists of ASCII characters.

11. The computing device of claim 10, wherein comparison is designated as case-insensitive, and computing the first string weight further comprises applying a sequence of bitwise operators to convert upper-case ASCII characters to corresponding lower-case ASCII characters.

12. The computing device of claim 10, wherein r=8.

13. The computing device of claim 10, further comprising padding the first text string on the right so that a total length of the first text string is an integer multiple of r.

14. The computing device of claim 13, wherein padding the first text string comprises adding ASCII null characters.

15. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computing device having one or more processors and memory, the one or more programs comprising instructions for:

receiving a first text string S=s₁s₂ . . . s_n having Unicode encoding and a second text string T=t₁t₂ . . . t_m having Unicode encoding, wherein n and m are positive integers, and s₁, s₂, . . . , s_n and t₁, t₂, . . . , t_m are Unicode characters;

computing, for the first text string S, a first string weight ƒ

(S) according to a weight function ƒ

, computed according to;

when it is determined that S consists entirely of ASCII characters, ƒ

(S)=S; and

when it is determined that S consists of ASCII characters and one or more accented ASCII characters that are replaceable by corresponding ASCII characters, ƒ

(S)=g(s₁)g(s₂) . . . g(s_n), wherein g(s_i)=s_i when s_i is an ASCII character and g(s_i)=s′

_i when s_i is an accented ASCII character that is replaceable by the corresponding ASCII character s′

_i;

computing, a second string weight ƒ

(T), for the second text string T, according to the weight function ƒ

; and

determining whether the first text string and the second text string are equal by comparing the first string weight to the second string weight.

16. The computer readable storage medium of claim 15, wherein comparing the first text string S to the second text string T uses a hash function h, and the first text string S is determined to be not equal to the second text string T when h(ƒ

(S))≠

h(ƒ

(T)).

17. The computer readable storage medium of claim 15, wherein computing the first string weight comprises:

subdividing the first text string S into one or more r-byte contiguous blocks, wherein r is a predefined integer greater than or equal to 4; and

processing the r-byte blocks sequentially beginning on the left, including applying a first bitwise operator to each r-byte block to determine whether the respective block consists of ASCII characters.

18. The computer readable storage medium of claim 17, wherein comparison is designated as case-insensitive, and computing the first string weight further comprises applying a sequence of bitwise operators to convert upper-case ASCII characters to corresponding lower-case ASCII characters.

19. The computer readable storage medium of claim 17, wherein r=8.

20. The computer readable storage medium of claim 17, further comprising padding the first text string on the right so that a total length of the first text string is an integer multiple of r.