中文信息检索系统的模糊匹配算法研究和实现.doc

第2l卷第6期 2007年11月中文信息学报 JOURNAL OF CHINESE INFORMATION PROCESSING , NOV.,2007 文章编号:1003—0077(2007)06—0059-06 中文信息检索系统的模糊匹配算法研究和实现王静帆,邬晓钧,夏云庆,郑方(清华大学计算机系清华信息科学与技术国家实验室技术创新和开发部语音和语言技术中心,北京100084) 摘要:在现代中文信息检索系统中,用户输入的字符串和实际数据库中的条目往往存在局部偏差,而基于关键词匹配的检索技术不能很好地解决这一问题。本文参考并改进了Tarhio和Ukkonen提出的过滤算法],针对汉字拼音输入法中常出现的同音字/近音字混用现象,将算法进一步扩展到广义的Edit Distance上。实验表明,本文提出的算法能有效提高中文信息检索系统的召回率,在实际应用中可达到“子线性”的效率。关键词:计算机应用;中文信息处理;模糊匹配;过滤算法;动态规划中图分类号:TP39l 文献标识码:A An Approximate String Matching Algorithm for Chinese Information Retrieval Systems WANG Jing~fan,WU Xiao—j un,XIA Yun—qing,ZHENG Fang ( Sci.& University, Center for Speech and Language Technologies,Division of Technical Innovation and Development, Tsinghua National Laboratory for Information Science and Technology,Beijing 100084,China) Abstract:In the modern Chinese information retrieval systems,classical keyword based string matching can not work when the input string is different from the entries in the paper proposed a method based on Tarhio and Ukkonen’S filtering algorithm tO solve the the Chinese Pinyin typewriting usually con— sists Chinese characters with the same or similar pronunciations,we defined a special Edlt Distance and expended our method experimental results showed that our algorithm can improve the recall rate of the re— trleval systems and obtain practical sub—plexity. Key puter application;Chinese information processing;approximate matching;filter algorithm;dynamic programming 1 引言现有的信息检索系统大部分采用基于关键词匹配的检索技术l_2]。在实际应用中,用户往往凭借印象进行检索,有时只能模糊地描述查询目标,输入的关键词无法和数据集合中保存的数据完全一致;另一方面,在构建数据集时引入的错误(如OCR识别错误等)也可能造成这些数据无法被用户获取。在上述情况下,传统的检索系统将难以从数据集中查找到所需要的信息。本文采用模糊匹配方法查找数据集中和用户输人相似的项,并根据相似度排序输出结果, 以部分解决上述问题。模糊匹配方法还可以用于其他领域,如入侵检测、信息过滤、基因检测等_3“中文用户大部分使用拼音输入法。用户输入查询串时选词错误造成的同音字替换是很典型的一种现象;方言、发音****惯等造成的音近字替换(如南方方言中,zh和z不分)是第二种典型的错误现象。本文针对这些错误,提出了一种考虑同音字/近音字替换的距离度量方法,在此基础上建立模糊匹配算法。收稿Et期:2007-01—09定稿El期:2007 09 10 作者简介:王静帆(1982一),女,硕士生,研究方向为自然语言处理;邬晓钧(197