QA中文查询词纠错初级模型框架

一:中文查询词纠错框架
中文处理的难点: 1, 字符有8W左右; 2, 词汇有6W左右; 3,一词多义; 4,书写不分词; 5,发音与字形(同音词,形近词)

对于初级模型来说可以把输入的字符和数据库中的现有实体名词进行字符串匹配. 如果匹配的上就直接采用用户输入查询词, 如果没有匹配上就需要进行纠错处理.
模型的建立可基于拼音,基于编辑距离,基于N-gram模型,基于统计等.
中文纠错有多种原因, 我们先仅考虑键盘录入错误. 中文查询词纠错的目的主要是推测用户输入, 确定查询信息, 给出纠错意见.
中文查询信息有两大特点: 1. 不包含错字; 2. 错误信息最多的是同音别字错误. 例: 要命-姚明. 这是由于输入法日益流行导致的. 因为拼音输入法学习成本低,思维干扰的最少,普及广,所以出现了大量的同音词错误,而多字漏字的情况多是由于不小心的输入造成的。根据这种错误的特点,设计中文查询词纠错模块使用基于拼音hash词典的纠错算法,和多字驱动词典+字符串匹配的纠错算法,利用前者处理包含同音别字的查询信息,利用后者处理包含多字漏字的查询信息。纠错模块结构如下:

二:同音别字查询词纠错
2.1 对于同音别字查询,首先第一要做的是把输入的字符串转换为拼音
Pinyin4j是一个流行的Java库,支持中文字符和拼音之间的转换。拼音输出格式可以定制。
Pinyin 4j介绍:有时候,需要将汉字编程对应的拼音,以方便数据的处理。比如在Android手机应用 的开发上,要查询联系人的姓名,通常都是用拼音进行查询的。比如要查询“曹孟德”,就可以输入“cmd”,即“曹孟德”三个汉字的拼音 “caomengde”各字的首字母。但是怎样才能将“曹孟德”翻译成“caomengde”呢?很简单的办法就是建立一个大的对照表(比如用关联容器 Map),比如<”曹”,”cao”>,<” 孟”,”meng”>,<” 德”,”de”>…但这样的做法,需要维护好一个比较大的对照表,同时一个汉字可能有多个发音,也就是说Map这样的容器时不行的,因为 其<key,value>必须是一一对应的。在C++中可以用STL里面的multimap来解决这个问题,但Java中没有类似 multimap这样的东西,除非自己实现一个。
Pinyin4j就是为了解决类似这样的问题的。它是sourceforge.net上的一个开源项目,功能非常强大:
+ 支持同一汉字有多个发音
+ 还支持拼音的格式化输出,比如第几声之类的,
+ 同时支持简体中文、繁体中文转换为拼音…使用起来也非常简单。下面是其官方网址,其中提供了下载:http://pinyin4j.sourceforge.net/
我们想得到的是将一段文字中的汉字全部转换成不带音调的拼音输出,而这段文字中又可能包含 阿拉伯数字、英文、标点符号等等。如果完全靠自己写代码进行转换,那是非常麻烦的,其中一个首先就要区别,这段文字中那些是汉字,那些是非汉字。有了 Pinyin4j,这个问题就不再困难了,因为对于非汉字,Pinyin4j会自动输出null。关于Pinyin4j的基本操作可参见博文 http://www.oschina.net/question/54100_27489 例输入中英文混合的一段文字 String str = “荆溪白石出,Hello 天寒红叶稀。Android 山路元无雨,What’s up? 空翠湿人衣。”;
可输出:

jingxibaishichu,Hello tianhanhongyexi。Android shanluyuanwuyu,What’s up? kongcuishirenyi。

对于多音节问题目前先只取第一个音节, 例 输入”婀娜多姿”,会输出 “enaduozi” 如果想输出所有音节的话就修改程序中的数组输出个数. 但是对于多音节来说哪个音节合理可能需要维护一个多音节词表,常用的多音词的数量是否多尚不清楚,不过这个待商榷,因为用户输入不一定就会输入正确的音节,例如婀娜多姿,有的用户知识欠缺的话,可能就会输入成“enaduozi”,所以正确的音节权重高,错误的音节也不能忽视。
同音别字查洵词的纠错原理应该如下所示:

