* String collation
** Summary
We are going to implement Windows-like collation, apart from ICU (that
implements UCA, Unicode Collation Algorithm).
** Tasks
* create collation element table(s)
- infer how Windows collation element table is composed
: mostly analyzed.
- write table generator source(s)
: mostly implemented. Need to fix nearly 400 mappings.
They are mainly 1) IPA extensions (U+250-U+300),
2) Latin extensions (U+1E00-U+1F00), 3) Letterlike
symbols (U+2100-U+2140), 4) some Cyrillic letters
(U+460-U+500), and 5) some Hangul characters.
- culture-specific sortkey data
: They are defined in mono-tailoring-source.txt.
All single sortkey remapping in all cultures are filled.
Contractions are not fully checked yet (should be filled
from UCA tailorings via create-tailorings.exe).
** How to implement CompareInfo members
GetSortKey() : done
Compute sort key for every character elements into byte[].
Compare() : done
Find first difference and compare it.
"Larger/smaller" matters (beyond "different").
IsPrefix()
It calls CompareInternal() which also answers if the target
is fully consumed, so it just returns true if it says that
the target is fully consumed.
IsSuffix()
It tries CompareInternal() to compare source and target at
the end, where source varies from minimum tail to the
original args.
IndexOf(), LastIndexOf()
For character search, it finds the matching character element
to the end (or start) of the string to find.
For string search, it invokes one of private IndexOf() (or
LastIndexOf()) overload passing the first character element
of the target, and if found, tests if the sequence is a valid
start point, using IsPrefix() (or IsSuffix()).
*** Optimizations
For Compare() and IsPrefix(), it uses forward iteration, which moves
forward and don't stop until either it finds next "primary" character
or it reached the end of the string, checking with IsSafe(char).
For IndexOf(char) and LastIndexOf(char), there is no special
optimization (since the codepoints usually do not match, while they
often matches as a natural collation), but it omits extraneous sortkey
value computation.
IsSuffix() reuses Compare() and returns false if it does not consume
the target string more than 3 times. 3 is kind of magic number that
represents the longest expansion.
IndexOf(string) is implemented as a combination of IndexOf(char) and
IsPrefix().
LastIndexOf(string) is implemented as a combination of
LastIndexOf(char) and IsPrefix().
Porting them to C code is an alternative possible approach, but from
Compare() optimization experience, it is quick enough.
** How to support CompareOptions
There are two kind of "ignorance" : strippers' ignorance and
normalizers' ignorance.
The strippers will "filter characters out" and there will be no
corresponding character elements in SortKey binaries.
Normalizers, on the other hand, will result in certain characters
that is still in effect between irrelevant character and itself.
For example, with IgnoreKanaType Hiragana "A" and Katakana "A" are
not distinguished, but Hiragana "A" and Hiragana "I" are.
Actually, even without any IgnoreXXX flags (i.e. "None"), there are
many characters that are ignored ("completely ignorable").
Except for LCID 101/1125(div), '\ufdf2' is completely ignorable.
This rule even applies to CompareOptions.None.
*** Normalizers
IgnoreCase
Maybe culture-dependent TextInfo.ToLower() could be used.
Unlike ICU (specialCaseToLower()), even with tr-TR(LCID 31)
and IgnoreCase, I\u0307 is not regarded as equal to i.
IgnoreKanaType
ToKanaTypeInsensitive(). Note that this does not cover the
whole "level 4" differences described later.
IgnoreWidth
ToWidthInsensitive(), which is likely to be culture
independent. See also "Notes".
IgnoreNonSpace (see also Strippers; this flag works in both sides)
For some cultures this logic is still incomplete. All culture-
dependent collators must handle valid "replacement" of "one or
more characters" which might be related to specific
CompareOptions.
For example, there is a Japanese text sorting rule that
however applies to InvariantCulture. Concretely to say,
"\u3042\u30FC" is equivalent to "\u3042\u3042" only when
IgnoreNonSpace is specified.
I'll take those items from CLDR (those items which has
), case by case though.
*** Strippers
I already wrote all the required strippers which should be MS
compatible (at least with .NET 1.1 invariant culture).
IgnoreNonSpace
IsIgnorableNonSpacing().
Some Diacritic characters are covered by this flag.
There are some culture *dependent* characters:
LCID 90/1114(syr) : 64b, 652, 670
IgnoreSymbols
IsIgnorableSymbol().
UnicodeCategory does not work here.
There are some culture *dependent* characters:
LCID 17/1041(ja) : 2015
LCID 90/1114(syr) : 64b, 652
*** StringSort
See "sort order categories" section.
** ICU and UCA
First to note: we won't use collation element table from unicode.org.
There are many differences between ICU/UCA and Windows despite they
look so similar; having collation keys in different levels, culture
dependent composition, etc. In the history, Windows collation is
designed before UCA was specified, so basically Windows is obsolete
in this area.
- Logic: Unlike UCA it has no concept of "blocked" combining marks,
and combining marks are never considered as an independent character
(thus combining in Windows is buggy).
- Data: Windows is based on old Unicode standard (even older than 1.1).
It ignores minor cultures. Character property values differ as well
as those from the default Unicode collation element table (DUCET).
In a few cultures Windows collation is close to the native language
(e.g. Tamil, while it does not conform to TAM).
IgnoreWidth/IgnoreSymbols is processed after Kana voice mark
decomposition (something like NFD, but not equivalent. Example: \u304C
is completely equivalent to \u304B\u309B, which is not part of NFKD).
This means, if there is a combined Kana characters, it will be
first decomposed and then compared. It scarcely matters since
there are special weight data for Japanese.
*** Microsoft design problem
Microsoft implementation seems to have a serious problem that many,
many characters that are used in for each specific culture, such as
Myanmar, Mongolian, Cherokee, Etiopic, Tagalog, Khmer, are regarded as
"completely ignorable".
I tagged many LAMESPEC items in the implementation (both in collator
and table generator).
** MS collation design inference
*** Levels
Each character has several "weights". It is a common concept between
Windows and UCA.
There are 5 levels:
- level 1: primary difference
The first byte of level 1 means the category of the character.
- level 2: diacritic difference, including Japanese voice mark countup
- level 3: case/width sensitivity, and Hangul properties
- level 4: kana weight (all of them have primary category 22, at least
in InvariantCulture)
- level 5: shift weight (apostrophe, hyphens etc.)
Note that these levels does not digitally match IgnoreXXX flags. Thus
it is not OK that we omit some levels of sortkey values in reflection
to CompareOptions.
String comparison is done from level 1 to 5. The comparison won't
stop until either it found the primary difference, or it reached to
the end (thus upper level differences are returned).
For example, "e" is smaller than "E", but "eB" is bigger than "EA".
If the collator just returned case difference at first 'e' and 'E',
"eB" is still smaller than "EA".
**** level 5: shift weight by StringSort
There are some characters that are treated specially. Namely they are
apostrophe and hyphens. The sortkeys for them is put after level 4
(thus here I write them as "level 5"). It has different sort key
format. See immediate below. There is no level 5 characters when
StringSort is specified.
*** sort key format
00 means the end of sort key.
01 means the end of the level.
02-FF means the value.
Actually '2' could be cut when all the following values are
also '2' (i.e. the sort key binary won't contain extraneous '2').
Every level has different key layout.
**** level 2
It looks like all level 2 keys are just accumulated, however without
considering overflow. It sometimes makes sense (e.g. diaeresis and
acute) but it causes many conflicts (e.g. "A\u0308\u0301" and "\u1EA6"
are incorrectly regarded as equal).
Anyways since Japanese voice mark has level 2 value as 1 it just
looked like the sum of voice marks.
**** level 3
The actual values are + 2 (e.g. for Hangul Normal Jamo, the value is 4)
For Korean letters:
- 2: Jongseong (11A8-11F9)
- 4: Half width? (FFA0-FFDC) and Compatibility Jamo? (3165-318E)
- 5: Compatibility Jamo (3130-3164)?
TODO: Learn about Korean characters.
For numbers:
- 4 circled inverse (2776-277F)
- 8 circled sans serif (2780-2789)
- C circled inverse && sans serif (278A-2793)
- 47 roman (2160-2182)
For Arabic letters:
- 2 Isolated form in presentation form B in FE80-FE8D
- 4 Alef/Bet/Gimel/Dalet (2135-2138)
- 8 Final form in presentation form B in FE82-FEF2
- 18 Medial form in presentation form B in FE8C-FEF4
Grep "ISOLATED", "FINAL" or "MEDIAL" on UnicodeData.txt
(and filter by codepoints).
or alternatively, see DerivedDecompositionType.txt.
- 22 6A9 (TODO: what is it?)
- 28 6AA (TODO: what is it?)
For other letters:
- 1 Fullwidth. UnicodeData.txt has .
- 2 Subscript. UnicodeData.txt has .
- 8 Small capital, 03C2 (TODO: why?),
2104, 212B(flag=1A) (TODO: why?)
grep "SMALL CAPITAL" against UnicodeData.txt.
- C only FE42. TODO: what is this?
- E Superscripts. UnicodeData.txt has .
- 10 Uppercase.
DerivedCoreProperties.txt has Uppercase property.
Note that simple 02 (value is 00) could be omitted.
Summary: at least 7 bits are required as to represent a table -
smallCapital, uppercase, normalization forms (2 bits:full/sub/super),
arabic forms (2 bits:isolated/medial/final)
**** level 4
Those sortkey data is collected only for Japanese (category 22)
characters.
There are 3 sections each of them ends with FF. Each of them
represents the values for character by character:
- small letter type (kogaki moji); C4 (small) or E4 (normal)
- category middle section:
two subsections separated by 0x02
- char type;
3 (normal)
or 4 (voice mark - \u309D,\u309E,\u30FD,\u30FE, \uFF70)
or 5 (dash mark - \u30FC)
- kana type; C4 (katakana) or E4 (hiragana)
- width; 2 (normal) or C5 (full) or C4 (half)
LAMESPEC: those characters of value '4' of middle section differs
in level 2 wrt voice marks, but does not differetiate kana types
(bug). It is ignored when IgnoreNonSpace applies.
**** level 5
UPDATED: I noticed offsetL does not exist, so removed it from here.
[offsetM + 0x80]? [const 3 + (offsetS + 1) * 4] [category] [level1]
where "offsetM" and "offsetS" represents the offset in the input
string. "offsetM" is always larger than 0x80.
LAMESPEC: This design results in a buggy overflow.
byte [] data = new CultureInfo ("").CompareInfo.GetSortKey (s).KeyData;
int idx = 0;
for (int i = 0; i < 4; i++, idx++)
for (; data [idx] != 1; idx++)
;
for (; idx < data.Length; idx++)
Console.Write ("{0:X02} ", data [idx]);
Console.WriteLine ();
inputs (s) and results:
80 07 06 82 80 2F 06 82 00 // '-' + new string ('A', 10) + '-'
80 07 06 82 81 97 06 82 00 // (100)
80 07 06 82 8F A7 06 82 00 // (1000)
80 07 06 82 9C 47 06 82 00 // (10000)
80 07 06 82 9A 87 06 82 00 // (100000)
80 07 06 82 89 07 06 82 00 // (1000000)
The actual offset is 63 * offsetM + offsetS
(const '3' may actually vary but no idea.
At least 00, 01 and 02 are not acceptable since they are reserved.
02 is not reserved by definition above, but the key-size optimizer
uses it as a special mark, as mentioned above.)
*** sort key table
Here is the simple sortkey dumper:
public static void Main (string [] args)
{
CultureInfo culture = args.Length > 0 ?
new CultureInfo (args [0]) :
CultureInfo.InvariantCulture;
CompareInfo ci = culture.CompareInfo;
for (int i = 0; i < char.MaxValue; i++) {
string s = new string ((char) i, 1);
if (ci.Compare (s, "") == 0)
continue; // ignored
byte [] data = ci.GetSortKey (s).KeyData;
foreach (byte b in data) {
Console.Write ("{0:X02}", b);
Console.Write (' ');
}
Console.WriteLine (" : {0:X}, {1} {2}",
i,
Char.GetUnicodeCategory ((char) i),
data [2] != 1 ? '!' : ' ');
}
}
*** multiple character mappings
Some sequence of characters are considered as a "composite" that is
to be composed either as another character or another sequence of
characters. Those "composite" might not have corresponding equivalent
character in sortkey.
Similarly, some single characters are expanded to a sequence of
characters.
**** diacritic characters
Except for those shift-weight characters, there are only
diacritical (or other kinds of nonspacing) characters that don't
have primary weights.
Diacritics are not regarded as a base character when placed after
(maybe some kind of) letters.
The behavior is diacritic character dependent. For example, Japanese
combination of a Kana character and a voice mark is compulsory (the
resulting sort key is regarded as identical to the corresponding
single character. Try \u304B\u309B with \u304C. It is invariant).
In French cultures, diacritic orderings are checked from right to left.
**** Composite character processing
There are some sequences of characters that are treated as another
character or another sequence of characters.
By default, there is no composite form.
http://www.microsoft.com/globaldev/dis_v1/disv1.asp?DID=dis33d&File=S24C2.asp
(Note that composite is different from expansion.)
Note that composite characters is likely to not have equivalent
codepoint.
**** Expanded character processing
Some characters are expanded to two or more characters:
C6 (AE), E6 (ae), 1F1-1F3 (dz), 1C4-1C6 (Dz), FB00-FB06 (ff, fi),
132-133 (IJ), 1C7-1C9 (LJ), 1CA-1CC (NJ), 152-153 (OE),
DF (ss), FB06 (st), FB05 (\u017Ft), FE, DE, 5F0-5F2,
1113-115F (hangul)
(CJK extension is not really expanded)
They don't match with any of Unicode normalization.
Some alphabetic cultures have different mappings, but mostly small
(at least da-DK, lt-LT, fr-FR, es-ES have tiny differences).
Invariant culture also puts Czech unique character \u0161 between s
and t, unlike described here:
http://www.microsoft.com/globaldev/dis_v1/disv1.asp?DID=dis33d&File=S24C0.asp
*** default sort key table
**** StringSort
When CompareOptions.StringSort is specified, then it modifies
characters in category 2 from "1 1 1 1 80 07 06 xx" to
"06 xx yy zz" and some characters become case sensitive.
For details, "level 5" description above.
To handle them simply, they are laid out as "category 0x01" (which
never happens in the actual sortkeys) for those shift-weight ones
in the table.
There seems no further differences between StringSort and None.
**** level 2 details
Known value maps:
-0A: Korean parenthesized numbers (3200-321C)
-0C: Korean circled numbers (3260-327B)
-03: Japanese voice mark
-08: 627-648 (basic Abjad letters)
-09: madda (622)
-05: waw with hamza (624)
-07: yeh with hamza (626. ignore Presentation Form A area)
-0A: alef with hamza above (623)
-0A: alef with hamza below (625)
Characters in non "0E" category are out of scope.
They can be grepped in UnicodeData.txt.
-0E: acute
-0F: grave
-10: dot above
-11: middle dot
-12: circumflex
-13: diaeresis
-14: caron
Note that 1C4-1C6 are covered but they are also expanded.
-15: breve (cyrillic are also covered? at least 4C1/4C2 are.)
-16: dialytika and tonos (category 0F though)
-17: macron
-19: tilde
-1A: ring above | 212B
-1B: ogonek ("WITH OGONEK;")
-1C: cedilla (WITH CEDILLA;")
-1D: double acute | acute and dot above
-1E: stroke, except for 0E[1F] and cp{19B, 1BE} |
circumflex and acute | 18B,18C,19A,289
(i.e. they not one-to-one mapping. Neither that every
"stroke" are mapped to 1E, nor not every 1E are mapped to
"stroke".)
-1F: diaeresis and acute | with circumflex and grave | l slash
beware "symbol slash"
-20: diaeresis and grave | 19B,19F
-21: breve and acute | D8,F8
-22: caron and dot above | breve and grave
-23: macron and acute
-24: macron and grave
-25: diaeresis and caron | dot above and macron | tilde and acute
-26: ring above and acute
-28: diaeresis and macron | cedilla and acute |
macron and diaeresis
-29: circumflex and tilde
-2A: tilde and diaeresis
-2B: stroke and acute
-2C: breve and tilde
-2F: cedilla and breve
-30: ogonek and macron
-43: hook, except for cp{192,1B2,25A,25D,27B,28B,2B1,2B5} |
left hook | with hook above except for cp{1EF6,1EF7} |
27D,284
-44: double grave | 1EF6,1EF7
-46: inverted breve
-48: preceded by apostrophe (actually only 149)
-52: horn
-55: line below | circumflex and hook above
-57: palatal hook (actually only 1AB)
-58: dot below except for cp{1EA0,1EA1}
-59: "retroflex" (without "WITH") | diaeresis below | 1EA0,1EA1
-5A: ring below | 1E76,1E77
-60: circumflex below except for cp{1E76,1E77} | horn and acute
-61: breve below | horn and grave
-63: tilde below | 2125
-68: D0,F0,182,183 | dot below and dot above | topbar
-69: right half ring | horn and tilde
-6A: circumflex and dot below
-6D: breve and dot below
-6E: dot below and macron
-95: horn and hook above
-AA: horn and dot
(for 01-0D and 7B-8A, they are not related to diacritics.)
-38: Arabic-Indic numbers (660-669)
-39: extended Arabic-Indic numbers (6F0-6F9)
-3A: Devanagari numbers (966-96F)
-3B: Bengali numbers (9E6-9EF)
-3C: Bengali currency enumerators (9F4-9F9)
-3D: Gurmukhi numbers (A66-A6F)
-3E: Gujarati numbesr (AE6-AEF)
-3F: Oriya digit numbers (B66-B6F)
-40: Tamil numbers (BE7-BF2)
-41: Telugu numbers (C66-C6F)
-42: Kannada numbers (CE6-CEF)
-43: Malayam numbers (D66-D6F)
-44: Thai numbers (E50-E59)
-45: Lao numbers (ED0-ED9)
-47: Roman numbers (2160-2182)
-4E: Hangchou numbers (3021-3029)
-E0[64]: 2107 (Eurer)
-E0[87]: some Tone letters (TONE TWO / TONE SIX)
-EE: Circled letter-or-digits and katakanas
CIRCLED {DIGIT|NUMBER|LATIN|KATAKANA}
numbers (2460-2473,2776-2793,24EA)
latin (24B6-24E9)
katakana (32D0-32FE)
-F3: Parenthesized enumerations
numbers (2474-2487)
latin (249C-24B5)
PARENTHESIZED {DIGIT|NUMBER|LATIN}
-F4: Numbers with dot (2488-249B)
{DIGIT|NUMBER} * FULL STOP
-258,25C-25E,285,286,29A,297 -> 0E[80-86,88]
-27F,2B3-2B6 -> 0E 8A[80-84]
-3D3 -> 0F[44]
-476,477 -> 10[46]
-215F -> 0C[03]
-20D0-20E1 -> 01[DD-F0]
-483-486 -> 01[94-97]
-559,55A -> 01[98,99]
-711 -> 01[9A]
-346-348,2BE-2C5,2CE-2CF -> 01[74-7F]
-2D1-2D3,2DE,2E4-2E9 -> 01[81-8A]
-342,343 -> 01[8D,8E]
-345 -> 01[90]
-700-780 01[8D-AF]. Maybe there is some kind of traditional
order in Estrangela, but for now am not sure.
/*
-740-742 -> 01[8D-8F]
-747,748,732,735,738,739,73C,73F,743-746,730 -> 01[90,91,94-9F]
-731,733,734,736,737,73A,73B,73D,73E,749,74A,7A6-7A9
-> 01[A0-AA,AC-AF]
*/
-7AA-7B0 -> 01[B0-B6]
-591-5C2 except for 5BA,5BE -> 01[03-33] in order
No further patterns for >= 80
TODO: Below are not done yet:
- x < 0x80 in non-"0E" part
- 03 <= x <= 0D in "0E" part
- 7B <= x <= 7F in "0E" part
**** sortkey details by category
1 specially ignored ones (Japanese, Tamil, Thai)
IdentifyBy: constants
Unicode: 3099-309C, BCD, E47, E4C, FF9E, FF9F
SortKey: 01 01 01 01 00
2 shift weight characters
They are either at 01 01 01 01 or 06, depending on StringSort. For
convenience, I use 06 to describe them.
2.1 control characters (specified as such in Unicode), except for
whitespaces (0009-000D).
ProcessAfter: 4.1
IdentifyBy: UnicodeCategory.Control
Unicode: 0001-000F minus 0009-000D, 007F-009F
SortKey: 06 03 - 06 3D
2.2 Apostrophe
IdentifyBy: constant
Unicode: 0027,FF07 (')
SortKey: 06 80 (and width insensitive equivalents)
2.3 minus sign, hyphen, dash
minus signs: FE63, 207B (super), 208B (sub), 002D, 00FD (full-width)
hyphens: 00AD (soft), 2010, 2011 (nonbreaking) ... Unicode HYPHEN?
dashes, horizontal bars: FE58 ... UnicodeCategory.DashPunctuation
IdentifyBy: UnicodeCategory.DashPunctuation
SortKey: 06 81 - 06 90 (and nonspace equivalents)
2.4 Arabic spacing and equivalents (64B-652, FE70-FE7F)
They are part of nonspacing mark, but not equal.
SortKey: 06 A0 - 06 A7 (and nonspace equivalents)
3 nonprimary characters, mixed.
ModifierSymbol, except for that are not in category 0 and "07" area
(i.e. < 128) nor those equivalents
NonSpacingMark which is ignorable (IsIgnorableNonSpacing())
// 30D, CD5-CD6, ABD, 2B9-2C5, 2C8, 2CB-2CD, 591-5C2. NonSpacingMark in
// 981-A3C. A4D, A70, A71, ABC ...
TODO: I need more insight to write table generator.
SortKey: 01 03 01 - 01 B6 01
This part of MS table design is problematic (buggy): \u0592 should
not be equal to \u09BC.
I guess, this buggy design is because Microsoft first thought that
there won't be more than 255 characters in this area. Or they might be
aware of the problem but prefer table optimization.
Ideal solutions:
1) We should not mix those code (make things sequential) and expands
level 2 length to 2 bytes. Instead of having direct value, we
could use index (pointer) to zero-terminating level 2 table.
2) Include those charactors from minor cultures here.
If in "discriminatory mode", those tables could be still provided
as to be compatible to Windows.
Additionally there seems some bugs around Modifier letter collection.
For example, 2C6 should be nonspacing diacritical character but it
is regarded as a primary character. The same applies to Mandarin
tone marks (2C9-2CB) (and there's a plenty of such characters).
4 space separators and some kind of marks
4.1 whitespaces, paragraph separator etc.
UnicodeCategory.SpaceSeparator : 20, 3000, A0, 9-D, 2000-200B
SortKey : 07 02 - 07 18
4.2 some OtherSymbols: 2422-2423
SortKey : 07 19 - 07 1A
4.3 ASCII compatible marks ('!', '^', ...)
Non-alpha-numeric < 0x7F except for [[+-<=>']]
small compatibility equivalents -> itself, wide
4.3 other marks
FIXME: how to identify them?
some Punctuations: InitialQuote/FinalQuote/Open/Close/Connector
some OtherSymbols: 2400-2424
3003, 3006, 2D0, 10FB
remaining Puncuations: 9xx, 7xx
70F (Format)
SortKey : 07 1B - 07 F0
5 mathmatical symbols
InitialQuotePunctuation and FinalQuotePunctuation in ASCII
(not Quotation_Mark property in PropList.txt ; 22, 27)
byte area MathSymbol: 2B,3C,3D,3E,AB,B1,BB,D7,F7 except for AC
some MathSymbol (2044, 208A, 208C, 207A, 207C)
OtherLetter (1C0-1C2)
2200-22FF MathSymbol except for 221E (INF. ; regarded as a number)
SortKey : 08 02 - 08 F8
6 Arrows and Box drawings
09 02 .. 09 7C : 2300-237A
only primary differences
09 BC ... 09 FE : 25A0-AB, 25E7-EB, 25AC-B5, 25EC-EF, 25B6-B9,
25BC-C3, 25BA-25BB, 25C4-25D8, 25E6, 25DA-25E5
21*,25*,26*,27*
This area contains level 2 values.
2190- (non-codepoint order)
note that there are many compatibility equivalents
2500- except for 266F (#)
SortKey : 09 02 - 09 7C, 09 BC 01 03 - 09 BC 01 13,
09 {BD|BE|BF} 01 {03|04}, ...
TODO: fill the patterns
7 currency sumbols and some punctuations
byte CurrencySymbols except for 24 ($)
byte OtherSymbols (A7-B6)
ConnectorPunctuation - 2040 (i.e. FF65, 30FB)
OtherPunct/ConnectorPunct/CurrencyCymbol 2020-20AC - 20AC
OtherSymbol 3012-303F,3004,327F
MathSymbol/OtherSymbol 2600-2767 (math = 266F)
OtherSymbol 2440-244A, 2117
20AC (CurrencySymbol)
Sortey : 0A 02 - 0A FB
8 (C) numbers
all DecimalDigitNumber, LetterNumber, non-CJK OtherNumber.
9F8.
digits, in numeric order. We can use NET_2_0 CharUnicodeInfo.
221E. (INF.)
SortKey : 0C 02 (9F8), 0C 03 - 0C E1 (normal numbers), 0C FF (INF.)
9 (E) latin letters (alphabets), mixing alphabetical symbols
Alphabets, A to Z, mixing alphabetical symbols. See below.
F8-2B8 except for (1BB-1BD and 1C0-1C3), but not sequential.
2E0-2E3.
For diacritical orders, see level 2.
For 'A' it is "0E 02", for 'B' "0E 09" ... 'Z' "0E A9", ezh "0E AA".
0E B3 (1BE), 0E B4 (298)
There are CJK compatibility characters (3800-) and letterlike
symbols (2100-) in those A-to-Z area, ordered by character name.
Primary weights are sometimes culture-dependent.
FIXME: [0E 0D], [0E 0E], [0E 4B], [0E 75], [0E B2] are unknown
02: A
03: C4 in sk|vi
04: C1 in is|pl|vi
05-08: CJKext
09: B
0A: C
0B: 10D in hr|lt|lv|pl, 107 in pl
0C: C7 in az|tr, 10D in cs|sk, 106 in hr
0F-19: CJKext
1A: D
1B: 189 (African D)
1C: 2A3 (DZ Digraph)
1D: 1C6 (dz) in hr
1E: 110 (D with stroke) in hr
1F-20: CJKext
21: E
22: 18F=259 in az, E9 in is, 119 in pl, EA in vi, 1EBE-1EC7 in vi
23: F
24: CJKext
25: G
26: 11F in az|tr, 123 in lv
28-2B: CJKext
2C: H
2D: 267 (Heng with hook)
2E: 33CB in az, 33CA in tr
2F-31: CJKext
32: I
33: CD in is, 79 in lt
34: CJKext
35: J
36: K
37-47: CJKext
48: L
49: 2114
4A: 1C9 in hr
4C: 142 in pl
4D-50: CJKext
51: M
52-6F: CJKext
70: N
71: 2116
72: 144 in pl
73: F1 in es, 1CC in hr
74: 14B
76-7B: CJKext
7C: O
7D: F6 in az|hu|tr, 151 in hu, F3 in is|pl, F4 in sk|vi, 1ED0-1ED9 in vi
7E: P
7F-88: CJKext
89: Q
8A: R
8B: 211E
8C: 211F
8D: 159 in cs|sk
8E-90: CJKext
91: S
92: 2108
93: 2120
94-95: CJKext
96: 17F (LATIN SMALL LONG S)
97: 15F in az|tr, 161 in cs|hr|lt|lv|sk|sl, 7A,179-17C in et, 15B in pl
98: 17E in et, 15F in ro, 15B in sl
99: T
9A: 2121
9B: CJKext
9C: 2122
9D: 2A6
9E: 166
9F: U
A0: FA in is, 1B0,1EE8-1EF1 in vi
A1: FC in az|tr, 56,57 in et, FC,171 in hu, FB in vi
A2: V
A3: 2123
A4: W
A5: CJKext
A6: X
A7: Y
A8: FD in is
A9: Z
AA: 292
AB: DE in is, 17E in lt|lv, 17A in pl
AC: E6 in da|is, 1E3 in is, 17C in pl, 17E in sl
AD: 17E in cs|hr|sk, E5 in fi, F6,F8 in is 17A in sl
AE: F6,F8,151 in da
AF: E4 in fi
B0: F6,F8,151 in fi
B1: E5 in da, "aa" in da
B3: 1BE
B4: 298
10 culture dependent letters (general)
0F: 386-3F2 ... Greek and Coptic
386-3CF: [0F 02] - [0F 19] (consider primary equivalents)
3D0-3EF: [0F 40] - [0F 54]
10: 400-4E9 ... Cyrillic.
For 400-45F and 4B1, they are mostly UCA DUCET order.
After that 460-481 follows, by codepoint.
(490-4FF except for 4B1 and Cyrillic supplementary are unused.)
11: 531-586 ... Armenian.
Simply sorted by codepoint (handle case).
12: 5D0-5F2 ... Hebrew.
Codepoint order (handle case).
13: 621-6D5 plus 670 (NonSpacingMark) ... Arabic
Area 1:
They look like ordered by Arabic Presentation Form B except
for FE95, and considering diacritical equivalents maybe based
on the primary character area (621-6D5).
There are still some special characters: 67E,686,698,6AF ...
which might not have equivalent characters (I wonder how they
are inserted into the presentation form B map).
Solution:
- hamza, waw, yeh (621,624,626) are special: [13 07]
- For all remaining letters, get primary letter name
and store it into dictionary. If unique, then
increment index by 4 from [13 0B]
Area 2:
674-6D5 : by codepoint from [13 84].
14: 901-963 exc. 93A-93D 950-954 ... Devanagari.
For <905 codepoint order, x2 from [14 04].
For 905-939 codepoint order, x4 from [14 0B].
For 93E-94D codepoint order, x2 from [14 DA].
15: 982-9FA ... Bengali. Actually all UnicodeCategories except for
NonSpacingMark, DecimalDigitNumber and OtherNumber.
For <9E0 simple codepoint order from [15 02].
For >9E0 simple codepoint order from [15 3B].
16: A05-A74 exc. A3C A4D A66-A71 ... Gurmukhi.
The same as UCA order, x4 from [16 04].
17: A81-AE0 exc. ABC-ABD ... Gujarati.
Mostly equivalent to UCA, but insert {AB3,A81-A83} before AB9,
x4 from [17 04].
18: B00-B70 ... Oriya
All but NonSpacingMark and DecimalDigitNumber, by codepoint.
19: B80-BFF ... Tamil
BD7 is special : [19 02].
B82-B93 (vowels) : x2 from [19 0A].
B94 (vowel AU) : [19 24]
For consonant order Windows has native Tamil order which is
different from UCA.
http://www.nationmaster.com/encyclopedia/Tamil-alphabet
(The order is still different in "Grantha" order from TAM.)
So, we should just hold constant array for consonants.
And put them in order, x4 form [19 26].
BBE-BCC : SpacingCombiningMark and BC0 ... x2 from [19 82].
1A: C00-C61 ... Telugu.
C55 and C56 are ignored (C5x line and remaining part of C6x
line just look like ignored).
C60 and C61 are specially placed. C60 after C0B, C61 after C0C.
Except for above, by codepoint, x3 from [1A 04].
1B: C80-CE5 ... Kannada.
CD5,CD6 (and CE6-CEF: DecimalDigitNumber) are ignored.
by codepoint, 3x from [1B 04].
1C: D02-D40 ... Malayalam.
by simple codepoint from [1C 02].
(1D: Sinhala ... totally ignored?)
1E: E00-E44 ... Thai.
preceding vowels (E40-E44) by codepoint [1E 02 - 1E 06]
consonants (E01-E2A) by codepoint, x6 from [1E 07].
1F: E2B-E5B,E80-EDF ... Thai / Lao. (Thai breaks the category wall.)
Thai:
remaining consonants (E2B-E2E) by codepoint, x6 from [1E 07].
remaining vowels (E2F-E3A) by codepoint.
E45,E46,E4E,E4F,E5A,E5B
Lao:
E80-EDF by codepoint from [1F 02].
21: 10A0-10FF ... Georgian
Mostly equal to UCA order, but swap 10E3 <-> 10F3,
x5 from [21 05].
11 (22) japanese kana letters and symbols, not in codepoint order
For single character, the sortkeys look like:
- Katakana normal A, Half Width (FF71) : FF 02 C4 FF C4 FF 01 00
- Katakana normal A, Full Width (30A2) : FF C4 FF 01 00
- Hiragana normal A, Full Width (3042) : FF FF 01 00
Actually for level 4 weights, there is a different rule (see
"level 4" format above).
There is also 32D0 (normal katakana A with circle) that have
diacritic difference.
For primary weights, 'A' to 'O' are mapped to 22-26, 'Ka' to 'Ko'
are to 2A-2E, 'Sa' to 'So' are to 32-36 ... and follows.
'Nn' is special: [22 80].
After Kana characters, there are CJK compat characters.
From 22 97 01 01 01 01 00 (3349) to 22 A6 01 01 01 01 00 (333B) are
sorted in JIS table order (CP932.TXT). Remaining square characters
are maybe sorted in Alphabetic order.
UCA DUCET also does not apply here.
12 (23) bopomofo letters
3105-312C: simple codepoint order from [23 02].
13 culture dependent letters 2
710-72C : Estrangela (ancient Syriac).
codepoint order.
711 is excluded (superscript).
714,716,71C,724 and 727 are "alternative" characters.
SortKey: [24 0B]-[24 60], by x where x is 2 for those
which is "alternative" defined above, otherwise 4.
780-7A5 : Thaana
Equals to UCA order, x2 from [24 6E].
(Maybe we should add remaining minor-culture characters here. Tibetan,
Limbu, Tagalog, Hanunoo, Buhid, Tagbanwa, Myanmar, Kumer, Tai-Le,
Mongolian, Cherokee, Canadian-Aboriginal, Ogham, Runic are ignored)
14 (41-45) surrogate Pt.1
15 (52 02-7E C8) hangul, mixing combined ones
It starts from 1100. After width-insensitive equivalents, those
syllables (from AC00) follow (until AE4BD7A3).
It follows kinda based on some formula (sometimes it looks not
e.g. 1117). FIXME: this area should be clarified more.
Hangle Syllables should not be filled in the table. Instead, they
can be easily computed by the following formulum:
// rc is the codepoint for the input Syllable
// (p holds "category << 8 + level1weight")
int ri = ((int) rc - 0xAC00) + 1;
ushort p = (ushort)
((ri / 254) * 256 + (ri % 254) + 2);
Hangul Jamo cannot be filled in the table directly, since
U+1113 - U+159 holds additional primary key bytes.
FIXME: find out how they can be computed.
See http://dev.icu-project.org/cgi-bin/viewcvs.cgi/*checkout*/icuhtml/design/collation/ICU_collation_design.htm?rev=HEAD&content-type=text/html#Hangul_Implicit_CEs
16 (9E 02-F1 E4) CJK
9E 02-F0 B4 [3192-319F,3220-3243,3280-32B0,4E00-9FA5] : CJK mark,
parenthesized CJK (part), circled CJK (part), CJK ideograph.
Ordered but condidering compatible characters (i.e. there is
no other way than having massive mapping).
F0 B5-F1 E4 [F900-FA2D]. CJK compatibility ideograph.
LAMESPEC: in the latest spec CJK ends at 9F BB. Since MS table
joins these two categories without any consideration, it is
impossible to insert those new characters without breaking binary
compatibility.
17 (E5 02-FE 33) PrivateUse.
In fact it overlaps to CJK characters (maybe layout design failure).
18 (F2 01-F2 31) surrogate Pt.2
In fact it overlaps to PrivateUse (maybe layout design failure).
19 (FE FF 10 02 - FE FF 29 E9) CJK extensions
3400-4DB5. Ordered.
They should be computed, since this range should be anyways
checked (to not directly acquire the sortkey values but needs
FE FF part) and anyways it can be computed.
20 (FF FF 01 01 01 01 00) special.
Japanese extender marks:
3005, 3031, 3032, 309D, 309E, 30FC, 30FD, 30FE, FF70
LAMESPEC: In native context Microsoft's understanding of Japanese
3031 and 3032 is wrong. They can never be used to repeat *just
previous one* character, but are usually used to repeat two or
more characters. Also, 3005 is not always used to repeat exactly
one character but sometimes used to repeat two (or possibly more)
characters.
Arabic shadda: FE7C (isolated), FE7D (medium)
(Actually they are not extender in Unicode PropList.txt)
- by UnicodeCategory -
DashPunctuation 6 (no exception)
DecimalDigitNumber C (no exception)
EnclosingMark 1 E (no exception)
Format 7 (only 70F)
LetterNumber C (no exception)
LineSeparator 7 (only 2028)
ParagraphSeparator 7 (only 2029)
PrivateUse
SpaceSeparator 7 (no exception)
Surrogate
OtherNumber C(<3192), 9E-A7 (3124<)
Control 6 except for 9-D (7)
FinalQuotePunctuation 7 except for BB (8)
InitialQuotePunctuation 7 except for AB (8)
ClosePunctuation 7 except for 232A (9)
OpenPunctuation 7 except for 2329 (9)
ConnectorPunctuation 7 except for FF65, 30FB, 2040 (A)
OtherLetter 1, 7, 8 (1C0-1C2), C, 12-FF
MathSymbol 8, 9, 6, 7, A, C
OtherSymbol 7, 9, A, C, E, F, <22, 52<
CurrencySymbol A except for FF69,24,FF04 (7) and 9F2,9F3 (15)
LowercaseLetter E-11 except for B5 (A) and 1BD (C)
TitlecaseLetter E (no exception)
UppercaseLetter E,F,10,11,21 except for 1BC (C)
ModifierLetter 1, 7, E, 1F, FF
ModifierSymbol 1, 6, 7
NonSpacingMark 1, 6, 13-1F
OtherPunctuation 1, 7, A, 1F
SpacingCombiningMark 1, 14-22
*** Culture dependent design
(To assure this section, run the simple dumper code shown above,
with all the supported cultures.)
**** primary cultures and non-primary cultures
This code is used to iterate character dump through all cultures,
using sort key dumper put above.
public static void Main ()
{
foreach (CultureInfo ci in CultureInfo.GetCultures (
CultureTypes.AllCultures)) {
ProcessStartInfo psi = new ProcessStartInfo ();
psi.FileName = "../allsortkey.exe";
psi.Arguments = ci.Name;
psi.RedirectStandardOutput = true;
psi.UseShellExecute = false;
Process p = new Process ();
p.StartInfo = psi;
p.Start ();
string s = p.StandardOutput.ReadToEnd ();
StreamWriter sw = new StreamWriter (ci.Name + ".txt", false, Encoding.UTF8);
sw.Write (s);
sw.Close ();
}
}
For each sub culture (that has a parent culture), its collation
mapping is identical to that of its parent, except for az-AZ-Cyrl.
Additionally,
- zh-CHS = zh-CN = zh-SG = zh-MO : pronounciation
- zh-TW = zh-HK = zh-CHT : stroke count
- da = no
- fi = sv
- hr = sr
(UCA implies that there are some cultures that sorts alphabets from
large to small, but as long as I see there is no such CultureInfo.)
**** Latin characters and NonSpacingMark order tailorings
div : FDF2 is 24 83 01 01 01 01 00 (only 1 difference)
syr : some NonSpacingMarks are totally ignorable.
tt,kk,mk,az-AZ-Cyrl,uk : cyrillic difference
az,et,lt,lv,sl,tr,sv,ro,pl,no,is,hu,fi,es,da : latin difference
fr : 1C4-1C6.
sk,hr,cs : latin and NonSpacingMark differences
ja,ko : 5C
**** CJK character order tailorings
There are five different CJK orderings:
default, ko(-KR), ja(-JP), zh-CHS and zh-CHT
They have very different CJK mapping for each.
Since they seems based on traditional encodings, we are likely to
provide other constant tables and switch depending on the culture.
ko : CJK layout difference (52 -> 80)
ja,zh-CHS,zh-TW : dash (5C), CJK layout difference.
Target characters are : CJK misc (3190-), Parenthesized CJK
(3200-), CJK compat (3300-), CJK ideographs (4E00-),
CJK compat ideograph (F900-), Half/Full width compat (FF00-)
Additionally for Korean: Jamo (1100-), Hangle syllables (AC00)
Japanese CJK order looks based on JIS table order. Those characters
which are also in JIS table are moved to 80 xx. Those which are *not*
in JIS table are left as is (9E-FE).
Additionally, Windows has different order for characters below:
4EDD,337B,337E,337D,337D,337C
They come in front of the first CJK character.
Maybe Korean CJK order respects KS C 5619. Note that Korean mixes
Hangul and CJK in their order so it's not flat order without indexes
(thus, for CJK they are not computable). Also, there is an extra
level2 values for Korean CJK map.
For some Chinese such as zh-CHS, character order is based on pinyin.
And for remaining Chinese such as zh-TW, it is stroke count based.
CLDR of unicode.org has reference ordering of those characters, so
our collation table extracts the sorting order from it.
http://www.unicode.org/cldr/
**** Accent evaluation order
With French cultures, diacritical marks are counted in reverse order.
French ordering does not affect only on some diacritics (Japanese
voice mark is not affected - FIXME: I doubt it, because the algorithm
does not seem to allow it).
Some other cultures might also have different ones, but not obvious.
** Mono implementation plans
*** Collator
CompareInfo contains many overloaded methods that are just for
convenience. This class contains almost only required members.
This class also provices access to tailoring information which is
culture instance dependent:
- French sorting
- contractions/expansions - returns contraction or expansion
- diacritical remapping
- CJK custom mapping
For data area, see CollationDataStructures.txt for now.
*** UnicodeTable (for now MSCompatUnicodeTable)
Provides several access to character information with related to
the collation element table (of our own).
FIXME: I want to fix some bugs in Windows collation table especially
to not ignore some characters, but it requires table modification
which results in further memory allocation. Maybe it would be done
as a patch for the runtime (or classlib) sources.
- ignorable, ignorable nonspace, normalize width, normalize kanatype
- level 4 sortkey provision method(s)
**** character comparison
Since composite character is likely to *not have* equivalent
codepoint, character comparison could not just be done by expecting
"resulting char" value.
In contrast, since composite character is likely to *do have*
equivalent codepoint, character comparison could not also just be done
by comparing "source char" value.
***** future optimizations
From where those codepoints differ, for each strings it adjusts the
position so that it represents exactly one character element. That is,
find primary character as the start of the range and the last
nonprimary character as the end of the range.
Once Compare() adjusted the character location to be valid
comparison position, further comparison is done as usual comparison,
i.e. sortkey comparison considering comparisonLevel.
**** Characters in the table / characters computed
Currently I plan not to contain following characters in the table
but compute on demand:
- PrivateUse
- Surrogate
**** CJK Unified Ideographs
For CJK unified ideographs, I had to make those culture-dependent
tables in memory. Since they came from some classical encodings, they
are not computed. Thus, they are in separate table.
**** Level 4: Kana type
The table does not contain level 4 (kanatype) properties for
the whole characters. They can be simply computed.
**** Level 3: Case/Width properties
Case properties will be stored as a byte array, with limited areas of
codepoint (cp < 3120 || FE00 < cp).
For Hangul characters, it will be computed by codepoint areas.
**** Level 2: Diacritical properties
The table will be composed as a byte for a character. If we provide
non-buggy mode (Windows is buggy here by design; it just sums
secondary weight values up), the values will come from UCA and
non-blocking check will be introduced.
Note that Japanese voice marks are considered at level 2 but no need to
have maps.
** Reference materials
Developing International Software for Windows 95 and Windows NT
Appendix D Sort Order for Selected Languages
http://www.microsoft.com/globaldev/dis_v1/disv1.asp?DID=dis33d&File=S24BF.asp
UTR#10 Unicode Collation Algorithm (It is still informative)
http://www.unicode.org/reports/tr10/
UAX#15 Unicode Normalization
http://www.unicode.org/reports/tr15/
especially its canonical/compatibility equivalent characters might
be informative to get those equivalent characters.
To know which character can be expanded, Unicode Character Database
(UCD) is informative (it's informative but not normative to us)
http://www.unicode.org/Public/UNIDATA/UCD.html
Decent char-by-char explaination is available here:
http://www.fileformat.info/info/unicode/
Wine uses UCA default element table, but has windows-like character
filterings support in their LCMapString implementation:
http://cvs.winehq.com/cvsweb/wine/dlls/kernel/locale.c
http://cvs.winehq.com/cvsweb/wine/libs/unicode/sortkey.c
Mimer has decent materials on culture specific collations:
http://developer.mimer.com/collations/
This is written in Japanese, but awesome analysis on MS Access
string sorting:
http://www.asahi-net.or.jp/~ez3k-msym/comp/acccoll.htm