大家都知道,排序算法是计算机学科最基础的知识之一,常见的排序算法有冒泡、快排等。这里讨论的文本排序不是一个排序算法,而是作为某个排序算法的底层依赖,常常在多语言环境下需要考虑,比如说中文的排序,日文的排序。
一个软件系统要做到全球化(globlization),应考虑以下几个方面:
一个系统要做到全球化,需要仔细考虑文本排序,因为文本排序可能会影响到系统的架构。之前就遇到过一个关于文本排序的问题,问题的原型是:
有一个电商平台,商家可以在平台上开店,在商家的后台产品管理界面,商家看到的产品列表默认以名字排序。现在有如下产品(名字):“abc”, “#abc”, “abc a”, “!abc”, “ abc”, “~abc”,但是看到的排列顺序却是:“abc”, “~abc”,“ abc”, “!abc”, “#abc”, “abc a”,可以看到a打头的两个名字“abc”,“abc a”被其他的以特殊符号打头的名字(“~abc”,“ abc”, “!abc”, “#abc”)分开了,直观上看起来不合理,照道理说两个a打头的名字应该挨在一起,这是为什么呢?
后来研究发现,这个问题是一个文本排序问题。
这个问题的原因是:电商平台底层用的是Posgres数据库,页面上看到的产品列表的排序是在后台数据库完成的。简单讲,这个排序动作可以翻译成如下sql语句:
SELECT name FROM unnest(ARRAY[
'abc', '#abc', 'abc a', '!abc', ' abc', '~abc'
]) name ORDER BY name
在数据库执行这条语句,得到的结果如下:
可以看到这个顺序和页面上显示的顺序是match的,说明问题就出在数据库这里。
那么数据库为什么会出现这样的排序结果呢?原因跟数据库的Locale Support相关,数据库Locale的设置会影响排序的方式,比如说locale设置成zh_CN,中文字符就会按照拼音排序;如果设置成zh_TW,中文字符就会按照笔画排序(其他字符则按照unicode的顺序)。
执行下面sql语句可以查看数据库支持哪些locale:
select * from pg_collation;
当执行sql语句做查询时,如果不指定任何collation key,就采用default的collation。关于default的collation是哪个,可以参考Postgres官方documentation - https://www.postgresql.org/docs/9.5/locale.html。
简单讲,如果创建db的时候没指定locale,就用默认的;指定了locale,就用指定的。
我们创建数据库的时候没有指定,所以用的是default的collation,default的会参考操作系统默认的locale设定,这里是en_US.utf8。在这种collation方式下,排序方式是:忽略打头的特殊字符,比如“~”,“!”,“ ”,拉丁字母按ASCII码顺序排序,其他字符按unicode顺序排序。如下:
排序方式也可以在执行sql语句的显示指定,如下显示指定分别按照简体中文和繁体中文排序:
繁体中文以笔划排序
简体中文以拼音排序
如果要解决上面的问题,我们也可以显示指定collation key为C,这种排序方式就是按照我们直观可理解的ASCII码顺序排序,a打头的两个名字挨着一起:
当然,对于一个电商平台(SaaS系统)来说,这种方案可以解决问题,但是会增加代码的复杂度,因为需要在每条sql语句后面根据商家的国家地区来显示指定一个collation key,如果这个平台面向的商家来自很多国家地区,这将会使代码变得非常复杂。针对这样的SaaS系统来说,我们可以考虑其他的一些解决方案:
1. 数据库的服务器直接落地在客户(商家)所在国家地区,这样可以使默认的locale和客户一致;
2. 当然,在平台setup的时候,不可能覆盖所有国家。针对一些小国家地区的客户(商家),可以使用统一的数据库服务器,但是setup独立的数据库instance,在setup instance的时候指定locale。
编程语言的支持
对于文本排序,各个开发语言也都有很好的支持。
Javascript
var items = ["一", "二", "三" , "四" , "五", "六", "七", " 七", "八", " 八", "a", "b", "1", "我"];
items.sort((a, b) => a.localeCompare(b, 'zh-TW', {ignorePunctuation: false, numeric: true}));
items.sort((a, b) => a.localeCompare(b, 'zh-CN-u-co-pinyin', {ignorePunctuation: false, numeric: true}));
执行上面JS代码,得到如下结果:
Java
Locale l = new Locale("zh", "CN");
//Locale l = new Locale("zh", "TW");
String[] str = {"一", "二", "三" , "四" , "五", "六", "七", "' '七", "八", "' '八", "a", "b", "1", "我"};
List<String> strList = Arrays.asList(str);
Collator coll = Collator.getInstance(l);
Collections.sort(strList, coll);
System.out.println(strList);
执行上面Java代码,得到如下结果:
从上面的排序结果可以看到,Java和Javascript排序的结果有点不一样,Java排序结果英文字符在中文字符前面,而Javascript排序结果英文字符在中文字符后面,这应该跟相应Library的实现有关,因为从Java官方文档可以看到,Java在处理打头的特殊字符时,会自动忽略掉,这个解释和上面最初的原型问题是吻合的,see
https://docs.oracle.com/javase/7/docs/api/java/text/RuleBasedCollator.html#compare(java.lang.String
同时可以看到javascript和Postgres的排序结果时吻合的,两者都是把英文字符在中文字符后面(至少从采用的排序locale来说)。
延伸
文章开头提到一些基础排序算法,有兴趣的同学可以网上搜索再回顾一下。See https://www.runoob.com/w3cnote/sort-algorithm-summary.html。
另外下面列出一些跟排序相关的应用场景:
References