[转]Sqlite中文排序研究

@H_301_4@sqlite中文排序研究@H_403_16@

@H_403_16@

转载时请注明出处：http://blog.csdn.net/absurd@H_403_16@

@H_403_16@

sqlite是一个用C语言实现的小型sql数据库引擎。它体积小巧但功能强大，对硬件资源要求很低而且性能表现卓越，非常适合于嵌入式应用环境。最近发现sqlite并不支持中文(拼音/笔画)排序，而这个功能又是我们必需的，所以花了些时间去研究。我对sqlite的了解只能算是业余级，在研究的过程或许走了些弯路，或许已经有现存的算法可利用，不管怎么样，在研究过程中还是有不少收获，写出来和大家探讨一下。@H_403_16@

@H_403_16@

我们知道，计算机中的每一个字符都有一个内码。在默认情况下，计算机排序时，比较两个字符的大小就是比较字符内码的大小，这对于英文来说没有问题，因为英文字母的内码是按字母顺序递增的。对于中文来说，就比较麻烦了：首先，中文的排序方式有多种，比如按内码排序、按拼音排序和按笔画排序，要通过参数指定排序的方式，否则计算机就按内码排序了。其次，汉字的内码顺序即不同于拼音顺序，也不同于按笔画顺序。在GB2312编码中，汉字基本上按拼音排序（据说有例外，不太清楚）。在GBK中，它在GB2312基础上进行了扩充，兼容GB2312中的所有字符，所以不是按拼音排序了。在Unicode中，汉字的排列似乎更没有什么规律可言了。@H_403_16@

@H_403_16@

为了解决内码顺序与用户习惯顺序(如拼音顺序)的冲突，在glibc的locale数据里，要求提供排序方式(collate)的描述。我看了一下glibc-2.3.5提供的locale数据，在简体中文(zh_CN)的locale数据描述里，关于排序方式的描述如下：@H_403_16@

% ISO 14651 collation sequence@H_403_16@

LC_COLLATE@H_403_16@

copy "iso14651_t1"@H_403_16@

END LC_COLLATE@H_403_16@

@H_403_16@

也就是说，照抄iso14651_t1的排序方式。打开iso14651_t1文件看了一下，也没有发现关于中文的特殊处理，可以推断glibc默认的排序方式就是按unicode排序。@H_403_16@

@H_403_16@

所以不能指望glibc提供中文排序功能，如果sqlite支持了中文排序只能是做了特殊处理。浏览了一下sqlite的代码，这种希望似乎也不大。在网上也没有查到相关的资料和补丁，看来只能靠自己了。@H_403_16@

@H_403_16@

不过，在浏览sqlite代码时还是有些收获，至少知道了它比较数据记录的过程：@H_403_16@

1. sqlite3VdbeExec调用sqlite3BtreeInsert把记录插入到适当的位置。@H_403_16@

2. sqlite3BtreeInsert调用sqlite3BtreeMoveto找到要插入的位置。@H_403_16@

3. sqlite3BtreeMoveto调用sqlite3VdbeRecordCompare比较两条记录的大小。@H_403_16@

4. sqlite3VdbeRecordCompare调用sqlite3MemCompare比较字段的大小。@H_403_16@

5. sqlite3MemCompare调用binCollFunc去做真正的比较。@H_403_16@

6. binCollFunc是一个回调函数，由外层设置的。@H_403_16@

@H_403_16@

进一步研究，知道了binCollFunc的来源：@H_403_16@

1. struct CollSeq是一个用来比较的对象，它带有一个比较函数和相关上下文。@H_403_16@

2. 通过multiSelectCollSeq找到合适的CollSeq对象。@H_403_16@

3. multiSelectCollSeq调用sqlite3ExprCollSeq查找。@H_403_16@

4. multiSelectCollSeq调用sqlite3CheckCollSeq查找。@H_403_16@

5. 查找标准是SELECT或CREATE TABLE所带的COLLATE子句。@H_403_16@

6. 也就是说可以通过SELECT或CREATE TABLE的参数来决定选择哪个比较函数。@H_403_16@

@H_403_16@

基于上面这些认识，我们知道比较函数是可以指定的了。接下来的问题是，我们能否自定义比较函数，如何自定义，以及如何安装到sqlite里。很快发现sqlite已经提供了安装比较函数的接口:@H_403_16@

int sqlite3_create_collation16( @H_403_16@

sqlite3* db,@H_403_16@

const char *zName,@H_403_16@

int enc,@H_403_16@

void* pCtx,@H_403_16@

int(*xCompare)(void*,int,const void*,const void*) @H_403_16@

) @H_403_16@

@H_403_16@

int sqlite3_create_collation( @H_403_16@

sqlite3* db,const void*) @H_403_16@

) @H_403_16@

@H_403_16@

前者用来安装UTF-16的比较函数，后者用来安装UTF-8的比较函数。我们发现，在main.c里已经安装了一些内置的比较函数：@H_403_16@

sqlite3_create_collation(db,"BINARY",sqlITE_UTF8,binCollFunc); @H_403_16@

sqlite3_create_collation(db,sqlITE_UTF16,"NOCASE",nocaseCollatingFunc);@H_403_16@

@H_403_16@

好了，原理清楚了，我们要做的只是提供一个比较函数，并且安装进去就OK了。为了测试，我写一个按拼音排序的比较函数(按笔画排序类似):@H_403_16@

int pinyin_cmp( @H_403_16@

void *NotUsed,@H_403_16@

int nKey1,const void *pKey1,@H_403_16@

int nKey2,const void *pKey2) @H_403_16@

