2012年2月12日星期日

有趣的字符比较规则(Collation)

在理解了字符集、字符编码的概念后,另一个很少有人理解的问题是如何对字符进行比较,也就是Collation的概念。发现网上很多文章只是解释了字符集设置的同时捎带的说了一下Collation,所以我就想重点解释Collation。

前些天我突然意识到 mysql 默认是字符比较是不区分大小写的,比如“abc”、“ABC”和“aBc”认为是相等的。这和我的直觉不一致,尤其在编程语言中,两个字符串的内容完全一致才认为是相等的(equals),除非明确地使用不区分大小写的比较方法(如equalsIgnoreCase)。

(注:mysql 支持很多字符集,而每种字符集又有多种collation,各种字符集的默认collation都是以ci 结尾的,即不区分大小写的方式)

对文字做排序主要是为了方便查找,可以快速定位到自己要找的地方,比如在有序的通讯录中我们可以快速定位到“王”字开头的人,另外排序后看起来也会比较整齐美观。

对于中国人而言,比较缺少文字排序这方面的意识。因为汉字是象形文字,字数非常多,每个字都是独立的,在日常生活中字之间没有明确的先后顺序或相等规则一说。现在常见的是以汉字对应的拼音字母顺序和笔画顺序。用拉丁字母表示汉字的拼音是近代才出现的,历史较短。

与之相反,英语等西方语言是由数量较少的基本字母组成的,而这些基本字母是有明确顺序的。所以很自然的就有了以字母表为基础的排序规则,历史就很长了。

在Unicode中的CJK部分,据说是以四字典中的顺序为基础的。四字典的排序顺序为:《康熙字典》、《大漢和辭典》、《汉语大字典》、《大字源》。即在查一个汉字,先在《康熙字典》查,查不到再在《大漢和辭典》查,依次类推。而康熙字典是以部首笔画为序的。

而中国的GB2312、GBK 是以拼音为顺序的。

Collation就是对字符串如何比较的规则。也就是不同字符的前后顺序,以及哪些字符可以认为是相等的。比如在德语中 ß 可以看做 ss 。

Collation问题的本质是:一些表面上不同的符号,在人们看来可能是相同的,取决于人们是如何“认为”的。有些表面上不同的符号,其意义可能是相同的,或者在一定级别下认为是相同的。

对字符进行比较:如何判断相等、如何比较大小,影响到查询和排序问题。

相等问题英文中最常见的就是大小写问题,在计算机中大小写是不同的字符,对应的编码也不同,但人们在使用过程中,一般又当做是一样的。在中文中全角和半角字符在意义上是相同的,还有中文的数字也有大小写,如“一”和“壹”在一定意义上也是相同的。

相等的判断在mysql中就是== 或 like。一般在编程语言中,字符串是按照他们(对应的编码)是否完全相等来判断的,大小比较也是按照他们的字典顺序比较的。这样对计算机而言是非常简单的,把每个字符当做字节就是纯数字的判断,相等和比较大小都很容易。

但是在不同的国家、语言环境中,根据当地人的文化习惯制定了很多特殊的规则。要让计算机去遵循这些规则,毕竟机器是为人服务的。

Collation简单的说就是描述这种规则的,哪些字符认为是等价的,以及这些字符比较排序等。

更复杂一点说,里面又可以分一些不同的比较级别。比如在这个级别下,认为是不同的,但在另一个级别下就认为是相同的。

语言文化

1. 拉丁字母

拉丁字母主要就是我们常说的 26 个字母 a-z 及大写形式。

另外拉丁字母还有一些衍生字母:

尖音

Áá

Éé

Íí

Óó

Úú

Ýý

重音

Àà

Èè

Ìì

Òò

Ùù

折音

Ââ

Êê

Îî

Ôô

Ûû

德语变音/分音

Ää

Ëë

Ïï

Öö

Üü

Ÿÿ

软音

Çç

Şş

鼻音

Ãã

Õõ

Ññ

鼻化元音

Ąą

Ęę

Įį

Ųų

合字

Ææ

Œœ

