本栏目责任编辑:唐一东

人工智能及识别技术ComputerKnowledgeandTechnology电脑知识与技术第5卷第7期(2009年3月)一种适合Java环境的中文快速排序和模糊检索方法刘焕焕1,2,陆锋2,赵云山3(1.
中国矿业大学(北京)资源与安全工程学院,北京100083;2.
中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京100101;3.
北京邮电大学网络与交换技术国家重点实验室,北京100876)摘要:涉及中文字符串记录的数据库管理是Java开发中的常见问题.
由于Java语言对中文支持不足,导致中文字符串记录的排序不能很好地满足应用要求.
该文在与当前中文排序方法比较分析的基础上,提出了一种通用的排序方法,适用于Java环境下中文字符串和数字类型记录的排序过程,较好地解决了中文字符串数据集记录的排序问题,并且针对记录添加和检索时易出现的谐音拼写错误,提出了谐音检索方法,提高了检索过程的容错和纠错性能.
关键词:排序;中文字符串;Java环境;模糊检索中图分类号:TP311文献标识码:A文章编号:1009-3044(2009)07-1664-03AQuickSortandFuzzyRetrievingApproachforChineseTextinJavaEnvironmentLIUHuan-huan1,2,LUFeng2,ZHAOYun-shan3(1.
CollegeofResourcesandSafetyEngineering,ChinaUniversityofMiningandTechnology,Beijing100083,China;2.
StateKeyLabora-toryofResourcesandEnvironmentalInformationSystem,InstituteofGeographicSciencesandNaturalResourcesResearch,ChineseA-cademyofSciences,Beijing100101,China;3.
StateKeyLaboratoryofNetworkingandSwitchingTechnology,BeijingUniversityofPostsandTelecommunications,Beijing100876,China)Abstract:ItisacommonproblemfordatabasemanagementinaJavadevelopmentenvironmentwheninvolvingChinesetextrecords.
AsaresultoftheincapabilityindealingwithChinesetextforJava,thesortingofChinesetextrecordscannotfulfilltheapplicationrequire-ments.
AgeneralsortingapproachapplyingtosortofChinesetextanddigitalrecordsinJavaenvironmentispresentedbasedoncompara-tiveanalysisofcurrentChinesesortingmethods,whichcanbettersolvethesortingproblemofChinesetextdataset.
Thispaperputsfor-wardfuzzyretrievingmethodswhichcanstandhomophonicspellingerrorseasilyoccurringinaddingandretrieving,whichimprovesfaulttoleranceanderror-correctingperformanceinretrievalprocess.
Keywords:sorting;chinesetext;Javaenvironment;fuzzyretrieving1引言Java语言由于其"一次编写,跨平台应用"优势,正在渗入生活的方方面面,如智能手机、数字家电、电子商务等.

由于上述应用中广泛涉及各种数据库系统,对数据的合理组织及有效管理成为应用系统性能的关键指标.

而其中使用频率最高的数据库记录排序和检索是优化系统性能的主要任务之一.
Java语言开发环境本身提供了功能强大的排序方法,可以满足常见的系统功能要求;不过由于Java语言"天生"对中文的支持不足(如Web系统开发中易出现的乱码问题),及中文字符自身的复杂性(如编码种类繁多及大量多音字的存在),导致Java语言开发环境内置的排序方法不能满足中文信息系统的拼音排序功能,主要原因是内置的排序方法仅实现了宽松的拼音排序法,即只实现了常用汉字的排序[1].
汉字最早采用GB2312编码,收录了六千多个汉字,按拼音排序,连续编码,后来出现的GBK编码对GB2312进行了扩展,收录了两万多汉字,GB2312中的汉字编码原封不动搬到GBK中(在GBK编码[B0-D7]区中).
另外由于汉字的同音字及多音字问题,使得拼音排序更加复杂[2].
针对中文检索,Java语言开发环境虽然也提供了相应的功能,但由于拼音输入法在输入检索关键词时易出现同音或谐音错误,导致应用系统无法智能识别该关键词,使得系统功能大打折扣.
本文根据笔者参与开发的实时交通信息处理与融合系统,在与当前中文排序方法比较的基础上,提出了一种通用的排序方法,较好地解决了中文字符串排序问题,并且针对信息检索时易出现的谐音拼写错误,提出了谐音检索方法,提高了检索过程的容错和纠错性能.

