基于拼音索引的中文模糊匹配算法
别妄想泡我
960次浏览
2020年07月29日 08:53
最佳经验
本文由作者推荐
女为悦己者容是什么意思-以狸饵鼠
音的错别字。模糊检索根据用户输入的模糊特征来检索匹配内容,可处理精确的关键词匹配所无法解决的这些问题[4]。在英文检索系统中,通常对用户输入的单词进行拼写纠错,就能解决大多数问题[5]。系统先搜索单词表,找出所有与查询串中单词的编辑距离(editdistance)在一定限度之内的所有词汇,再根据这些词汇来执行精确检索,即可在一定程度上实现模糊检索[4]。所以,英文模糊检索的主要研究集中在快速
简捷的字符串的模糊匹配算法方面[6-7]。考虑到查询串的整体性,文[8]提出了块索引的方法,通过二步的模糊匹配过程,找到与查询串整体编辑距离在一定限度之内的串的位置。汉语是典型的非字母语言,把任意两个汉字的差别都算成同一个值不够精确。绝大多数汉字都是表意单元,词语的搭配灵活多样,难以建立完整的词表用于纠错。所以汉语的模糊检索无法照搬英文中的方法,目前的研究主要集中在快速的汉字串模糊匹配算法方面[9-10]。其中,文[9]的研究工作改善了模糊匹配的时空复杂度,在实际系统中算法的时间复杂度可以达到子线性,在实际的实验中也取得了很好的效果。然而,遍历整个文本集来寻找相似串的出现位置,虽然可以比较准确地完成模糊检索任务,但随着数据集规模的进一步增长,时间开销依然难以接受。本文提出一种基于汉语拼音的模糊检索方法。与前述思路不同,通过扩展原始的查询串,将模糊检索任务转化为若干精确匹配的检索任务,从而大大降低算法复杂度。1汉字串相似度度量参考英文基于字母编辑距离的度量方式,本文提出3种汉字串相似度的度量方式:基于汉字的编辑距离、基于拼音的编辑距离,以及基于拼音改良的编辑距离。1.1基于汉字的编辑距离将单个汉字作为编辑距离中的距离度量单位,即:两个汉字串之间的距离,等于使它们完全一样所需的最少替换、插入或者删除的汉字个数。1.2基于拼音的编辑距离由于汉语拼音输入法的广泛使用,大部分用户的输入错误都表现为同音字或者近音字的替换误用,对Sogou实验室所提供的用户日志的分析结果也证实了这一点。基于此,本文提出了基于拼音的编辑距离来衡量汉字串的相似度。如果把拼音串简单地看作广义的英文字母串,则替换、插入或者删除一个字母后,所得结果不一定是合法的拼音串。因此应从音节的角度来分析拼音串的差别。对于一个单独的音节来说,它与另外一个音节的差异总可以分解为以下三种变化:声母变化、韵母变化和声调变化。声母、韵母和声调的可能取值都是有限的,可以枚举定义从一种取值变为另一种取值的编辑距离。所以,对于一个现有的音节,容易找到所有与它
编辑距离为n的音节。例如,要找到所有与它编辑距离是2的音节,那么变化可能是声母改变1个距离单位,韵母改变1个距离单位,声调改变0个距离单位;或者声母改变2个距离单位,韵母和声调没有发生改变。这只是一个排列组合的问题。如果给所有音节编号,将音节整体看作一个特殊的单字,那么基于拼音的编辑距离可认为是基于汉字的编辑距离的细化,即不同的汉字之间根据拼音的近似程度有不同的距离,而不是笼统地将任意两个汉字的距离都计为1。1.3基于拼音改良的编辑距离根据前述基于拼音的编辑距离定义,音节ue000li3ue000和ue000ni3ue000的编辑距离是1,ue000li3ue000和ue000pi3ue000的编辑距离也是1。但是这2组音节的差异从发音机理角度来看,ue000li3ue000与ue000ni3ue000更加近似。类似的例子如:音节ue000lin3ue000与ue000ling3ue000的差异较小,而ue000lin3ue000和ue000lan3ue000的差异较大。基于以上考虑,提出改良的编辑距离计算方式如下。1)发音相似(容易发生替换错误)的声母或韵母之间差异小于1。例如,ue000lue000和ue000nue000、ue000zue000和ue000zhue000、ue000cue000和ue000chue000等声母对,ue000inue000和ue000ingue000、ue000enue000和ue000engue000等韵母对,对音节编辑距离的贡献小于1(本文实验中赋予0.5的替换代价),这样的声母和韵母对一共是9对。对于其余的声母或者韵母对的替换代价的计算,则依然采用方法二中的使用字符编辑距离的计算方法。2)若同一音节的声母和韵母同时发生改变,则在计算编辑距离时给予一个正的惩罚值(本文实验中取值为2)。根据这一计算方式,对于音节串A=I1I2I3…In(其中Ii,i=1,2,…,n代表一个音节),若I2在声母和韵母上同时发生差异为1的变化得到新的音节串B=I1I′2I3…In,I1和I3各发生一个声母或韵母的差异为1的变化得到新的音节串C=I′1I2I′3…In,则C与A之间的编辑距离为2,小于B与A之间的编辑距离4。3)音调变化导致的差异小于1。由于音调错误比较常见和普遍,而且广泛使用的各种拼音输入法都不要求用户输入音调,所以可认为音调差异小于一般声母和韵母之间的差异,因而,按照发音相似的韵母和声母对一样的处理方式,这种差异在本文实验中赋予0.5的替换代价。在本文实验中,由于将所有小于1的差异都赋9231曹犟,等:基于拼音索引的中文模糊匹配算法
值为0.5,因此将所有的差异都乘以2之后,可以得到结果为整数的编辑距离,而这并不影响不同串之间相似度大小的比较。2索引与查询扩展依据具体的距离度量方式,可以扩展原始的查询串,将模糊匹配转化成多个相关的精确匹配,实现检索任务,步骤是:首先对查询串进行编辑距离由小到大的扩展,然后对扩展出的查询串进行精确匹配,精确匹配的结果在去重之后再按照查询串的编辑距离由小到大进行排序,最后
将排序的检索结果返回给用户。2.1建立索引在本文提出的模糊检索系统中,以离线方式对文本数据集中的单字或者音节建立索引。这是因为,在第1节中所提出的3种距离度量方式都以单字或音节作为最小的考察和计算单位。当采用2种基于拼音的距离度量方式时,要先将文本逐句地转成拼音串(逐句进行拼音的自动标注可以更好地联系上下文处理多音字、变音字等拼音现象),然后再以音节为单位构建索引。在文本数据集的索引表中,需要记录索引头(本索引对应的单字或者音节),以及索引头在文本数据集合中出现过的所有位置(文本号以及在文本中出现的具体位置)。2.2汉字串近邻空间在对原始查询串进行扩展时,需要引入汉字串近邻空间的概念。定义1在具体的汉字串相似度度量方式下,所有与目标串编辑距离为m的汉字串组成的集合,称为该目标串的m近邻空间。m近邻空间中每一个汉字串,称为该目标串的一个m近邻串。将查询串按编辑距离进行由小到大的扩展,其实质就是依次计算查询串的各个近邻空间。而近邻空间内汉字串的数量,直接影响遍历该近邻空间的时间复杂度。下面以基于汉字的编辑距离为例,对近邻空间进行分析。令汉语体系全部汉字的集合为2,则所有长度为n的汉字串总数为ue0012ue001n。对于一个长度为n(n远小于ue0012ue001)的汉字串X,它的0近邻空间显然只包含它自身。对于X的1近邻空间,编辑距离可能由替换、插入和删除这3种方式之一造成。以替换为例,长度为n的汉字串共有n个可能的替换位置,每个替换都有ue0012ue001-1个候选的替换汉字,因此只考虑替换可得到n(ue0012ue001-1)个与X编辑距离为1的汉字串。对插入和删除操作进行类似的分析可知:只考虑插入可以得到约(n+1)ue0012ue001个汉字串,只考虑删除则可以得到n个汉字串。所以总的来说,12近邻空间内所有汉字串的数目大约是(2n+1)ue0012ue001。在实际应用中,n一般不超过10,ue0012ue001的大小至少在103数量级上,所以12近邻空间内汉字串的数目也至少是103的数量级。对于X的m近邻空间内的串,一共发生了m处替换、插入或删除。可近似地认为串X共有(n+1)个位置能够插入汉字,有n个位置的汉字能够删除或者替换。假设在m处变化中有a次插入,m-a次删除或替换,则可产生新的汉字串约Can+1ue0012ue001a×Cm-anue0012ue001m-a个(其中Can+1表示组合数,下同),因此m近邻空间内所有串的数目大约为∑ma=0Can+1Cm-anue0012ue001m=Cm2n+1ue0012ue001m.在实际应用中,虽然m的取值通常不超过nue0002,但m近邻空间内的串仍然数量巨大。对于如此数量级的近邻空间,不可能逐一访问其中每个近邻串来进行检索。即使有可能在较小的时间开销内判断某个汉字串是否符合中文语法,从而去掉许多不合理的近
邻串,这一判断过程需要进行的次数也是惊人的。因此,必须通过其他的方式来遍历近邻空间,完成对原始查询串的扩展。2.3查询扩展和模糊检索依然以基于汉字的编辑距离度量方式为例,介绍本文的模糊检索系统进行查询扩展并检索的过程。令用户输入的查询串为A=a1a2…an,其中ai(i=1,2,…,n)是汉字。在A的1近邻空间中,所有因ai被替换所生成的串有Bi=a1a2…ai-1xai+1…an的形式,其中x∈2且x≠ai。Bi实际上代表ue0012ue001-1个不同汉字串,称Bi为通配串。在检索时,先分别精确地检索两个子串Bi1=a1a2…ai-1和Bi2=ai+1ai+2…an在数据集中出现的位置,然后对两个子串的位置进行比较,找到串Bi1和串Bi2同时出现且Bi1在Bi2的i+1个位置前出现的文本。由于替换可能发生在n个不同的位置,所以类似的通配串有n个。对于插入和删除两种改变方式,可构造类似的通配串扩展并检索。分析上述过程的复杂度。考虑插入、删除和替换这3种操作,则在12近邻空间内通配串的总数目大0331清华大学学报(自然科学版)2009,49(S1)
约是3n,每个串通过至多2次的精确匹配实现模糊检索。考虑到精确匹配的结果可以被不同的通配串共享,实际上只需经过2n-1次精确匹配即可实现12近邻空间内的所有串的检索,这相对于12近邻空间内串的总数量大大减少了。对于A的m近邻空间(m>1),方法是类似的。在编辑距离为m时,可近似认为串有2n+1个位置可能发生改变,相应通配串的数目约为Cm2n+1。由于进行精确匹配的通配串的子串实际上都是原输入串的子串,而原输入串的子串总数量为n(n+1)ue0002,所以实际最多进行n(n+1)ue0002次精确匹配。随着m的增长(m
串一共400个,它们得到的检索结果8平均含大约7篇文本。其中,包含结果数不多于3的query
有31.25%,包含结果数不多于10的query有78.75%,包含结果数不多于30的query有97.5%。完成了3组对比实验。实验数据结果如表1。其中,Top3、Top10和Top30分别指在前3个、前10个和前30个查询返回结果的集合上进行统计和计算的结果。表1模糊匹配系统的准确率和召回率距离度量方式准确率ue000%召回率ue000%Top3Top10Top30Top3Top10Top30基于汉字31.4818.1511.7745.3360.9875.57基于拼音53.7028.2316.8251.4076.5589.52基于拼音的改进60.4234.1719.6254.3184.4591.70从表1可以看出,在准确率和召回率这2项指标上,2种基于拼音的度量方式都比基于汉字的度量方式有较大提高,这是由于拼音能够更好地刻画汉字串之间的相似程度。基于拼音改良的度量方式,在准确率和召回率上,都取得了最好的实验结果,说明引入语音学知识对性能提高有帮助。从表1还可以看出,前30个查询结果已经能够达到90%左右的召回率,而返回前30个结果,一般只需要对原始的错误查询串扩展出不多于10次的扩展。此外,对于4万个文本组成的共79.3MB的文本集合,建立的索引(单级索引,未压缩)大小在100MB左右,基于音节建立的索引与基于单字建立的索引相比,大小并没有显著增加。4结论与未来工作本文所提出的基于拼音改良的编辑距离度量方式,依然存在一些局限性。虽然在实际检索系统的输入中,拼音相关错误占有非常高的比例(在Sogou用户日志的统计中,这一比例超过了90%),但是对于其他类型的错误,例如形近字和近义词带来的错误,本方法提出的距离度量方法并不能很好地进行度量和表征,依然有待进一步的研究。同时,工作在方法依然有较大的改进空间:可以引入语言学方面的知识,以及根据用户日志的实际统计结果,对于每一种改变赋予的权值采用更细致合理的规定。如果两个汉字串的相似度不能方便地转换成整数,如何完备地对查询进行扩展,也是值得研究的问题。未来,计划研究本文提出的查询扩展和检索思路在多级索引下的应用,考察模糊检索的性能,并进行相应的算法改进。同时,结合汉语中的词汇和二元拼音文法进行拼音索引,引入这些先验知识可以有效地降低查询扩展的次数,同时实际的用户大部分也是以词为单位进行输入,引入词汇知识可以更好地匹配用户的实际情况。致谢本文在研究工作中,使用了搜狗(Sogou)实验室无偿开放的文本数据和用户日志,在此表示衷心的感谢。参考文献(References)[1]ManningC,RaghavanP,SchüuctiontoInformationRetrieval.[M].CambridgeUniversityPress.2008.[2]MitraM,SinghalA,ingAutomaticQueryExpansion[C]ue000ue000Procofthe21stAnnIntACM2SIGIRConferenceonReserandDevinInfoRetrieval,1998.[3]AraujoM,NavarroG,extsearchingallowingerrors[C]ue000
aiso,Chile:CarletonUniversityPress.1997,8:2-20.[4]dtourtoapproximatestringmatching[J].ACMComputingSurveys,2001,33(1):31-88.[5]BoyerR,tringsearchingalgorithm[J].CommunicationsoftheACM,1977,20(10):762-772.[6]TarhioJ,imateBoyer2Moorestringmatching[J].SIAMJonComputing,1993,22(2):243-260.[7]KnuthD,MorrisJ,tternmatchinginstrings[J].SIAMJonComputing,1977,6(2):323-350.[8]Baeza2YatesR,2addressingindicesforapproximatetextretrieval[J].JAmSocInfoSci,2000,51(1):69-82.[9]王静帆,邬晓钧,夏云庆,等.中文信息检索系统的模糊匹配算法研究和实现[J].中文信息学报,2007,21(6):ngfan,WUXiaojun,XIAYunqing,oximatestringmatchingalgorithmforChineseinformationretrievalsystems[J].JChinInfoProc,2007,21(6):59-64.(inChinese)[10]陈儒.面向短信过滤的中文信息模糊匹配技术[D].哈尔滨:哈尔滨工业大学信息检索实验室.imateStringMatchingAlgorithmforCell2phoneNotesFiltering[D].InfoRetrievalLab,HarbinInstituteofTechnology,2003.(inChinese)2331清华大学学报(自然科学版)2009,49(S1)