Øø

IJij

ß

卢恩字母

Þþ

2. 德语

德语字母表是由拉丁字母组成,除了拉丁字母的26个字母外德语还有四个字母的变体。

Aa

(Ää)

Bb

Cc

Dd

Ee

Ff

Gg

Hh

Ii

Jj

Kk

Ll

Mm

Nn

Oo

(Öö)

Pp

Qq

Rr

Ss

(ß)

Tt

Uu

(Üü)

Vv

Ww

Xx

Yy

Zz

注意:不要把德语中的 ß 和 希腊字母 β 混淆。一般 ß 也可以用 ss 代替。

替换规则:Ü=Ue Ä=Ae Ö=Oe ß=ss

3. 瑞典语

瑞典语有29个字母:拉丁字母的26个加上Å / å、Ä / ä及Ö / ö。这3个字母排在z之后。W经常不算作一个独立的字母。

Aa

Bb

Cc

Dd

Ee

Ff

Gg

Hh

Ii

Jj

Kk

Ll

Mm

Nn

Oo

Pp

Qq

Rr

Ss

Tt

Uu

Vv

Ww

Xx

Yy

Zz

Åå

Ää

Öö

其它语言如法语西班牙语 等不再列出,请参考相关资料。

不同语言间Collation差异举例:

  1. 在瑞典语中z < ö,而在德语中ö < z。
  2. 在西班牙语中连字ch 在c之后,而在斯洛伐克语中 ch 看做独立字符排在 h 之后。
  3. 同样是在德语中,按字典规则:of < öf,而按电话簿规则:öf < of。
  4. 在主要的拉丁语言中,ø被看作是o的语音变种排在o旁边,而在挪威和丹麦语中是在z之后的独立字母。

大多数Collation有许多个规则:不仅仅是大小写不敏感,还包括重音符不敏感(“重音符” 是附属于一个字母的符号,象德语的‘Ö’符号)和多字节映射(例如,作为规则‘Ö’=‘OE’就是两个德语校对规则的一种)。

Collation是随国家、语言、文化的不同而不同的。比如德国、法国、瑞典对同样字符的排序是不同的。甚至对同一种语言也可能有不同的排序方式。西方语言一般是以字母表的顺序为基础,而东方语言一般是以语音或者字形为基础的。Collation也可以根据用户的偏好来设置,比如是否忽略标点、大写字母在小写字母之前还是之后。

一个有趣的现象:在我的Chrome浏览器上Ctrl+F搜索Ö会当做o来搜索、ß会当做ss来搜索,而在Firefox和IE就只当做自身来搜索。

Unicode Collation Algorithm (UCA)

UCA是Unicode技术标准 #10 的定义的内容,是说Unicode中如何Collation的。因为Unicode涉及的语言情况很多,充分考虑这些语言要求是比较复杂的。对Collation感兴趣的人强烈建议读此内容。

collation 不是 code point (binary) order。

字符在字符集中的顺序被称为二进制顺序,Unicode中就叫code point顺序。

二进制顺序对计算机而言是最容易最高效的处理方式,但这种顺序不一定符合人们的期望,比如ascii中大写字母排在小写字母的前面,所以才有collation,它是为了满足语言的特定要求。

严格的说collation是一种排序规则,独立于字符集

一种字符集可以有多种不同的collation。比如瑞典和德国共用大部分相同的字母,但是他们却有不同的排列顺序。

单个字符的顺序不意味着多字符也是这样,比如:

x < y 不意味着 xz < yz

x < y 不意味着 zx < zy

xz < yz 不意味着 x < y

zx < zy 不意味着 x < y

Java中的Collation

Java 最初就是支持Unicode的:

  1. Java 1.4 支持 Unicode 3.0
  2. Java 5 和 Java 6 支持Unicode 4.0
  3. Java 7支持Unicode 6.0

Java中以String、Character为字符串的基础,以及StringBuffer、StringBuilder 。

Java中的java.text包下提供了一些与Collation相关的类,主要是抽象类 Collator 及其具体子类 RuleBasedCollator。

