Hybrid comparison for unicode text strings consisting primarily of ASCII characters

• US 10,089,281 B1
• Filed: 09/28/2017
• Issued: 10/02/2018
• 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
• Primary Examiner(s): Mai, Lam T
• Application Number:
  US15/719,479
• Time in Patent Office: 369 Days
• Field of Search: 341 50- 70
• 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

Comparing text strings with Unicode encoding includes receiving two text strings S₁ and S₂. The process computes, for the first text string S₁, a first weight according to a weight function ƒ that computes an ASCII prefix ƒ_A(S₁), computes a Unicode weight suffix ƒ_U(S₁), and concatenates the weights to form the first weight ƒ(S₁)=ƒ_A(S₁)+ƒ_U(S₁). Computing the ASCII prefix for the first string applies bitwise operations to n-byte contiguous blocks of the first string to determine whether each block contains only ASCII characters, and replaces accented Unicode characters with equivalent unaccented ASCII characters when comparison is designated as accent-insensitive. When there is a first block containing a non-replaceable non-ASCII character, the Unicode weight suffix is computed by performing a character-by-character Unicode weight lookup beginning with the first block. The same process is applied to the second string. The text string are compared by comparing their computed weights.

Claims

1. A method of comparing text strings with 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₁ with Unicode encoding and a second text string S₂ with Unicode encoding;

computing, for the first text string S₁, a first string weight according to a weight function ƒ

that computes an ASCII prefix ƒ

_A(S₁), computes a Unicode weight suffix ƒ

_U(S₁), and concatenates the ASCII prefix to the Unicode weight suffix to form the first string weight ƒ

(S₁)=ƒ

_A(S₁)+ƒ

_U(S₁), wherein;

computing the ASCII prefix for the first text string comprises applying bitwise operations to n-byte contiguous blocks of the first text string to determine whether each block contains only ASCII characters, and replacing accented Unicode characters in the first text string with equivalent unaccented ASCII characters when comparison is designated as accent-insensitive, wherein n is a predefined integer greater than or equal to 4; and

computing the Unicode weight suffix comprises, when there is a first block containing a non-replaceable non-ASCII character, performing a character-by-character Unicode weight lookup beginning with the first block containing a non-replaceable non-ASCII character;

computing, for the second text string S₂, a second string weight 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 the computed ASCII prefix is an empty string.

3. The method of claim 1, wherein the Unicode weight suffix is an empty string.

4. The method of claim 1, wherein comparison is designated as case-insensitive, and computing the ASCII prefix further comprises applying a sequence of bitwise operations to convert upper-case ASCII characters to corresponding lower-case ASCII characters.

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

(S₁))≠

h(ƒ

(S₂)).

6. The method of claim 1, wherein n=8.

7. The method of claim 1, 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 n.

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

9. The method of claim 1, wherein computing the ASCII prefix is performed iteratively, starting with an initial n-byte block of the first text string, sequentially processing n-byte blocks until reaching the end of the first text string or reaching an n-byte block that contains a non-replaceable non-ASCII character.

10. The method of claim 9, wherein, when comparison is not designated as accent-insensitive, each non-ASCII character is designated as a non-replaceable non-ASCII character.

11. The method of claim 9, wherein, when comparison is designated as accent-insensitive, each non-ASCII character is designated as a non-replaceable non-ASCII character when lookup of the respective non-ASCII character in an ASCII-equivalent table has no matching entry.

12. The method of claim 1, wherein computing the Unicode weight suffix comprises:

for each character beginning with the first block containing a non-replaceable non-ASCII character, performing a lookup in a Unicode weight table to identify a respective primary weight, a respective accent weight, and a respective case-weight;

forming a primary Unicode weight w_p as a concatenation of the identified primary weights;

forming an accent Unicode weight w_a as a concatenation of the identified accent weights;

forming a case Unicode weight w_c as a concatenation of the identified case weights; and

forming the Unicode weight suffix as a concatenation w_p+w_a+w_c of the primary Unicode weight, the accent Unicode weight, and the case Unicode weight.

13. The method of claim 12, wherein the comparison designates a specific language, and the Unicode weight table is selected according to the specific language.

14. 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₁ with Unicode encoding and a second text string S₂ with Unicode encoding;

computing, for the first text string S₁, a first string weight according to a weight function ƒ

that computes an ASCII prefix ƒ

_A(S₁), computes a Unicode weight suffix ƒ

_U(S₁), and concatenates the ASCII prefix to the Unicode weight suffix to form the first string weight ƒ

(S₁)=ƒ

_A(S₁)+ƒ

_U(S₁), wherein;

computing the ASCII prefix for the first text string comprises applying bitwise operations to n-byte contiguous blocks of the first text string to determine whether each block contains only ASCII characters, and replacing accented Unicode characters in the first text string with equivalent unaccented ASCII characters when comparison is designated as accent-insensitive, wherein n is a predefined integer greater than or equal to 4; and

computing the Unicode weight suffix comprises, when there is a first block containing a non-replaceable non-ASCII character, performing a character-by-character Unicode weight lookup beginning with the first block containing a non-replaceable non-ASCII character;

computing, for the second text string S₂, a second string weight 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.

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

(S₁))≠

h(ƒ

(S₂)).

16. The computing device of claim 14, wherein computing the ASCII prefix is performed iteratively, starting with an initial n-byte block of the first text string, sequentially processing n-byte blocks until reaching the end of the first text string or reaching an n-byte block that contains a non-replaceable non-ASCII character.

17. The computing device of claim 16, wherein, when comparison is designated as accent-insensitive, each non-ASCII character is designated as a non-replaceable non-ASCII character when lookup of the respective non-ASCII character in an ASCII-equivalent table has no matching entry.

18. The computing device of claim 14, wherein computing the Unicode weight suffix comprises:

for each character beginning with the first block containing a non-replaceable non-ASCII character, performing a lookup in a Unicode weight table to identify a respective primary weight, a respective accent weight, and a respective case-weight;

forming a primary Unicode weight w_p as a concatenation of the identified primary weights;

forming an accent Unicode weight w_a as a concatenation of the identified accent weights;

forming a case Unicode weight w_c as a concatenation of the identified case weights; and

forming the Unicode weight suffix as a concatenation w_p+w_a+w_c of the primary Unicode weight, the accent Unicode weight, and the case Unicode weight.

19. The computing device of claim 18, wherein the comparison designates a specific language, and the Unicode weight table is selected according to the specific language.

20. 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₁ with Unicode encoding and a second text string S₂ with Unicode encoding;

computing, for the first text string S₁, a first string weight according to a weight function ƒ

that computes an ASCII prefix ƒ

_A(S₁), computes a Unicode weight suffix ƒ

_U(S₁), and concatenates the ASCII prefix to the Unicode weight suffix to form the first string weight ƒ

(S₁)=ƒ

_A(S₁)+ƒ

_U(S₁), wherein;

computing the ASCII prefix for the first text string comprises applying bitwise operations to n-byte contiguous blocks of the first text string to determine whether each block contains only ASCII characters, and replacing accented Unicode characters in the first text string with equivalent unaccented ASCII characters when comparison is designated as accent-insensitive, wherein n is a predefined integer greater than or equal to 4; and

computing the Unicode weight suffix comprises, when there is a first block containing a non-replaceable non-ASCII character, performing a character-by-character Unicode weight lookup beginning with the first block containing a non-replaceable non-ASCII character;

computing, for the second text string S₂, a second string weight 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.