基于Android系统的联系人最大匹配检索算法设计与实现*

2013-03-13王超

自动化与信息工程 2013年6期

王超

（1.广州华商职业学院 2.中山大学）

0 引言

随着手机技术的迅速发展，搭载了开源手机操作系统Android的手机已经成为人们生活中密不可分的一部分。Android平台作为开发平台，由Linux内核、函数库、虚拟机、中间件、用户界面和应用软件组成。Android平台提供了四大组件：Activity、Service、Content Provider和Broadcast Receiver广播接收器[1]。其中Content Provider提供应用程序指定的数据集合给其它应用程序访问。

手机联系人资料存储在contacts2.db数据库中，作为记录通讯地址的集合，包含多项内容：姓名、电话、单位电话、移动电话、家庭电话、传真、电子邮件、QQ、MSN/个人主页、公司、生日、邮编、头像、skype、街道地址等[2]。用户使用手机搜索联系人时，期望包含全方位的检索结果。基于Android系统的联系人检索算法可分为利用系统库函数检索和非系统库函数检索两种实现方式，本文讨论非系统库函数的联系人检索算法。

研究手机联系人检索算法在Java环境下，使用编译软件eclipse和谷歌提供的Android SDK、ADT集成环境完成。

1 Android联系人存储介绍

自Android2.0（API Level 5）以后，联系人数据主要被安排存储在3个表中：Contacts，Raw Contacts和Data。这3个表对应的关系结构如图1所示。

图1 Android联系人存储表结构表

Contacts表是联系人信息的集合；Raw Contacts记录的是联系人来自某信息源的信息，例如本地输入，来自google等；Data则是具体的信息存储，包含联系电话、家庭电话、手机号码等。每一个 Data都存放一个具体的信息[3]。

Android联系人检索库函数是通过 Content Provider，即内容提供者完成。对外提供访问的途径是URI，主要包含以下7种：

1) 联系人URI：

2) 联系人电话URI:

3) 联系人邮箱URI：

4) 联系人组信息URI：

5) 联系人地址信息URI：

6) 联系人个人主页信息：

7) Data表URI:

2 Android联系人的库函数检索介绍

系统在实现联系人检索时，对外提供的主要检索方式如下：

针对联系人的查询：

//查找联系人名字

//查找联系人电话

//查找联系人邮箱

//查找联系人地址

3 Android联系人库函数检索原理分析

在contacts2.db数据库contacts表中有一个字段lookup，该字段提供快速检索的集合，将需要查询的lookup Key和lookup字段值进行数据库的查询操作，并将符合条件的结果在Cursor中返回。

lookup字段主要有3种：1) 提供汉字快速检索；2) 提供汉字首字母组合；3) 是电话号码数字的快速检索。如数据库语句：

由以上分析可以得出在进行检索时，匹配的过程实际为进行关键字的汉字检索、全拼检索以及拼音模糊检索。

3.1 汉字检索

汉字检索[4]比较快速，用户只需输入名字中的一个或多个字，即可检索出结果。但是汉字的输入比较麻烦，目前手机采用T9输入法，除了输入拼音以外，还需手动选择对应拼音的汉字，甚至还需翻页查找，这样极大地浪费了用户查找的时间。而且由于一些用户方言或者拼音不准，使用此检索方法无法满足其需求。

3.2 全拼检索

用户需要输入名字的拼音全拼进行全拼检索[5]以匹配到联系人。使用该方法检索速度比较快，且比汉字检索更简单，只需要输入拼音，而无需手动选择汉字。但是如果用户拼音不准，同样使用困难。

3.3 拼音模糊检索

拼音模糊检索[6]极大地方便了用户，减少了用户多余的手动选择和输入，同时将查找的任务给了计算机程序代码，节约了用户的时间。但同时也会增加计算时间的开销。

以上查找方法都有各自的局限：1) 如果用户没有清楚的记得联系人姓名或者姓名首字母时，进行全拼查找和首字母查找将无法查找到；2) 非连续的首字母检索和汉字首字母混合模糊检索是无法检索出结果的；3) 中国汉字有多音字，一些单个汉字对应多个拼音，尤其有一些常用汉字会作为姓名中的字出现，在进行检索时，需要做进一步的算法处理。

4 Android联系人非库函数检索

