Hybrid comparison for unicode text strings consisting primarily of ASCII characters

Patent metadata

Field	Value
Publication number	US-10540425-B2
Application number	US-201916445139-A
Country	US
Kind code	B2
Filing date	Jun 18, 2019
Priority date	Nov 6, 2016
Publication date	Jan 21, 2020
Grant date	Jan 21, 2020

Abstract

A method compares text strings having Unicode encoding. The method receives a first string S=s1 s2 . . . sn and a second string T=t1 t2 . . . tm, where s1, s2, . . . , sn and t1, t2, . . . , tm 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(s1) g(s2) . . . g(sn), where g(si)=si when si is an ASCII character and g(si)=si′ when si is an accented ASCII character that is replaceable by the corresponding ASCII character si′. When S includes one or more non-replaceable non-ASCII characters, the first string weight concatenates an ASCII weight prefix ƒA (S) and a Unicode weight suffix ƒU(S). The method also computes a second string weight for the second text string T. Equality of the strings is tested using the string weights.

First claim

What is claimed is:

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 1 s 2 . . . s n having Unicode encoding and a second text string T=t 1 t 2 . . . t m having Unicode encoding, wherein n and m are positive integers, and s 1 , s 2 , . . . , s n and t 1 , t 2 , . . . , 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;
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 1 ) g(s 2 ) . . . 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 ′; and
when S includes one or more non-replaceable non-ASCII characters, the first string weight ƒ(S) is a concatenation of an ASCII weight prefix ƒ A (S) and a Unicode weight suffix ƒ U (S);

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 the computed ASCII prefix for the first text string S and/or for the second text string T is an empty string.

4. 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.

5. The method of claim 4 , 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.

6. The method of claim 4 , wherein r=8.

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

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

9. The method of claim 4 , wherein computing the first string weight is performed iteratively, starting with an initial r-byte block of the first text string, sequentially processing r-byte blocks until reaching the end of the first text string or reaching an r-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 the Unicode weight suffix ƒ U (S) is computed beginning with a first block containing a non-replaceable non-ASCII character, by:
performing a character-by-character 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=s 1 s 2 . . . s n having Unicode encoding and a second text string T=t 1 t 2 . . . t m having Unicode encoding, wherein n and m are positive integers, and s 1 , s 2 , . . . , s n and t 1 , t 2 , . . . , 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;
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 1 ) g(s 2 ) . . . 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 ′; and
when S includes one or more non-replaceable non-ASCII characters, the first string weight ƒ(S) is a concatenation of an ASCII weight prefix ƒ A (S) and a Unicode weight suffix ƒ U (S);

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.

15. The computing device of claim 14 , 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)).

16. The computing device of claim 14 , 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.

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

18. 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.

19. The computing device of claim 14 , wherein the Unicode weight suffix ƒ U (S) is computed beginning with a first block containing a non-repla

Assignees

• Tableau Software Inc

Inventors

• Neumann Thomas
• Leis Viktor
• Kemper Alfons

Classifications

• G06F16/24542

  Plan optimisation · CPC title

• G06F16/24537

  of operators · CPC title

• G06F16/24535

  of sub-queries or views · CPC title

• G06F40/166

  Editing, e.g. inserting or deleting · CPC title

• H03M7/14 Primary

  Conversion to or from non-weighted codes · CPC title