Compressed unicode normalization with inversion

• US 20040006569A1
• Filed: 06/28/2002
• Published: 01/08/2004
• Est. Priority Date: 06/28/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: OʼNeil, Patrick Eugene, OʼNeil, Elizabeth Jean, Fang, Jun, Carlin, Peter
• Granted Patent: US 7,155,442 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 40/12 Use of codes for handling textual entities
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Any string in any character set with an arbitrary-leveled weight-based comparison system is transformed into a bitstring in such a way that two transformed strings can be compared byte-by-byte. The resulting bit string has the minimum possible maximum length. The transformed bit strings can be inverted—meaning the original string can be recovered from the transformed string.

Claims

1. A method for use in a computer environment, comprising:

receiving a string of characters; and

performing a normalizing transformation on the string of characters to generate a bitstring.

2. The method of claim 1, wherein the length of the generated bitstring is substantially equal to a minimum possible maximum encoded length for the string of characters.

3. The method of claim 1, wherein performing the normalizing transformation comprises receiving a set of weights for each character in the string of characters and generating the bitstring based on the set of weights.

4. The method of claim 3, wherein receiving the set of weights for each character in the string of characters comprises retrieving the set of weights from a weight table.

5. The method of claim 3, wherein the set of weights comprises at least one of a weight associated with a character category and a weight associated with a diacritical mark.

6. The method of claim 3, wherein the set of weights comprises a set of weight strings, each weight string being represented by an associated (0-1)-bit sequence.

7. The method of claim 1, further comprising compressing the generated bitstring to generate a prefix-coded bitstring.

8. The method of claim 7, wherein compressing comprises applying a minimax technique to the generated bitstring.

9. The method of claim 1, further comprising inverting the generated bitstring to recover the string of characters.

10. The method of claim 9, wherein inverting the generated bitstring comprises retrieving an inversion weight from the generated bitstring and recovering the string of characters based on the inversion weight.

17. A computer readable storage medium on which is stored a weight table for use in the method of claim 4.

18. The weight table as recited in claim 17, comprising a plurality of characters, each character having an associated code, primary weight, and secondary weight.

19. The weight table as recited in claim 18, wherein the primary weight comprises an associated primary weight string, and the secondary weight comprises an associated secondary weight string.

11. A method of comparing a first string of characters and a second string of characters, comprising:

performing a normalizing transformation on each string of characters to generate a first bitstring having a first primary weight and a first secondary weight, and a second bitstring having a second primary weight and a second secondary weight;

comparing the first primary weight and the second primary weight;

if the first primary weight is greater than the second primary weight then determining that the first bitstring is greater than the second bitstring;

if the first primary weight is less than the second primary weight then determining that the first bitstring is less than the second bitstring; and

if the first primary weight is equal to the second primary weight then performing a comparison based on the first secondary weight and the second secondary weight.

12. The method of claim 11, wherein performing a comparison based on the first secondary weight and the second secondary weight comprises:

comparing the first secondary weight and the second secondary weight;

if the first secondary weight is greater than the second secondary weight then determining that the first bitstring is greater than the second bitstring;

if the first secondary weight is less than the second secondary weight then determining that the first bitstring is less than the second bitstring; and

if the first secondary weight is equal to the second secondary weight then performing another comparison based on an additional weight associated with the first bitstring and an additional weight associated with the second bitstring.

13. The method of claim 12, wherein the additional weight associated with the first bitstring and the additional weight associated with the second bitstring are each a tertiary weight associated with a case.

14. The method of claim 12, wherein the first primary weight and the second primary weight are each associated with a character category.

15. The method of claim 12, wherein the first secondary weight and the second secondary weight are each associated with a diacritical mark.

16. The method of claim 12, wherein each of the primary weights and each of the secondary weights comprises an associated weight string, each weight string being represented by an associated (0-1)-bit sequence.

20. A string processing system, comprising:

a first data source using a string of characters;

a weight table comprising a plurality of characters, including the characters in the string of characters, each character having an associated code, primary weight, and secondary weight; and

a processor to perform a normalizing transformation on the string of characters to generate a bitstring.

21. The system of claim 20, wherein the primary weight comprises an associated primary weight string, and the secondary weight comprises an associated secondary weight string.

22. The system of claim 21, wherein each weight string is represented by an associated (0-1)-bit sequence.

23. The system of claim 20, wherein the primary weight comprises a weight associated with a character category and the secondary weight comprises a weight associated with a diacritical mark.

24. The system of claim 20, further comprising a compressor to compress the generated bitstring into a prefix-coded bitstring.

25. The system of claim 20, further comprising an inverter to invert the generated bitstring to recover the string of characters.