如何提高信息检索速度以便有效降低击键次数，提高查询效率，一直是开发人员研究的热点问题[7]，本文介绍的联系人最大匹配算法，即能有效降低用户击键次数，又能提供基于全拼、首字母查找以及介于这两者之间的混合部分拼音查找，同时可以进行多音字的检索，在时间开销和性能开销上都能满足Android平台的要求和限制，完全达到商用的标准。

4.1 Android平台限制

由于Android都运行于移动设备，这些设备的内存比较有限[8]，对于一个app来说，系统在内存分配上原则上不超过24M，程序占用内存也应在此限定范围内。同时移动设备的性能相较个人PC或者大型计算机，性能较差，要求的算法复杂度低。

4.2 算法运行环境

算法运行在Java jdk1.5，Android sdk2.0，adt10上，使用编译软件为 eclipse juno，运行环境为Android2.2。

4.3 检索原理

本算法检索原理是基于混合最大匹配，允许用户输入数字、汉字以及拼音，按照这些组合和T9键盘进行模糊最大匹配。

用户输入数字则进行电话号码匹配，同时按照T9键盘[9]转化数字为对应字母组合，通过正则表达式进行拼音检索，同时将检索结果集进行去重，最后显示给用户。

用户输入汉字则进行汉字匹配，检索联系人名字，通过Java的String.contains(String str)将符合检索条件的联系人显示给用户。

用户输入拼音则进行拼音分词，按照声母和韵母进行最大匹配。算法对声母记录联系人列表中的位置，实现快速定位的功能。

用拼音检索联系人时，首先要获知每个汉字的拼音。算法根据汉字拼音对照表查找对应汉字的拼音，生成对应联系人姓名的全拼表和首字母拼音表，然后按照输入的字母进行匹配，与全拼表和首字母拼音表匹配，如果匹配，则加入到结果集，否则查找下一条记录。

汉字拼音对照表既可以使用操作系统的微软全拼码表文件 winpy.mb，将其逆转成为码表源文件winpy.txt[10]。汉字拼音对照表又可使用Android平台上类HanZiToPinYin，使用该类时，需要增加常用汉字的多音字拼音。

使用数据库作为查询的来源，可以预先在数据库中添加辅助字段，比如全拼和首字母简写，这样在查询的时候直接使用查询语句即可。

4.4 算法实现原理

算法的匹配可以按照数据库方式实现，进行like操作：

查询语句如下：

也可以按照Java代码，String类的匹配方式进行：

4.5 算法流程

算法主要是通过字符串的String进行匹配，按照最大匹配进行检索，直到检索字符串长度为0。搜索字符串是指每次经过匹配后剩余的字符串，流程图如图2所示。

图2 最长匹配流程图

5 实验结果和分析

该算法运行在Android手机，硬件配置为联发科双核1.0 G处理器，512 MB内存，Android版本为4.1.2，按照图3所示进行测试。

图3横坐标代表联系人数目，纵坐标为时间开销，单位为秒，4条曲线分别代表：算法平均搜索时间、拼音检索花费时间、汉字检索花费时间以及首字母检索花费时间。

图3反映了本算法和其它几种算法的效率比较。

当联系人条目数为100条、200条、500条、600条、1000条时，本文算法平均检索时间为0.102秒、0.121秒、0.287秒、0.309秒、0.352秒、0.422秒，消耗时间都少于拼音检索、汉字检索以及首字母检索，说明本文算法性能比较高。

图3 算法性能比较图

实验结果表明：本算法处理性能比拼音检索、首字母检索更快。

以n代表用户输入的字符串长度，本文中算法在最优的情况下一次就可以查询到，也就是0(n)=1，这样的情况也就是用户直接输入全拼的时候，字符串刚好和拼音完全匹配。最差的情况下匹配的复杂度是0(n)=n,也就是用户输入的字符串刚好是要查找联系人的姓名首字母简写，这样，算法先从输入字符串长度n开始由后往前依次减掉最后一位字符，最终匹配到第一位，再从第一位往后，依次到所有字符串都匹配完成。因为算法对首字母做了字母索引映射表，所以可以快速检索。因此最差的情况下：

0(n)=n-α=n ；α为通过首字母索引表快速检索减少的匹配次数；

其余情况在这两者之间。而用户一般在查找（中文名）联系人时，通常输入的字符串长度不会超过5个，因此查找的次数为5，

0 ＜ 0(n) ＜ 5；在效率上满足Android的要求，而在使用内存上，既不需要产生其它的数据库，也不会增加系统的开销和修改系统数据库。