| 1. Introduction Collation is not uniform; launguage and culture에 따라 다양 같은 언어라도 application에 따라다름. : 사전, phonebook, book index 사용자 설정에 따라 customized or configured 될수 있음. : 점이 있느냐 없느냐, 소문자 앞에 대문자가 있느냐 없느냐. by language, by usage, by customization. 1.1 Multi-Level Comparison Level 1 base character Level 2 accents Level 3 Case L4 Puncutation Ln Tie-breaker 1.2 Canonical Equivalence they are essentially the same character but can be represented in different ways. 1.3 Contextual Sensitivity CH acts like a character after C. 1.4 Customization .Languages .Strength .Case Ordering. .User-Defined Rules. Merging Tailorings. Script Order. Numbers. 1.5 Other Applications of Collation sorting말고 searching이 있음. searching에서는 strengh level이 매우 중요함. O" in Swedish collation: O에서 P를 찾았는데 O" 가 없으면 고객은 unhappy. ch in Slovak refs UTS #18, UAX #29 1.6 Interleaved Levels Level은 interleaved 될 필요가 있다. DB에서 2개의 필드를 sorting하는 예제. 가장 간단한 방법은 field by field로 순차적으로 sorting하는것. 첫번째 필드를 모든 레벨로 sorting하고 그다음 두번째 필드를 모든 레벨로 sorting. 이렇게 하면 field 1이 이름이고 field 2가 성일때 성의 순서를 기대할수 없다는것. 두번째 방법은 첫 필드의 base level을 제외한 것은 무시하고 비교하는것. 단점은 첫번째 필드의 순서가 올바르지 않음. 올바른 방법은 field를 sorting할때 merge하는것. 필드의 모든 차이를 고려함. level을 uniform으로 고려. 모든 필드에서 accent는 무시 혹은 accent, case무시 등. 1.7 Performance collation은 performance critical feature. 각 collation engine은 주어진 string으로부터 sort key의 생성을 제공함. A <= B accoding to C if and only if sortkey(C, A) <= sortkey(C, B) 일반적으로는 simple string comparison이 sort key를 generate하는것보다 5~10배 빠르지만 multiple comparison에서는 더 빠르다. 1.8 Common Misperceptions 1. Collation은 character set이나 레퍼토리에 의해 align되지 않는다. Swedish나 German이나 character는 대부분 같지만 sorting order는 다름. 2. Collation은 code point (binary) order가 아님. 제대로된 순서를 얻으려면 binary ordering이 아니라 language-sensitive collation을 사용해야한다. 3. Collation은 string의 property가 아님. Language로 tag된 city를 고려하면. 독일인은 German order로 sorting을 기대한다. O와 P사이의 도시를 찾을때 O"로 시작하는 도시는 Z후에 나오는게 아니라 여기에 포함되어야 한다. 4. Collation order는 concatenation이나 substring에서도 preserve되지 않는다. 즉 x < y 일때 x + z < y + z 는 성립하지 않는다. x < y != xz < yz x < y != zx < zy xz < yz != x < y zx < zy != x < y 5. Collation order는 different collation sequence로부터 생성된 sort key를 비교할때 preserve되지 않는다. A <= B according to F if and only if sortkey (F, A) <= sortkey (F, B) A <= B according to G if and only if sortkey (G, A) <= sortkey (G, B) sortkey(F, A) and sortkey (G, B)사이의 관계는 nothing 6. Collation order는 stable sort가 아님. sort algorithm의 property가 아님. 3.4 Stability참조 7. Collation order is not fixed. 시간에 따라 collation order는 vary. collation은 주의깊게 version되어야함. 1.9 The Unicode Collation Algorithm DUCET(Default Unicode Collation Element Table)은 모든 unicode 문자에 대한 default collation 을 정하는 데이터. 문자를 위한 map데이터를 포함하고, sort key를 제공. (16bit unsigned integer) 두개 이상의 sort key가 생성될수 있음. Canadian sorting standard[CanStd]와 ISO14651, IBM연구소 등에서 구현한 multi-level key weighting을 가정. 기본적으로 알고리즘은 3 fully-customizable level을 사용. Latin script 에서 각 level은 다음과 같다. 1. alphabetic ordering 2. diacritic ordering 3. case ordering 하지만 구현은 더 많은 level도 가능. 1.9.1 Goals 1. 완전하고, 모호하지않고, unicode의 모든 문자의 순서를 정함. 2. 기본 순서와 관련된 canonical compatibility equivalence를 완벽하게 다뤄야함. 3. collation에서 기본적으로 무시하는 문자를 포함하여 collation level의 meaning과 assignment를 완벽히 정함. 4. 제멋대로 길이를 가진 스트링의 기본적인 collation order를 정하는 level weight를 이용하는 완벽한 룰을 정함. 5. language-specific ordering을 생성하는 override 메커니즘을(tailoring) 허용. Tailoring은 well-defined syntax를 제공하고 다른 well-formed ordering을 제공함. 6. performance와 memory requirement 둘다 효율적으로 algorithm을 구현, 주어진 standard ordering과 tailoring for any particular language는 무작위로 두개의 unicode를 입력받았을때 정확하게 같은 두 스트링의 순서를 만든다. 게다가 French accents tailoring은 Canadian과 ISO 1465 benchmark를 통과했음. Note: DUCET는 모든 할당된 unicode 문자에 대한 weight를 정확하게 list하지는 않지만 알고리즘ㄷ은 모든 unicode 에 대해서 well defined됨. 1.9.2 Non-Goals DECUT는 다음을 제공하지 않음. 1. reversibility : Collation Element에서 original character를 recover할수 없음. 2. numeric formatting: digits string이나 numerics는 numerical order로 sort되지 않음. 예 112 < 12 3. API: 알고리즘을 위한 API를 정하거나 요구하지 않음. 4. title sorting: a 같은 article을 제거한 도서목록 sorting은 지원하지 않음. 5. version간의 binary sort key 값의 Stability : 3.4참고 6. linguistic applicability : 대부분의 사용자 기대를 맞추기위해 linguistic tailoring이 필요함. Section 5 참조. 2. Conformance (일치) 알고리즘은 logical spec. 알고리즘에 의해 같은 순서로만 구현이 되면 구현은 자유롭게 바꿀수 있음. Collation Element Table에서 data는 다른 포맷을 사용하는것도 자유로움. sort key도 logical intermediate object이고 , 스트링 비교의 결과만 같으면 sort key는 여기서 정의한것과 다를수 있다. UCA 구현의 일치는 다음을 요구함. C1. 주어진 well-formed Unicode Collation Element Table에서 conformant 구현은 Section 4 Main Algorithm에서 생성된 것 처럼 같은 스트링 비교를 replicate한다. 특히 구현에서 지원하는 Unicode 캐릭터에 대해서는, 두개의 canonically equivalent string이 같도록 비교해야한다. conformant implementation은 올바른 캐릭터셋에 있는 스트링을 비교하면, Unicode로 변경된 스트링의은 같은 결과를 제공해야 한다. C2. conformant implementation은 최소한 3개 레벨의 collation을 지원해야한다. (그이상은 may) C3. bakward level의 feature, variable weighting, semisstability를 지원하는 conformant implementation은 이 스펙과 일치해야한다. 이들 feature는 반드시 요구되지는 않지만 backwards secondary level은 구현이 요구된다. (French에서 사용됨) C4. conformant implementation은 UTS의 version number를 정해야 한다. Collation element의 값은 Unicode Standard에 새로운 캐릭터가 추가될수 있음. 따라서 Unicode Standard version과 sync해야함. C5. claiming conformance to Matching Searching 구현은 UTS#10에 따라 구현, Section 8 Searching and Matching에 기술된 요구사항 참조. 3. Collation Element Table Collation Element Table은 하나의 문자부터 하나의 Collation Elements까지 매핑을 포함한다. Collation element는 3개 혹은 이상의 16bit weight로된 ordered list. 모든 특별하게 언급이 없는 code points는 implicit weight로 매핑. 구현은 16bit weight사용하지 않고도 같은 결과를 만들수 있다. first weight는 Level 1 weight (primary weight) second는 Level 2 weight (secodnary weight) third 는 level 3 weight (tetriary weight)... Collation element X는 X1, X2 등으로 압축해서 표현. 주어진 2 collation elemnt X and Y, 에대해서 다음을 notation Equals Notation X = _1 Y Meaning X_1 = Y_1 ... X < _1 Y ASCII로는 X < [n] Y A 3= B는 collation이 동일 A = B는 bit까지 완벽하게 같음 weight 가 0 이면 collation element는 해당 level에서 ignorable. 즉 해당 레벨에서 weight는 sorting에 관련이 없음. Level N에서 ignorable이면 N에서만이고 N+1은 아님. . Level 3 ignoreable (tetriary ignorable) is ignorable at Levels 1, 2, 3 but not Level 4. .어느 레벨에서도 ignorable이 아니면 non-ignorable .모든 레벨에서 ignorable이면 completely ignorable. MIN n 는 least weight in any collation element at level n MAX n is maximum weight in any collation element at level n 3.1 Linguistic Features. 3.1.1 Multiple Mappings one character가 one collation element에 매핑되지 않을수 있다. one to many , many to one 3.1.1.1 expansion [ae] 는 독립적인 문자로 쓰이지만 영어에서는 <a e> sequence와 같이 다뤄진다. Collation element는 a, e각각 weight value를 줌. 3.1.1.2 Contractions Spanish에서 ch는 하나의 collation element로 매핑된다. 순서는 c와 d사이임. soft hyphen이 분리된 문자임을 알도록 하기 위해서 쓰일수 있다. Slovak ch or Danish aa 3.1.1.3 Other multiple Mapping. Section 1.3 3.1.2 Frehcn Accents 어떤 language(특히 French)에서 accents는 스트링의 뒤에서부터 앞으로 sort된다. 이것은 DUCET에서 mark되는것은아니나 tailored table에서 나타날수 있다. accent를 위한 collation element와 base character는 level2에서 backwards로 mark된다. 3.1.3 Rearrancement 어떤 문자는 logical order로 code되지않는다. 태국어 모음 ㅡ.ㅡ; (Logical_Order_Excetioin property로 UCD에 표시) collation에서는 문자를 처리하기전에 이후 문자와 swapping함으로써 rearrange. 왜냐하면 논리적으로 afterwards에 속함. 이들 sequance의 처리는 Collation Element Table에서 contraction으로 처리됨. 3.1.4 Default Values DECUT에서나 typical tailoring에서 둘다, 대부분의 unaccented 문자는 primary wieght가 다름. secondary weights 는 MIN2와 같음. primary ignorable은 MIN2보다 큰 secondary weight를 가짐. compatibility나 case variant를 가진 문자는 primary 와 secondary weight가 같음 즉 a1 = A1 and a2 = A2 그러나 3 weight는 다름. unmarked chracter는 a3 = MIN3과 같음. well-formed Unicode Collation Element Table은 2혹은 3 weight가 uniform across table을 보장하지는 않음. capital A와 카타카나 ta는 둘다 3 weight임. 3.1.5 Collation Graphemes collation ordering 은 collation grapheme cluster를 정함. 순서를 정하는데 주요한 단위로 사용됨. ch는 spanish ordering에서 collation grapheme임. contraction에서 추가적인 ignorable chracter를 포함. collation grapheme 의 boundary를 정하는것은 다음 프로세스를 따름. 1. Set oldPosition to be equal to position 2. if postion is 스트링의 끝이면 리턴 3. 다음 element를 fetch하고 position의 문자를 패밍 4. collation element가 를 non-ignorable로 포함하고 position이 oldPosition과 다르면 position을 리턴 5. 아니면 position을 chracter의 마지막에 위치 6. Step2를 다시. 3.1.6 Combining Grapheme Joiner UCA는 collation weighting전에 Unicode Text string의 nomalization을 포함. U+34F CCJ (COMBINING GRAPHEME JOINER)는 UCA에서 주로 collation key weighting을 무시하고 Unicode에 기술된 스트링의 combining mark를 reordering을 block하는데 사용. 효과는 those combining mark와 연관된 secondary key weight의 순서를 invert한다.두 스트링이 각각의 구별된 key를 가지고 searching과 sorting에서 사용하면, combining grapheme joiner 나 combining mark없이 이들을 다루는것이가능? CGJ는 UCA에서 contraction의 formation을 막는데 사용. ch는 Sloval collation에서 single unit으로 sort, sequence <c, CGJ, h> 는 c다음 h로 sort될것이다. German에서 사용된다. u"는 u + " 로 sort. (u <2 u") dictionary sort는 ue <3 u" 3.2 Default Unicode Collation Element Table DUCET는 [Allkeys]를 제공. 모든 weighted character에 대해서 chracter부터 collation element까지 매핑을 제공. 문자는 순서로 리스트됨. table에 explicit하게 언급되지 않은 code point는 collation element로부터 wnsek. Section 7. Weight Derivation참조. 3타입 mapping이 있음. . Normal . - 하나의 Unicode character map이 하나의 collation element에 매핑 . Expention - 하나의 Unicode character가 collation element의 sequence에 매핑 . Contraction - Unicode 문자의 sequence가 collation element의 sequence(하나 혹은 이상)에 매핑 Contraction은 canonical decomposable chracter가 main weight table에서 primary weight가 구별되도록 주어진 인스턴스를 제공한다. 현재는 인도의 2 part vowel과 몇몇 Cyrillic accent문자가 각 스크립트에서 collation behavior를 만족하도록 매치할때. Contraction은 Thai/Lao reordering에서 제공됨. 3.2.1 File Format 3.2.2 Variable Weighting 3.3 Well-formed Collation Element Table 3.4 Stability |
Programming