2.2 为了支撑这个算法需要4个模块,第一是原始词库的建立、纠错词典建立、纠错判断和相似性计算排序
首先,原始词库的建立 是为了保证在相同音节的词汇中能有一个词频的排序. 例如姚明 和姚铭. 原始词典中可能都有,但是姚明的词频明显要比姚铭的词频要高很多. 因而把姚明做为推荐纠错词. 这里需要建立一个强大的数据库. 我们先使用现有的用户词典usrdict.txt, 现有的用户词典的一个问题就是没有对应拼音. 解决这个问题可以编程调用Pinyin4j进行拼音标注. (自动标注的一个问题仍然是多音节的问题). 而且,没有词频排序,只要出现权重等价,可根据类互信息进行挑选,只要数据库中的实体词与查询语句中的另一个实体词有关联,则置优先级高。例如查询要命的身高多少?可查找要命的身高,可能会发现usrdict中同时存在要命和姚明两个词,但是发现姚明 和身高 有关联,则姚明置前,作为推荐纠错词。
第二:纠错词典,纠错词典应该是把原始词库按照同音词的拼音为key值的链式hash结构.如:

纠错词典的建立过程是:
①从原始词库中读取一个词条,进入步骤②。
②将词条的每一个汉字转化为拼音,得到词条的拼音x;进入步骤3。
③以得到x为自变量,经由hash函数f(x)得到X对应的hash元素,将词条加入到相应的hash元素的链表中,进入步骤④。
④如果关键字源文件还有剩余词条,则进入步骤①,否则进入⑤
⑤词典建立结束。
第三:纠错判定
以下几种情况就需要进行纠错处理:
1,输入的关键字在数据库中查不到 (或者没有关联节点),例如有 要命,但是要命和身高无关联;
2,对输入的中文信息分词时发现连续的单字字符串;
3,检索输入词条中不包含汉字只包含拼音;
4,检索输入词条中同时包含拼音与汉字。
第四:拼音相似性计算排序
第一种方案是由同音词字符来计算;对字串ZlZ2…Zn(Zi为错误字串的一个字)和词C1C2…Cm(Ci为纠错建议词中的一个字),字串中的相同字比重越多则相似性越强。例如:输入“西按市”去检索信息,“西按市”满足纠错判定条件,将其转化为“xianshi”,由“xianshi”确定的一组其词条为“西安市”、“显示”、“现实”、“县市”,排序取前N(N=3)项的结果为:西安市、县市、显示。
此处注意的是多音词问题,例如在上述过程中,将错误的词条转化为拼音时,要考虑多音字的情况。例如,词条“”被转化为“zhangdu”而不是“changdu’’时,不就不会得到纠错结果“长度”了。
为了处理多音字的问题,在词条转换为拼音时,需要根据多音字音字对照表,如果词条中包含多音字,则给出词条拼音的所有组合(借助java pinyin4j库),对组合中每一个词条拼音都进行获取同音词条、相似计算、排序的处理。

【以后的工作】第二更深入的方案,就是对拼音进行编辑距离的操作。例如姚明yaoming 可能会错误输入称姚敏yaomin。注意这个拼错都是有规律性的,因为拼的太离谱的字母串是拼不出汉字字符的。如用户不会拼成yoamnig这样的错误。除非进来的查询词就是拼音,而不是汉语字符,这时才考虑这种情况。这个操作的计算量会比较大,暂时放到后面做。

