Sqlite中文排序研究

Sqlite中文排序研究,第1张

概述Sqlite是一个用C语言实现的小型SQL数据库引擎。它体积小巧但功能强大,对硬件资源要求很低而且性能表现卓越,非常适合于嵌入式应用环境。最近发现sqlite并不支持中文(拼音/笔画)排序,而这个功能又是我们必需的,所以花了些时间去研究。我对Sqlite的了解只能算是业余级,在研究的过程或许走了些弯路,或许已经有现存的算法可利用,不管怎么样,在研究过程中还是有不少收获,写出来和大家探讨一下。    sqlite是一个用C语言实现的小型sql数据库引擎。它体积小巧但功能强大,对硬件资源要求很低而且性能表现卓越,非常适合于嵌入式应用环境。最近发现sqlite并不支持中文(拼音/笔画)排序,而这个功能又是我们必需的,所以花了些时间去研究。我对sqlite的了解只能算是业余级,在研究的过程或许走了些弯路,或许已经有现存的算法可利用,不管怎么样,在研究过程中还是有不少收获,写出来和大家探讨一下。 我们知道,计算机中的每一个字符都有一个内码。在默认情况下,计算机排序时,比较两个字符的大小就是比较字符内码的大小,这对于英文来说没有问题,因为英文字母的内码是按字母顺序递增的。对于中文来说,就比较麻烦了:首先,中文的排序方式有多种,比如按内码排序、按拼音排序和按笔画排序,要通过参数指定排序的方式,否则计算机就按内码排序了。其次,汉字的内码顺序即不同于拼音顺序,也不同于按笔画顺序。在GB2312编码中,汉字基本上按拼音排序(据说有例外,不太清楚)。在GBK中,它在GB2312基础上进行了扩充,兼容GB2312中的所有字符,所以不是按拼音排序了。在Unicode中,汉字的排列似乎更没有什么规律可言了。 为了解决内码顺序与用户习惯顺序(如拼音顺序)的冲突,在glibc的locale数据里,要求提供排序方式(collate)的描述。我看了一下glibc-2.3.5提供的locale数据,在简体中文(zh_CN)的locale数据描述里,关于排序方式的描述如下: % ISO 14651 collation sequence LC_ColLATE copy "iso14651_t1" END LC_ColLATE 也就是说,照抄iso14651_t1的排序方式。打开iso14651_t1文件看了一下,也没有发现关于中文的特殊处理,可以推断glibc默认的排序方式就是按unicode排序。 所以不能指望glibc提供中文排序功能,如果sqlite支持了中文排序只能是做了特殊处理。浏览了一下sqlite的代码,这种希望似乎也不大。在网上也没有查到相关的资料和补丁,看来只能靠自己了。 不过,在浏览sqlite代码时还是有些收获,至少知道了它比较数据记录的过程: 1. sqlite3VdbeExec调用sqlite3BtreeInsert把记录插入到适当的位置。 2. sqlite3BtreeInsert调用sqlite3BtreeMoveto找到要插入的位置。 3. sqlite3BtreeMoveto调用sqlite3VdbeRecordCompare比较两条记录的大小。 4. sqlite3VdbeRecordCompare调用sqlite3MemCompare比较字段的大小。 5. sqlite3MemCompare调用binCollFunc去做真正的比较。 6. binCollFunc是一个回调函数,由外层设置的。 进一步研究,知道了binCollFunc的来源: 1. struct CollSeq是一个用来比较的对象,它带有一个比较函数和相关上下文。 2. 通过multiSelectCollSeq找到合适的CollSeq对象。 3. multiSelectCollSeq调用sqlite3ExprCollSeq查找。 4. multiSelectCollSeq调用sqlite3CheckCollSeq查找。 5. 查找标准是SELECT或CREATE table所带的ColLATE子句。 6. 也就是说可以通过SELECT或CREATE table的参数来决定选择哪个比较函数。 基于上面这些认识,我们知道比较函数是可以指定的了。接下来的问题是,我们能否自定义比较函数,如何自定义,以及如何安装到sqlite里。很快发现sqlite已经提供了安装比较函数的接口:

intsqlite3_create_collation16( sqlite3* db, constchar *zname, intenc, voID* pCtx, int(*xCompare)(voID*,int,constvoID*,constvoID*) ) int sqlite3_create_collation( sqlite3* db,constvoID*) )
前者用来安装UTF-16的比较函数,后者用来安装UTF-8的比较函数。我们发现,在main.c里已经安装了一些内置的比较函数:

sqlite3_create_collation(db,"BINARY",sqlITE_UTF8,binCollFunc); sqlite3_create_collation(db,sqlITE_UTF16,"NOCASE",nocaseCollatingFunc);
好了,原理清楚了,我们要做的只是提供一个比较函数,并且安装进去就OK了。为了测试,我写一个按拼音排序的比较函数(按笔画排序类似):

intpinyin_cmp( voID *NotUsed, intnKey1,constvoID *pKey1, intnKey2,constvoID *pKey2) { intn = nKey1 < nKey1 ? nKey1 : nKey2; return pinyin_strncmp(pKey1,pKey2,n + 1); }
安装比较函数时要注意,因为我们实现的比较函数是针对UTF-16的,所以名字要用UTF-16编码。但是由于linux下默认的wchar_t是32位的,不能直接用L”pinyin”的方式把ANSI字符串转换成UTF-16字符串,只能按下列方式。

unsignedshortzname[] = {'p','i','n','y',0}; sqlite3_create_collation16(db,zname,16,pinyin_cmp);
测试结果正常(红色部分为按拼音排序,蓝色部分为默认排序):

sqlite> create table person(name text,age int); sqlite> insert into person values("张三",23); sqlite> insert into person values("张三丰",23); sqlite> insert into person values("李四",24); sqlite> insert into person values("李四叔",24); sqlite> insert into person values("王五",25); sqlite> insert into person values("王五妹",25); sqlite> insert into person values("赵七",26); sqlite> insert into person values("赵七姑",26); sqlite> sqlite> select * from person order by name collate pinyin; 李四 |24 李四叔 |24 王五 |25 王五妹 |25 张三 |23 张三丰 |23 赵七 |26 赵七姑 |26 sqlite> select * from person order by name; 张三 |23 张三丰 |23 李四 |24 李四叔 |24 王五 |25 王五妹 |25 赵七 |26 赵七姑 |26
总结:sqlite的架构设计非常优秀,接口定义得也比较合理,支持中文排序变得非常简单。

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

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

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

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

% ISO 14651 collation sequence

LC_ColLATE

copy "iso14651_t1"

END LC_ColLATE

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

实现拼音排序其实很简单,我们可以先取出汉字的拼音然后再比较。这种方法会不会性能低下呢?实际上不会,看起来取拼音过程可能会有点慢,但是一次比较函数调用只需要一次取拼音函数调用,因为只当它们的内码不同时才调用取拼音的函数。

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

如何找到所有汉字呢?如果需要GBK/Unicode中的汉字,GBKUnicode中的汉字是一一对应的,在Unicode中,汉字所在的区间为0x4e00 - 0x9FA5,所以一个循环就可以打印出所有的汉字。

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

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

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

总结

以上是内存溢出为你收集整理的Sqlite中文排序研究全部内容,希望文章能够帮你解决Sqlite中文排序研究所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/sjk/1183468.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-02
下一篇 2022-06-02

发表评论

登录后才能评论

评论列表(0条)

保存