How do you set strings to uppercase / lowercase in

Question

This is mostly a theoretical question I'm just very curious about. (I'm not trying to do this by coding it myself or anything, I'm not reinventing wheels.)

My question is how the uppercase/lowercase table of equivalence works for Unicode.

For example, if I had to do this in ASCII, I'd take a character, and if it falls withing the [a-z] range, I'd sum the difference between A and a.

If it doesn't fall on that range, I'd have a small equivalence table for the 10 or so accented characters plus ñ. (Or, I could just have a full equivalence array with 256 entries, most of which would be the same as the input)

However, I'm guessing that there's a better way of specifying the equivalences in Unicode, given that there are hundreds of thousands of characters, and that theoretically, a new language or set of characters can be added (and I'm expecting that you wouldn't need to patch windows when that happens).

Does Windows have a huge hard-coded equivalence table for each character? Or how is this implemented?

A related question is how SQL Server implements Unicode-based accent-insensitive and case-insensitive queries. Does it have an internal table that tells it that é ë è E É È and Ë are all equivalent to "e"?

That doesn't sound very fast when it comes to comparing strings.

How does it access Indexes quickly? Does it already index values converted to their "base" characters, corresponding to that field's collation?

Does anyone know the internals for these things?

Thank you!

Answer 1

The correct answer is a little more complicated, depending on what you are trying to do.

When comparing character strings, for sorting or searching applications, the correct algorithm to use is specified in UTS #10: "Unicode Collation Algorithm". Case-insensitivity is part of the mix, but there are different ways to represent a many characters, and applications often need to treat the various representations as equivalent.

The sorting rules are locale-dependent. This is mainly an issue when you are sorting results for display to a user. Ignoring the rules can frustrate users and even result in security vulnerabilities.

If you are just trying to capitalize words for display purposes, the rules there can be tricky too; there are one-to-many conversions and other issues. Depending on the locale, the same letter may capitalize differently. The letter's position in a word can make a difference. There's also a a distinct notion of "title case", where you just want to capitalize the first letter of each word. Sometimes the title-case of a character is not the same as its upper-case.

Answer 2

There is a mapping file that contains all the case mappings that have a 1:1 mapping ratio. Usually operating systems/frameworks/libraries support a specific version of Unicode, and since this case mappings file is versioned, you would get the mappings for whichever version of Unicode your particular OS/framework/library/whatever happened to support.

For more information on Unicode case mappings, see: http://www.unicode.org/faq/casemap_charprop.html

Answer 3

I'm going to address the MS SQL Server part of this question, but the "correct" answer actually depends on the language(s) supported and application.

When you create a table in SQL Server, each text field has either an implicitly or explicitly specified collation. This affects both sort order and comparison behavior. The default, for most English (US) locales, is Latin1_General_CI_AS, or Latin 1, Case-insensitive, Accent-Sensitive. That means that, for example, a=A, but a!=Ä and a!=ä. You can also use accent-insensitive (Latin1_General_CI_AI) which treats all the diacritic variations of "A" as equal.

Some locales support other categories of comparison; for example, French orders words containing diacritics somewhat differently than German does. Turkish considers a dotless i and dotted i semantically different, so I and i don't match even with case-insensitive comparisons if you use Turkish, case-insensitive, accent-sensitive collation.

You can change the collation per database, per table, per field, and, with some cost, even per-query. My understanding is that indices normalize according to the specified collation order, which means that basically the index keeps a flattened version of the original string. For example, with case-insensitive collations, Apple and apple are stored as apple. Queries are flattened with the same collation before the search.

In Japanese, there's another category of normalization, where fullwidth and halfwidth characters like ア=ｱ, and in some cases, two halfwidth characters are flattened to a single, semantically equivalent character (バ=ﾊﾞ). Finally, for some languages, there's another ball of wax with composite characters, where isolated diacritic characters can be composed with other characters (e.g. the umlaut in ä is one character, composed with the simple form a). Vietnamese, Thai and a few other languages have variations of this category. If there's a canonical form, Unicode normalization allows the composed and decomposed forms to be treated as equivalent. Unicode normalization is typically applied before any comparisons are made.

To summarize, for a case-insensitive comparison, you do something much like you would when comparing ASCII-range strings: flatten the left and right side of the comparison "to lower case" (for example), then compare the array as a binary array. The difference is that you need to 1) normalize the strings to the same unicode form (kC or kD) 2) normalize the strings to the same case according to the rules of that locale 3) normalize the accents according to the accent-sensitivity rules 4) compare according to a binary comparison 4) if applicable, such as in the case of sorting, compare using additional secondary and ternary sorting rules, which include things analogous to things like "Mc" sorts before "M" in some languages.

And yes, Windows stores tables for all of these rules. You don't get all of them by default in every installation, unless you add support for them with the East Asian Language Support and Complex Scripts support from control panel.

Answer 4

Most writing systems do not have separate uppercase and lowercase letters. According to Wikipedia, exceptions include "Roman, Greek, Cyrillic and Armenian alphabets".

So there aren't that many letters to worry about. This page shows that large ranges of characters follow a simple scheme of adding 1 to an uppercase character to get the lowercase equivalent (though of course there are some exceptions).