三:漏字多字查询词纠错
对漏字,多字的中文词条纠错多采用使用双字驱动双向词典,以错误词条的首字,尾字为其发信息,通过中文字符串模糊匹配方法将发现的相似词条放入集合中,由纠错建议排序程序根据一定的规则对它们进行排序.作为纠错建议。本系统中可利用正则表达式把查询词和usrdict中的词进行匹配查询。
3.1 字符串模糊匹配算法—极大似然模糊匹配算法
对字串ZIZ223…..Zn(Zi为错误字串的一个字)和词C1C2C3…..Cm(Ci为纠错建议词中的一个字):设函数\[Same({Z_i},{C_i}) = \left\{ {\begin{array}{*{20}{c}}
{1,}\\
{0,}
\end{array}} \right.\begin{array}{*{20}{c}}
{}\\
{}
\end{array}\begin{array}{*{20}{c}}
{{Z_i} = {C_i}}\\
{{Z_i} \ne {C_i}}
\end{array}\]
下列条件成立:
若当m≥n时,有:
∑Same(Zi,Ci)≥n-1 (1≤i≤n:Zl=c1)
或∑Same(Zn-i+l,Cm-i+1)≥n-1 (1≤i≤n:Zn=Cm)
或∑Same(Zi,Ci)+∑Same(Zn-i+l,Cm-i+1)≥n-1 (1≤i≤n:ZI=C1:Zn=Cm)
即表示当建议词比较长时,记录从词头或词尾或两头同时记录相同词,如果大于错误查询词的长度n-1时,就可以认为似然匹配,例如,Z=中华人民和国 与C=中华人民共和国 似然匹配
当m<n时,有:
∑Same(Zi,Ci)+Same(Zn-i+l,Cm-i+1)=m (1≤i≤m:ZI=C1:Zn=Cm)
注意,对于建议词比较短时,只考虑两头相同的情况。
以上这两种情况称字串ZlZ223…..Zn与词C1C2C3…..Cm似然匹配。记为Match(Z12223…Zn,C1C2C3…Cm)。
似然匹配可纠正任一字与原串不同的词条、首尾漏字、词中多字、少字等错误。
如:match(“当务之争”,“当务之急”),match(“而走险”,“铤而走险”)等
但仍有个问题就是对于首尾同时出错如,(忠科院自动化锁,中科院自动化所),且建议词比查询词短时,比如查询词(国中科院自动化所务,中科院自动化所)按照文献[3]的简单的似然匹配算法无法进行合理匹配,比如:(假设中科院自动化所不可再分词)
错误查询词 由似然匹配算法计算相同字数
中科院自动化 6
科院自动化所 6
中中科院自动化所务 1
中科院上自动化所 4
3.2改进中文字符的似然匹配算法
可见,后面两条的相似度计算都不好,因而需要修正。设字符串Z:Z1Z2Z3…..Zn和C:C1C2C3…..Cm;N,M分别为其字符串的长度,假设Z为错误串,C为正确字符串。
(1)、i,j分别为Z,C字符串的下标,初值设为0,similar表示两串相同汉字个数初值设为0。
(2)、如果i<N-1,j<M-1进入(3),否则进入(4);
(3)、如果same(Zi,Cj)==1,那么i++;j++;similar++;如果same(Zi,Cj)≠1,如果N>M,i++;如果N≤M,j++。进入步骤(2);
(4)、F=similar/M X 100%,i=N,j=M,similar=0进入步骤(5);
(5)、如果i≥0,J≥0进入(6):否则进入(7);
(6)、如果same(Zi,Cj)==l,勇B么i–;j–;similar++;如果same(Zi,Cj)≠1,如果N>M,i–;如果N≤M,j–。进入步骤(5)
(7)、B=similar/M X 100%,相似度=max(F,B);分别为Z,Q字符串的下标计算的值作为相似度返回。
即,从头对字符串进行逐一匹配,然后从尾开始对字符串进行逐一匹配,最后找出最大相似比。但是这里仍有个问题,相似度计算的分母应该是max(M,N)可能更合理一点,因为错误的查询词可能会很长,而建议词比较短。那么上面算法的bug就会算出很多相似度为100的推荐词。
注意,这里仍采用双字驱动字典查询方法。

3.3 多字驱动字典
【以后的工作】上面提到的都是双字驱动,即以查询词的首字和尾字进行查询,但是有相当一部分的查询词首字,尾字均不正确,这导致只使用错误词条的首字,尾字为信息的方式将无法对这种查询词进行有效的纠错,因此可考虑采用多字驱动字典,利用更多地启发信息进行纠错。

参考:1, http://www.oschina.net/question/54100_27489 Pinyin4j的基本使用方法
2, 搜索引擎中中文分词与纠错模块的设计与实现 硕士论文 2008 北京交通
3, 中文校对系统中纠错知识库的构造及纠错建议的产生算法 2000

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>