{ @H_403_16@

int n = nKey1 < nKey1 ? nKey1 : nKey2; @H_403_16@

@H_403_16@

return pinyin_strncmp(pKey1,pKey2,n + 1); @H_403_16@

}@H_403_16@

@H_403_16@

安装比较函数时要注意，因为我们实现的比较函数是针对UTF-16的，所以名字要用UTF-16编码。但是由于linux下默认的wchar_t是32位的，不能直接用L”pinyin”的方式把ANSI字符串转换成UTF-16字符串，只能按下列方式。@H_403_16@

unsigned short zName[] = {'p','i','n','y',0}; @H_403_16@

sqlite3_create_collation16(db,zName,16,pinyin_cmp);@H_403_16@

@H_403_16@

测试结果正常(红色部分为按拼音排序，蓝色部分为默认排序):@H_403_16@

sqlite> create table person(name text,age int);@H_403_16@

sqlite> insert into person values("张三",23);@H_403_16@

sqlite> insert into person values("张三丰",23);@H_403_16@

sqlite> insert into person values("李四",24);@H_403_16@

sqlite> insert into person values("李四叔",24);@H_403_16@

sqlite> insert into person values("王五",25);@H_403_16@

sqlite> insert into person values("王五妹",25);@H_403_16@

sqlite> insert into person values("赵七",26);@H_403_16@

sqlite> insert into person values("赵七姑",26);@H_403_16@

sqlite> @H_403_16@

sqlite> select * from person order by name collate pinyin; @H_403_16@

李四|24 @H_403_16@

李四叔|24 @H_403_16@

王五|25 @H_403_16@

王五妹|25 @H_403_16@

张三|23 @H_403_16@

张三丰|23 @H_403_16@

赵七|26 @H_403_16@

赵七姑|26@H_403_16@

sqlite> select * from person order by name; @H_403_16@

张三|23 @H_403_16@

张三丰|23 @H_403_16@

李四|24 @H_403_16@

李四叔|24 @H_403_16@

王五|25 @H_403_16@

王五妹|25 @H_403_16@

赵七|26 @H_403_16@

赵七姑|26@H_403_16@

@H_403_16@

总结：sqlite的架构设计非常优秀，接口定义得也比较合理，支持中文排序变得非常简单。@H_403_16@

@H_403_16@

(关于pinyin_strncmp的实现，将在下一篇文章中介绍)@H_403_16@

@H_403_16@

~~end~~@H_403_16@

@H_403_16@

from: http://blog.csdn.net/absurd/archive/2006/09/24/1271259.aspx@H_403_16@

@H_403_16@

附加：@H_403_16@

@H_403_16@

@H_301_4@[open source] 拼音排序函数库发布@H_403_16@

@H_403_16@

最近在做资源管理器的设计，SPEC要求中文文件名按拼音排序。于是花了点时间去研究关于拼音排序的问题，然后又花了两小时写了一个函数库。其实知道了原理，按拼音排序的实现很简单，放到这里供大家参考吧。@H_403_16@

@H_403_16@

% ISO 14651 collation sequence@H_403_16@

LC_COLLATE@H_403_16@

copy "iso14651_t1"@H_403_16@

END LC_COLLATE@H_403_16@

@H_403_16@

也就是说，照抄iso14651_t1的排序方式。打开iso14651_t1文件看了一下，也没有发现关于中文的特殊处理，可以推断glibc默认的排序方式就是按unicode排序。由此看来，glibc没有提供拼音排序功能，只能由我们自己去实现了。@H_403_16@

@H_403_16@

实现拼音排序其实很简单，我在另外一篇文章中介绍了获得汉字对应拼音的方法，我们可以先取出汉字的拼音然后再比较。这种方法会不会性能低下呢？实际上不会，看起来取拼音过程可能会有点慢，但是一次比较函数调用只需要一次取拼音函数调用，因为只当它们的内码不同时才调用取拼音的函数。@H_403_16@

@H_403_16@

如果仅仅是为了比较汉字的拼音顺序，其实我们可以用更简单的办法，而不必存储那些拼音数据。我们只要预先把所有汉字按拼音排序，汉字在排序后位置偏移量，就可以用来作为比较的基准值。@H_403_16@

@H_403_16@

如何找到所有汉字呢？如果你只需要GB2312中汉字，你可以按我的另外一篇文章里所说的方法去做。如果需要GBK/Unicode中的汉字，GBK和Unicode中的汉字是一一对应的，在Unicode中，汉字所在的区间为0x4e00 - 0x9FA5，所以一个循环就可以打印出所有的汉字。@H_403_16@

@H_403_16@

如何按拼音排序呢？很简单，有很多工具可以完成这一功能，像wps/word/pagemaker/excel。Word排序太慢，而且对行数也有限制，还是用excel吧。@H_403_16@

@H_403_16@

数据如何组织？很简单，建立一张unicode与排序偏移量的映射表就行了。考虑到汉字与非汉字之间的比较，我们需要把偏移量加上0x4e00。考虑到空间问题，0x4e00前面都不是汉字，我们的表只要0x9FA5 - 0x4e00 + 1大小就行了，所以表中的unicode要减去0x4e00。@H_403_16@

@H_403_16@

有兴趣的朋友可以到这里下载。@H_403_16@

@H_403_16@

(如果在程序中即要获取拼音，又要按拼音排序，还是建议用取拼音的方式来比较，那样两个功能的数据可以共享。)@H_403_16@

@H_403_16@

~~end~~@H_403_16@

@H_403_16@

from: http://blog.csdn.net/absurd/archive/2006/09/25/1282740.aspx@H_403_16@

原文链接：https://www.f2er.com/sqlite/203200.html

[转]Sqlite中文排序研究

猜你在找的Sqlite相关文章