相等和大小写问题

String.equals 方法是两个字符串的完全相同才认为是相等的。

String.equalsIgnoreCase 是不区分大小写的比较。

注意:Java中的大小写判断是基于Unicode的,也就是以 UnicodeData 文件的大小写映射信息来判断的,不仅仅是指26个字母的大小写,实际上包括了很多字符。

比如:"Ä".equalsIgnoreCase("ä"); 返回true,再比如"Ạ"的小写是"ạ"。

但是注意 String.toLowerCase、toUpperCase 和 Character.toLowerCase、toUpperCase稍有区别:

  1. Character.toLowerCase提供char 和 int(code point)来自不同参数的方法
  2. Character.toLowerCase是以UnicodeData 文件的大小写映射信息将字符参数转换
  3. String.toLowerCase 和语言环境有关,默认使用本地Locale规则进行大小写转换,同时也提供了带Locale参数的方法。
  4. 通常,应该使用 String.toLowerCase() 将字符映射为小写。String 大小写映射方法有几个胜过 Character 大小写映射方法的优点。String 大小写映射方法可以执行语言环境敏感的映射、上下文相关的映射和 1:M 字符映射,而 Character 大小写映射方法却不能。

String.toLowerCase 是和语言环境有关的,例如:土耳其语言环境中,小写字母 i 对应的大写字母不是英文的 I, "i".toUpperCase(new Locale("tr")); //输出 İ (上面有个点),而在一般语言环境中小写 i 对应的大写就是 I 。

"ß".toUpperCase(); // 输出 SS。这是1对多的映射。

Collator 及其子类 RuleBasedCollator.

Collator 是用于字符串比较的,所以它实现了Comparator接口。当然String类自身就实现了Comparable 接口。他们的差异是String的比较是按照字典排序的。而Collator 提供了区分语言环境的 String 比较,而进一步说是和Unicode Collation Algorithm (UCA)相关的比较方式。(另外 ICU 提供了C/C++和Java的UCA实现,它是一个Unicode和国际化支持的库。)

Java中Collator 提供了四种强度的差异级别:PRIMARY、SECONDARY、TERTIARY 和 IDENTICAL。具体每个级别的含义和特定的Locale相关。

例如在Locale.US等环境下,PRIMARY和SECONDARY强度是下不区分大小写的。

捷克语中,"e" 和 "f" 被认为是 PRIMARY 差异,而 "e" 和 "ě" 则是 SECONDARY 差异,"e" 和 "E" 是 TERTIARY 差异,"e" 和 "e" 是 IDENTICAL。

由于这种Collation实现比较稍复杂,而一般对String 列表排序的话,每个 String 要进行多次比较。所以从性能考虑,可以利用Collator类先将要比较的字符串一次性转换为CollationKey对象再做比较。

RuleBasedCollator 类是 Collator 的具体子类,它提供了一个简单的、数据驱动的表的 collator。利用它自定义collation的时候只要设计规则就行了。实际上抽象类Collator的工厂方法返回的特定 Locale的实例其实就是定义了某种规则的RuleBasedCollator对象。

随便说点Java字符串的基础部分:

Java的内部字符是以UTF-16为编码的,实际上UTF-16是变长编码。当初Java是以早期的Unicode为参考的,那时所有Unicode只需要16位就能表示(现在的BMP部分),所以char 选择了固定宽度的16位来表示一个字符。String内部是以char为基础的,索引值是指的char。但是后来Unicode中的字符数早就超过了这个限制。现在char 只能表示BMP部分的代码点(code point),BMP以外的增补字符需要2个char来表示,所以char被称为代码单元(code unit),而Unicode 代码点才表示真正的字符。int 是32位,在Java中用来表示所有的code point。因为以char为参数的方法处理不了增补字符,所以现在一般会提供两种方法以char为参数的和以int为参数的方法。

由于这个历史原因,导致Java 中常见的误解是char表示一个字符、length方法返回的是字符长度。实际上char是代码单元(code unit)、length返回是char的数量。而际上char是16位,只能表示基本字符BMP,而增补字符多于16位需要2个char来表示。所以求字符串长度或迭代字符的时候,完全正确的方法是使用基于代码点(code point)的方法,否则可能有误。