2中文字符串记录的排序算法目前在Java开发环境中的记录排序方法需要为待排序元素实现Comparator接口,通过其中的compareTo函数得出排序结果,最终调用集合框架中Array或Collections的静态方法sort,就可以直接对集合排序.
程序员用不同的方式实现了Comparator接口,就可以用各自不同的方式排序[3].
对于排序结果要求不严格的数据库系统可以使用宽松排序方法,即调用Java中的java.
text.
Collator、java.
util.
Locale类进行实现.
前者可为自然语言文本构建搜索和排序例程,后者为用户量身定制语言环境敏感的操作信息,如根据用户的国家、地区或文化的风俗传统来格式化将显示的数值、百分比等信息.
具体实例如下:publicclassPinyinSimpleComparatorimplementsComparator{publicintcompare(Stringo1,Stringo2){returnCollator.
getInstance(Locale.
CHINESE).
compare(o1,o2);}}收稿日期:2009-02-15基金项目:国家863项目(2006AA12Z209,2007AA12Z241);国家自然科学基金项目(40871184);中国科学院知识创新工程重点方向性项目(KZCX2-YW-308)ISSN1009-3044ComputerKnowledgeandTechnology电脑知识与技术Vol.
5,No.
7,March2009,pp.
1664-1666E-mail:eduf@cccc.
net.
cnhttp://www.
dnzs.
net.
cnTel:+86-551-569096356909641664人工智能及识别技术本栏目责任编辑:唐一东在实现了此比较器后,可以使用集合类的sort(Listlist,newPinyinSimple-Comparator())方法,调用自行构造的比较器实现宽松的中文排序.
使用上述方法对"孙,孟,宋,尹,廖,张,徐,昆,曹,曾,怡"这几个汉字排序,结果为:"曹,昆,廖,孟,宋,孙,徐,尹,曾,张,怡".
"怡"字的排序出现错误;另外对同音字"怕,帕"排序后发现,该方法对同音字排序结果并不相等.
所以对于排序结果要求严格的系统,必须对此方法加以改进.
2.
1改进的中文排序算法在Java中字符是用Unicode码表示的,对于Unicode基本区域中的文字,用2个字节存储,用一个char表示,而辅助区域中的文字用4个字节存储,用两个char来表示.
一个文字的Unicode编码,在Java中统一用code-Point(代码点)这个概念来表示.
为了解决宽松拼音排序的不足,可以通过实现汉语拼音的函数来解决.
在此我们首先用Java中Character类中的isSupplementaryCodePoint方法判定某字符是否位于辅助区域中,再利用pinyin4j这一开源项目的成果,其中PinyinHelper类中的toHanyuPinyinStringArray()方法可以获取该字符的拼音[1].
实现原理如图1所示.
使用该方法可以较好地完成中文排序,唯一不足的是对同音字排序时不能智能获取准确的拼音.
2.
2排序过程作者将待排序信息按数据类型不同分别处理:若为数字,则首先将取得对象转化为数字类型,调用相应的数字排序函数,然后用冒泡算法进行排序;若为中文,则采用上述改进的中文排序方法.
具体实现原理如下:首先获取待排序内容:Objectobj1=dataModel.
getValueAt(index,sortColumn);Objectobj2=dataModel.
getValueAt(row.
index,sortColumn);若为数字类型,则调用Java已实现的比较方法得出比较结果:((Comparable)Integer.
valueOf(obj1.
toString())).
compareTo((Comparable)(Integer.
valueOf(obj2.
toString())));若为中文,我们就调用自己改写的拼音比较函数来对中文字符串进行比较:PinyinComparator.
compare(obj1.
toString(),obj2.
toString());3基于谐音的模糊检索上述中文排序方法可以准确完成中文字符串排序和检索过程.
但是如果数据库中存在拼写错误,数据库查询检索将出现问题.
为了解决此问题,本文提出了谐音检索方法.
3.
1谐音检索方法谐音检索方法具有检索谐音不规范书写的能力[4-6],其关键技术在于确定检索词的拼音是否与词库中的相同,通过判断两个词汇是否具有同样的拼音来推导两个词是否匹配.
若对比词汇之间具有相同的拼音,那么推断二者词汇成功匹配.
基于谐音的检索技术的首要任务是对所涉及的词汇进行拼音化改造,主要是将中文词库中词汇转换为词汇拼音形式进行存储,建立词汇拼音库,通过特定的数据结构同中文词库建立对应关系.
同时,将查询词与词库表精确检索后,匹配上查询词转换成拼音形式,与中文词库对应的拼音词库比较,将成功识别谐音词汇并以标准词汇作为返回,从而排除人工查询带来的谐音错误,使查询方法具有良好的模糊特征.
其中,词库的拼音化改造是基于谐音的字符串匹配技术的核心步骤.
作者采用SpellMap工具实现中文汉字到全拼拼音的转换.
本质上,SpellMap是一个预先设计好的linkedhashmap结构,结构中存储了中文拼音和ASCII码的对应关系.
而现有的技术可以很容易地提炼出中文字符的ASCII码,从而形成了"中文—ASCII码—中文拼音"三步转换的技术链.
最终,完成中文词汇的拼音化改造工作.
3.
2谐音检索数据结构与流程丰富的词库能保证检索的正确性,而合理的数据结构确保检索的运行效率.

