基于n-gram中英⽂字符串分割算法实现
本栏⽬责任编辑:代影数据库与信息管理ComputerKnowledgeandTechnology电脑知识与技术第8卷第23期(2012年8⽉)基
于n-gram中英⽂字符串分割算法实现
何晓明,洪亲,蔡坚勇,林鸿
(福建师范⼤学仓⼭校区光电与信息⼯程学院,福建福州350007)
摘要:相似字符串的模糊查询是信息检索的重要组成部分,⼀直是⼈们研究的热点。⽬前基于关键词的查询技术都是前缀匹配,
⽆法查找到与搜索字符串相似的结果。该⽂提出⼀种基于n-gram的中英⽂字符串分割技术的算法,该技术主要是对字符串进⾏
中英⽂识别,然后基于n-gram按照指定长度进⾏分割,该技术是实现基于关键词的模糊查询技术的基础。该技术在数据清洗
以及学位论⽂TMLC系统和垃圾邮件过滤等⽅⾯也有重要的应⽤前景。
关键词:模糊查询;n-gram;字符串分割;编辑距离;数据挖掘
中图分类号:TP391⽂献标识码:A⽂章编号:1009-3044(2012)23-5530-04
ImplementationofAlgorithmBadonn-gramChine-EnglishStringSegmentation
HEXiao-ming,HONGQin,CAIJian-yong,LINHong
(CollegeofPhotonicandElectronicEngineeringofFujianNormalUniversityCangshanCampus,Fuzhou350007,China)
Abstract:Similarstringoffuzzyqueryisanimportantpartoftheinformationretrieval,
keywordarchtechnologyistheprefixmatching,perprentsan-
grambadintheChi?ne-Englishstringgmentationalgorithm,thetechniqueismainlytostringrecognitionbadonn-
graminChine-English,theninac?cordancewiththespecifiedlengthofgmentation,thetechniqueisrealizedbadon
h?nologyindatacleaninganddisrtationsTMLCsystemandspam
filteringhasimportantapplicationprospect.
Keywords:fuzzyquery;n-gram;stringgmentation;editdistance;datamining
⾃从改⾰开放以来,中国与世界各国的联系⼀步⼀步地加强。这种不断加强的联系表现在信息的表达形式上是凸显的。在⽇常
⽣活查找信息时,我们很容易看到⼀些中英⽂混合使⽤的表达⽅式。⽐如:中国各省⼈均GDP,windows操作系统,3G⼿
机,3D电影,做CT,ICU病房等。⾯对这样⼀个新形势的信息爆炸时代,如何从互联⽹的海量信息中快速准确地找到我们
所需的信息成为⼀个难题[1]。
在信息爆炸时代⾥,搜索引擎已经成为千千万万⽹民上⽹的必备⼯具。但是随着信息量的不断增长,⼈们在在进⾏查询的时
候,有可能输⼊错误的信息(⽐如错误的字母,错误的数字,错误的同⾳汉字)。在这些⼀种情况下,⽤户可能就⽆法得到想要
的查询结果。尽管⽬前已经有些搜索引擎中加⼊了“您是否要找***”等类似的功能[2],但这依然⽆法快速准确的满⾜⽤户的查询
要求。因此,如何从海量的中英⽂数据中查找出与查询字符串相类似的查询结果,是该⽂努⼒研究的⽅向。⽬前,已经有⼈提出
了基
于n-gram的字符串分割的算法实现[3]。该算法只针对英⽂字符串,能解决在英⽂信息检索中基于关键词的查询技术前缀精确
匹配
问题[4],也就是检索结果是“错误的输⼊,错误的输出”,还能解决⽤户因记忆模糊或误输⼊单词中的个别字母,甚⾄在数据库中可能
存在某些不正确的数据即“脏数据”的这些情况下可能⽆法得到⽤户所期待的查询结果[5]。已有的算法针对的是英⽂数据,对中
英⽂这样的数据束⼿⽆策。为此,该⽂提出⼀种改进的解决⽅法,⾸先对关键词进⾏中英⽂识别,然后根据指定长度对字符串进
⾏分割。综上所述,该⽂对基于关键词的传统查询⽅法和基于n-gram的字符串分割的算法进⾏了分析,提出了基于n-gram的
中英⽂字符串分割的算法。
1基于关键词的查询
1.1传统的查询⽅法
随着⽹络通信的快速发展,信息爆炸已经成为⼀个不可避免的趋势。当⼈们⾯对如此巨⼤的信息量时如何从互联⽹的海量信息
中快速准确地找到我们所需的信息成为⼀个难题。此时,搜索引擎已经成为千千万万⽹民上⽹的必备⼯具。互联⽹上已有的搜
索引擎可分为两种:⽬录式搜索引擎和基于关键词的搜索引擎,后者处于主流地位[6]。基于关键词查询⼀般都是精确匹配,
其不⾜收稿⽇期:2012-07-12
基⾦项⽬:福建省⾃然科学基⾦项⽬(2010J01324)
作者简介:何晓明(1983-),男,福建泉州⼈,硕⼠,研究⽅向为数据库;(通讯作者)洪亲(1964-),⼥,⾼⼯,研究⽅向为
数据库,电⼦邮
箱为hongqin@/doc/;蔡坚勇(1962-),男,副教授,研究⽅向为光电
信息处理与⽹络通信;林鸿(1987-),男,硕⼠,研究
⽅向为嵌⼊式数据库。
E-mail:jslt@/doc/
/doc/l:+86-551-569ISSN1009-3044Computer
KnowledgeandTechnology电脑知识与技术Vol.8,No.23,August2012.5530
数据库与信息管理本栏⽬责任编辑:代影ComputerKnowledgeandTechnology电脑知识与技术第8卷第23期(2012年8⽉)之
处是:当检索者因为记忆错误或操作错误⽽输⼊错误查找信息,甚⾄因为数据库本来已存有错误的信息,⽽⽆法找到想要的信
息。为此该⽂对原有算法进⾏了改进,提出了基于n-gram的中英⽂字符串分割的算法实现,可对中英⽂信息实现基于关键词
的模糊搜索。
1.2基于n-gram的字符串分割技术的查询⽅法
该查询⽅法可以避免基于关键词查询技术的完全匹配的问题。当⽤户在操作失误或记忆不清时输⼊有误的查询信息时,利⽤基
于n-gram的中英⽂字符串分割技术的查询⽅法,⽤户将可以找到⾃⼰需要的信息。现将显⽰基于关键词查询的主要流程图
(如
图1)[7]和基于n-gram的字符串分割技术查询的主要流程图(如图2)
。
图1
传统基于关键词查询的主要流程图
图2基于n-gram的字符串分割技术查询的主要流程图
其中,分割后的字符串可通过编辑距离[8],余弦相似度[9],Jaccard系数[10]来计算字符串的相似程度,进⾏数据清洗实现模
糊搜素。现在以基于编辑距离的查询技术举例。先定义编辑距离,将⼦串r1转换成r2所需要的字符编辑操作(删除、插⼊、替
换)的次数定义为r1和r2之间的编辑距离,写作ED(r1,r2)。
⽐如当我们输⼊查询⼦串“做CT”且设定检索出的结果与输⼊查询⼦串允许⼀个字符不同(即编辑距离ED=1)时,那么我们可能得
到的结果是“*做CT”、“做*CT”、“做C*T”、“做CT*”、“做*T”、“做C*”,其中*表⽰可以是空或任意⼀个英⽂字符。我们还可以假
设编辑距离ED=2,那么我们可能得到的结果是“做**”、“**CT”、“做C**”等结果,其中*表⽰可以是空或任意⼀个英⽂字符,两
个连续*才可以表⽰⼀个汉字。这样的话,即使⽤户在输⼊⼀个错误的查询汉字或英⽂,或者输⼊两个错误的英⽂查询⼦串,或者
存储数据库中存在的某种程度有错误的记录,也都可以作为查询结果返回给⽤户,⽽这些记录很有可能就是⽤户所需要的结果。
因此,这种新的查询技术应⽤在中英⽂混合表达的信息中,将帮助⼈们更加快速准确找到他们所需的结果。⽽要实现上⾯所述
的这种中英⽂模糊查询,⾸先将整个数据集进⾏字符串分割,创建倒排索引[11],然后再对⽤户输⼊的查询字符串进⾏字符串分割,
最后把分割后的⼦串与倒排索引中的字符串⽚段进⾏模糊匹配[12],将候选结果与输⼊字符串按照编辑距离进⾏匹配后得到最后
结果。可见,中英⽂字符串的分割技术是中英⽂信息实现基于关键词的模糊搜索的基础。
2基于n-gram的中英⽂字符串分割技术
2.1n-gramn-gram[13]的定义:Z是⼀个字符串。|Z|表⽰Z的长度,Z[i]是Z中第i个字母/汉字(i从1开始),Z[i,j]是Z中从第i个到第j
个字母/汉字,n是⼀个整数。A(Z,n)表⽰字符串Z中所有的n-gram的集合,如Z=windows操作系统,n=4,则A(Z,n)={(1,wind),
(2,indo),(3,ndow),(4,dows),(5,ows操),(6,ws操作),(7,s操作系),(8,操作系统)}。在本算法中,字符串中的数字和空格也将分割,
⽽中⽂标点符号将剔除处理,不考虑其作为分割的字符。
2.2算法的实现
该算法根据指定的长度和n-gram的规则进⾏字符串分割,其流程图如图3所⽰。
该算法的主要函数如下:
(1)isAChinaFont(参量cn)
这个函数是⽤来识别输⼊的字符是不是中⽂字符,cn表⽰输⼊的字符。
(2)StringLen_Function(参量cPtr)
这个函数是先调⽤函数(1)对字符串中的字符进⾏识别,后统计字符串的字符个数,cPtr表⽰需要分割字符串。
(3)FormatNum_Function(参量cPtr,参量iSegmentationLen)
这个函数是先调⽤函数(2)求得源⽂件中⼀⾏字符串的字符个数,后根据分割长度算出该⾏字符串能分割成⼏个字符串⽚
段。cPtr表⽰需要分割字符串,iSegmentationLen表⽰分割长度。
(4)GetSegmentationString_Function(参量cPtr,参量iSegmentationLen,参量iFormatNum)
这个函数利⽤函数(1)(2)从⼀⾏字符串中取出我们分割的字符串。cPtr表⽰需要分割的字符串,iSegmentationLen表⽰
分割长度,iFormatNum表⽰需要分割第⼏个字符。
(5)WriteID_Function(参量fp,参量cPtr,参量iLineNum)
这个函数作⽤是如果从⽬标⽂件查到有⼀段字符串符合我们分割之后的字符串,我们将ID写⼊到这个字符串中。fp表⽰⽬标
⽂件,cPtr表⽰原来的字符串+插⼊ID=现在这个字符串,iLineNum表⽰要修改第⼏⾏。
(6)ChechInrt_Function(参量cPtr,参量iSegmentationLen,参量id)
这个函数是⽤来判断是否可以插⼊ID,因为有的分割字符串的ID已经存在于⽬标⽂件中,我们就不需要再插⼊ID。cPtr表⽰
分割好的字符串,iSegmentationLen表⽰分割长度,id表⽰⾏号。
5531
本栏⽬责任编辑:代影数据库与信息管理ComputerKnowledgeandTechnology电脑知识与技术第8卷第23期(2012年8⽉)
(7)Search_Function(参量Dest_fp,参量cPtr,参量iSegmentationLen,参量id)
这个函数是利⽤函数(1)(5)(6)查找分割的字符⽚段在不同⾏是否有重复,如不重复则写⼊到输出⽂件;如果在不同⾏
重复则在该⾏的⽂本后加上当前的⾏号输出;如果在同⾏重复则不改变原先的输出。Dest_fp表⽰⽬标⽂件,cPtr表⽰分割完
成的字符串,iSegmentation表⽰分割长度,id表⽰⾏号。以下是本算法的实现过程:If源⽂件存在打开⽬标⽂件,没有则新
建⼀个
获取分割长度
识别字符串中的字符,按照指定长度分割
取出⼀⾏字符串中分割的字符串⽚段,并写⼊ID存⼊⽬标⽂件(重复字符串⽚段只保存⼀次)
利⽤Search_Function()函数El退出程序2.3实验结果与分析
本实验在运⾏环境为Intel(R)Core(TM)*********************.66GHZ,1.50G内存的WindowsXP系统通过对包含不
同记录数的⽂该⽂件,设定不同的分割长度进⾏分割,程序运⾏时间⽐较如图4
所⽰:
图4
字符串分割时间
图3中英⽂字符串分割算法流程图
5532
本栏⽬责任编辑:代影ComputerKnowledgeandTechnology电脑知识与技术
第8卷第23期(2012年8⽉)
说明:横轴1,2,3分别表⽰⽂该⽂件中的记录数为10,25,50。
本算法的时间复杂度为(n/2),其中n表⽰⽂件中的记录数。该算法分割时间与记录数成线性增长,有较理想的效率。
3结论
随着信息的爆炸式增长,基于关键词搜索已经不能满⾜⼈们的需求,对模糊搜索的需求越来越迫切。该⽂提出了基于n-gram
的中英⽂字符串分割算法,不仅仅能满⾜英⽂的字符串分割,还能满⾜中⽂、中英⽂,以及混有数字的字符串分割,是实现模
糊搜索的⼀项重要技术。该技术的实现除了在模糊搜索有重要的应⽤,还在学位论⽂TMLC系统[14]和垃圾邮件过滤[15]也有重
要的应⽤前景。
参考⽂献:
[1]周景.浅谈互联⽹信息检索[J].信息与电脑:理论版,2011(12).
[2]刘竟.近⼗年我国搜索引擎研究的可视化分析[J].图书情报研究,2011(4).
[3]李⽂.基于n-gram的字符串分割技术的算法实现[J].计算机与现代化,2010(9).
[4]quesforautomaticallycorrectingwordsintext[J]..,1992,24(4):377-439.
[5]JiShengyue,LiGuoliang,LiChen,entinteractivefuzzykeywordarch[C].InternationalWorldWideWeb
Conference,2009:371-380.
[6]BehmAlexander,JiShengyue,LiChen,-constrainedgram-badindexingforefficientapproximatestring
arch[C].ICDE,2009:604-615.
[7]沈⽂婷.数据库关键字查询清理技术研究[J].电脑知识与技术,2011(34).
[8]LiC,LuJ,entmergingandfilteringalgorithmsforapproximatestringarches[C].ICDE,2008:257-266.
[9]WangJ,LiG,-join:Anefficientmethodforfuzzytokenmatchingbadstringsimilarityjoin[C].ICDE,2011:458-
469.
[10]潘磊.基于权重的Jaccard相似度度量的实体识别⽅法[J].北京交通⼤学学报,2009(6).
[11]JiannanWang,GuoliangLi,JianhuaFeng:Trie-Join:EfficientTrie-badStringSimilarityJoinswithEdit-Distance
Constraints.[J].PVLDB2010PVLDB3(1):1219-1230.
[12]ChaudhuriS,GantiV,tiveoperatorforsimilarityjoinsindatacleaning[C].ICDE,2006.
[13]WagnerRA,ing2to2stringcorrectionproblem[J].ACM,1974,21(1):168-173.
[14]张旻浩.国内外学术不端⽂献检测系统平台的⽐较研究[J].中国科技期刊研究,2011(4).
[15]常凯.基于TF*IDF垃圾邮件过滤改进算法的研究[J].电脑知识与技术,2010(25).
5533
数据库与信息管理
基于n-gram中英⽂字符串分割算法实现
作者:何晓明,洪亲,蔡坚勇,林鸿
作者单位:福建师范⼤学仓⼭校区光电与信息⼯程学院,福建福州350007
刊名:
电脑知识与技术
英⽂刊名:ComputerKnowledgeandTechnology
年,卷(期):2012(23)
本⽂链接:/doc//Periodical_
本文发布于:2023-01-04 01:58:29,感谢您对本站的认可!
本文链接:http://www.wtabcd.cn/fanwen/fan/90/87913.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
留言与评论(共有 0 条评论) |