比如求String s的长度是: s.codePointCount(0, s.length());

Mysql相关

对数据库而言,Collation是很重要的,对于查找和排序需要符合用户语言环境的期望结果。

Mysql支持很多字符集和collation,每种字符集对应一种或多种collation,每个字符集有一个默认collation。mysql 各字符集的默认collation都是不区分大小写(xxx_ci)。

查看mysql支持的字符集及其默认collation命令:SHOW CHARACTER SET;

查看mysql支持的collation的命令:SHOW COLLATION;

上面两个语句都可附加like 做条件限定,如 LIKE 'utf8%' 。

mysql collation命名约定:以相关的字符集名开始,通常包括一个语言名,并且以_ci(大小写不敏感)、_cs(大小写敏感)或_bin(二进制)结束。

可以设置数据库、表、字段的默认字符集及其collation。

可以在sql语句中指定要使用的collation,如查询字段的条件或排序。BINARY 操作符表示使用二进制collation,相当于使用对应字符集的_bin 的 collation。

latin1的默认collation是latin1_swedish_ci,latin1有9种不同的collation:

  1. latin1_german1_ci
  2. latin1_swedish_ci
  3. latin1_danish_ci
  4. latin1_german2_ci
  5. latin1_bin
  6. latin1_general_ci
  7. latin1_general_cs
  8. latin1_spanish_ci

utf8的默认collation是utf8_general_ci ,还有utf8_unicode_ci、utf8_bin 以及针对不同语言的utf8 。utf8_unicode_ci是根据Unicode校对规则算法(UCA)执行的。utf8_unicode_ci的最主要的特色是支持扩展,即当把一个字母看作与其它字母组合相等时。例如,在德语中‘ß’等于‘ss’。

utf8_general_ci是一个遗留的校对规则,不支持扩展。它仅能够在字符之间进行逐个比较。但utf8_general_ci校对规则进行的比较速度很快,但是与使用utf8_unicode_ci相比正确性稍差。

例如,utf8_general_ci和utf8_unicode_ci 都认为Ä = A、Ö = O、Ü = U。差异在于utf8_general_ci 认为ß = s ,而utf8_unicode_ci 认为ß = ss。

utf8_unicode_ci 对德语和法语都工作得很好,所以不需要再单独建立对应的utf8校对规则。

utf8_swedish_ci,与其它语言相关的utf8的校对规则相似,来源于utf8_unicode_ci,使用额外的语言规则。例如,在瑞典语中,以下的关系式成立,它在德语和法语中不成立:Ü = Y < Ö

utf8_spanish_ci和utf8_spanish2_ci校对规则分别适用于现代和古典西班牙语。在两种校对规则中,ñ’(n-发音符)是‘n’和‘o’之间的间隔字母。另外,对于古典西班牙语,‘ch’是‘c’和d之间的间隔字母,并且‘ll’是‘l’和‘m’之间的间隔字母。

latin1_german1_ci和latin1_german2_ci校对规则基于DIN-1和DIN-2标准,这里DIN代表Deutsches Institut für Normung。DIN-1被叫做“字典校对规则”,DIN-2被叫做“电话簿校对规则”。

DIN-1中:Ä = a、Ö = O、Ü = U、ß = s

DIN-2中:Ä = aE、Ö = OE、Ü = UE、ß = ss

中文字符集gbk,只有gbk_chinese_ci和gbk_bin两种。实际上除了latin和unicode系列外,其它很多字符集大都以这两种形式出现。

参考资料:

Unicode Collation Algorithm(UCA) 及其 FAQ

ICU (International Components for Unicode)提供C/C++、Java的UCA 实现支持。

Wiki条目: Collation , 德语 , 法语 , 瑞典语 , 西班牙语 , 拉丁字母

Collation Charts

Mysql 相关文档

Java Api: java.text.Collatorjava.text.RuleBasedCollator