为了更为有效地检索词库的信息,文中将词库中词汇的数据结构设计为多层树型模式.

如图2所示,A1表示词库词汇的中文,B1为对应A1的拼音.
此数据结构通过将Ai与Bi建立对应关系(i=1,2……n),为谐音检索返回正确的结果提供了很大帮助.

模糊检索的过程:检索词C,中文词汇Ai,拼音词汇Bi,Ai与Bi建立对应关系.
1)C与Ai比较,相同,则词库中文词汇Ai选中显示2)若不相同,将C转化成拼音D,将D与Bi进行比较3)相同,找到与Bi对应中文词汇Ai,将词库中文词汇Ai进行选中显示4)若不相同,将未知词汇C添加到数据库中4实验分析在上述技术研发的基础上,作者采用包含了4198条北京市路名与兴趣点的地址库作为实验对象,采用Oracle10g数据库管理系统完成数据管理工作.
4.
1排序方法验证改进的排序方法提高了数字检索的效率,使中文排序更满足我们的需求.

图1改进中文排序流程图图2词库存储数据结构刘焕焕等:一种适合Java环境的中文快速排序和模糊检索方法1665本栏目责任编辑:唐一东人工智能及识别技术ComputerKnowledgeandTechnology电脑知识与技术第5卷第7期(2009年3月)图3改进前道路名降序结果图4改进后道路名降序结果由上图可以看出改进后的排序算法是按照拼音排序的,更符合我们应用的需求.

4.
2谐音检索方法验证谐音检索方法提高了数据库检索信的容错性和鲁棒性.
例如,我们在地址库中查询"学院路"时,如错输为"学员路",则系统无法完成精确匹配,会给出提示,可检索到正确的"学院路",或在地址词库里新建"学员路"记录.

通过上述验证,作者开发的谐音检索方法在出现中文谐音拼写错误时,仍能够给出正确查询结果,从而较好地满足了模糊查询的需求.
5总结本文在综合比较各种排序方法的基础上,提出了适合Java开发环境的中文字符串数据集排序算法,且在排序效率方面得到了较好的提升;同时针对中文字符串数据集检索中可能出现的谐音拼写错误,提出了适合谐音匹配的模糊检索方法,提高了系统的容错纠错能力.
后续研究中将进一步完善系统对同音字、多音字的排序支持,加强检索词汇的容错性,提高计算机处理中文信息的智能化水平.
参考文献:[1]孙宏凯,王彦勋.
中文数据排序与快速检索方法研究[J].
微计算机信息,2007(3):256-257.

[2]胡彧,苏雪峰.
特定主题的相关概念挖掘研究与实现[J].
电脑开发与应用,2007,20(2).

[3]杨宪泽,谈文蓉,刘玉萍,等.
汉语同音字和多音字处理方法研究[J].
计算机与现代化,2006(2):88-90.

[4]陈传彬.
自然语言表达城市路网信息融合方法研究[D].
福州大学,2008.
[5]王冬,张运波,黄应红.
中文信息检索关键技术分析[J].
电脑知识与技术,2007(17).

[6]李梅,王庆林.
中文全文检索技术的研究及实现[J].
情报学报,2003,22(1):9-16.

刘焕焕(1983-),女,硕士,研究方向:自然语言处理.
陆锋(1970-),男,博士,研究员、博士生导师,研究方向:交通GIS理论与技术;赵云山(1983-),男,硕士,研究方向:基于模型驱动架构(MDA)的电信业务智能化.
(上接第1654页)学生分步进行设计.
这样降低了综合设计的门槛,使学生循序渐进,有步可循.
通过以上方法的开展,使学生都能根据自身的特点,主动积极的进行综合设计,不同层次的学生都能较好的发挥自己的才能,最大限度的开发学生的能力.

4充分利用网络,促进教学网络是一种新兴的媒体,利用网络内容丰富、方便快捷、共享性强的特点为可以更好的促进"C程序设计"的教学.
首先,在备课时,利用网络可以快速准确的搜集到丰富的参考资料.
其次,在实践教学时,开放局域网,可以把实践作业和同学们的实践作品随时在全班实现共享.
第三,申请班级公共邮箱,这样课上有未解决的问题或者同学们课下遇到问题可以随时发到邮箱,师生进行网络交流.
参考文献:[1]谭浩强.
C程序设计[M].
3版.
北京:清华大学出版社,2005.
[2]薛小锋.
C语言程序设计教学方法探析[J].
福建电脑,2004(1):87.
[3]何钦铭,颜晖.
"C程序设计基础及实验"国家精品课程的建设经验[J].
计算机教育,2008(19):28-31.