论文部分内容阅读
摘要：相似字符串的模糊查询是信息检索的重要组成部分,一直是人们研究的热点。目前基于关键词的查询技术都是前缀匹配,无法查找到与搜索字符串相似的结果。该文提出一种基于n-gram的中英文字符串分割技术的算法,该技术主要是对字符串进行中英文识别，然后基于n-gram按照指定长度进行分割，该技术是实现基于关键词的模糊查询技术的基础。该技术在数据清洗以及学位论文TMLC系统和垃圾邮件过滤等方面也有重要的应用前景。
关键词:模糊查询; n-gram;字符串分割;编辑距离;数据挖掘
中图分类号：TP391文献标识码：A文章编号：1009-3044(2012)23-5530-04
Implementation of Algorithm Based on n-gram Chinese-English String Segmentation
HE Xiao-ming，HONG Qin，CAI Jian-yong，LIN Hong
(College of Photonic and Electronic Engineering of Fujian Normal University Cangshan Campus, Fuzhou 350007, China)
Abstract: Similar string of fuzzy query is an important part of the information retrieval, has been the hotspot of the research. The keyword search technology is the prefix matching, unable to find similar results with the search string. This paper presents a n-gram based in the Chi? nese-English string segmentation algorithm, the technique is mainly to string recognition based on n-gram in Chinese-English, then in ac? cordance with the specified length of segmentation, the technique is realized based on keywords fuzzy query technology based. The tech? nology in data cleaning and dissertations TMLC system and spam filtering has important application prospect.
Key words: fuzzy query; n-gram; string segmentation; edit distance; data mining
自从改革开放以来，中国与世界各国的联系一步一步地加强。这种不断加强的联系表现在信息的表达形式上是凸显的。在日常生活查找信息时，我们很容易看到一些中英文混合使用的表达方式。比如：中国各省人均GDP，windows操作系统，3G手机，3D电影，做CT，ICU病房等。面对这样一个新形势的信息爆炸时代，如何从互联网的海量信息中快速准确地找到我们所需的信息成为一个难题[1]。
在信息爆炸时代里，搜索引擎已经成为千千万万网民上网的必备工具。但是随着信息量的不断增长，人们在在进行查询的时候,有可能输入错误的信息（比如错误的字母，错误的数字，错误的同音汉字）。在这些一种情况下,用户可能就无法得到想要的查询结果。尽管目前已经有些搜索引擎中加入了“您是否要找***”等类似的功能[2],但这依然无法快速准确的满足用户的查询要求。
因此,如何从海量的中英文数据中查找出与查询字符串相类似的查询结果,是该文努力研究的方向。目前，已经有人提出了基于n-gram的字符串分割的算法实现[3]。该算法只针对英文字符串，能解决在英文信息检索中基于关键词的查询技术前缀精确匹配问题[4],也就是检索结果是“错误的输入,错误的输出”,还能解决用户因记忆模糊或误输入单词中的个别字母,甚至在数据库中可能存在某些不正确的数据即“脏数据”的这些情况下可能无法得到用户所期待的查询结果[5]。已有的算法针对的是英文数据，对中英文这样的数据束手无策。为此，该文提出一种改进的解决方法,首先对关键词进行中英文识别,然后根据指定长度对字符串进行分割。综上所述，该文对基于关键词的传统查询方法和基于n-gram的字符串分割的算法进行了分析，提出了基于n-gram的中英文字符串分割的算法。
1基于关键词的查询
1.1传统的查询方法
随着网络通信的快速发展,信息爆炸已经成为一个不可避免的趋势。当人们面对如此巨大的信息量时如何从互联网的海量信息中快速准确地找到我们所需的信息成为一个难题。此时，搜索引擎已经成为千千万万网民上网的必备工具。互联网上已有的搜索引擎可分为两种：目录式搜索引擎和基于关键词的搜索引擎，后者处于主流地位[6]。基于关键词查询一般都是精确匹配，其不足之处是：当检索者因为记忆错误或操作错误而输入错误查找信息，甚至因为数据库本来已存有错误的信息，而无法找到想要的信息。为此该文对原有算法进行了改进，提出了基于n-gram的中英文字符串分割的算法实现，可对中英文信息实现基于关键词的模糊搜索。
1.2基于n-gram的字符串分割技术的查询方法
该查询方法可以避免基于关键词查询技术的完全匹配的问题。当用户在操作失误或记忆不清时输入有误的查询信息时,利用基于n-gram的中英文字符串分割技术的查询方法，用户将可以找到自己需要的信息。现将显示基于关键词查询的主要流程图（如图1）[7]和基于n-gram的字符串分割技术查询的主要流程图（如图2）。
其中，分割后的字符串可通过编辑距离[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.1 n-gram
n-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）ChechInsert_Function(参量cPtr,参量iSegmentationLen,参量id)
这个函数是用来判断是否可以插入ID，因为有的分割字符串的ID已经存在于目标文件中，我们就不需要再插入ID。cPtr表示分割好的字符串，iSegmentationLen表示分割长度，id表示行号。
（7）Search_Function(参量Dest_fp,参量cPtr,参量iSegmentationLen,参量id)
这个函数是利用函数（1）（5）（6）查找分割的字符片段在不同行是否有重复，如不重复则写入到输出文件；如果在不同行重复则在该行的文本后加上当前的行号输出；如果在同行重复则不改变原先的输出。Dest_fp表示目标文件，cPtr表示分割完成的字符串，iSegmentation表示分割长度，id表示行号。
以下是本算法的实现过程：
If源文件存在
打开目标文件，没有则新建一个
获取分割长度
识别字符串中的字符，按照指定长度分割
取出一行字符串中分割的字符串片段，并写入ID存入目标文件（重复字符串片段只保存一次）
利用Search_Function（）函数
Else退出程序
2.3实验结果与分析
本实验在运行环境为Intel(R) Core(TM)2 Duo CPU T5450 @1.66GHZ 1.66GHZ,1.50G内存的Windows XP系统通过对包含不同记录数的文该文件，设定不同的分割长度进行分割，程序运行时间比较如图4所示：
说明：横轴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] Kukich K. Techniques for automatically correcting words intext [J]. ACM Comput. Surv. , 1992,24 (4):377-439.
[5] Ji Shengyue,Li Guoliang,Li Chen, et al. Efficient interactive fuzzy keyword search [C] . InternationalWorld Wide Web Conference,2009: 371-380.
[6] Behm Alexander, Ji Shengyue,Li Chen, et al. Space-constrained gram-based indexing for efficient approximate string search[C].ICDE, 2009: 604-615.
[7]沈文婷.数据库关键字查询清理技术研究[J].电脑知识与技术, 2011(34).
[8] L i C, Lu J, Lu Y. Efficient merging and filtering algorithms for approximate string searches [C] .ICDE,2008:257-266.
[9] Wang J, Li G, Feng J. Fast-join: An efficient method for fuzzy token matching based string similarity join[C] .ICDE, 2011: 458-469.
[10]潘磊.基于权重的Jaccard相似度度量的实体识别方法[J].北京交通大学学报, 2009(6).
[11] Jiannan Wang, Guoliang Li, Jianhua Feng : Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints. [J]. PVLDB 2010 PVLDB 3 (1) :1219-1230.
[12] ChaudhuriS, GantiV, Kaushik R. Aprimitive operator for similarity joins in data cleaning[C] .ICDE,2006.
[13] Wagner R A, FischerM J. The string2to2string correction problem[J]. ACM, 1974, 21 (1) : 168-173.
[14]张旻浩.国内外学术不端文献检测系统平台的比较研究[J].中国科技期刊研究, 2011(4).
[15]常凯.基于TF*IDF垃圾邮件过滤改进算法的研究[J].电脑知识与技术, 2010(25).
关键词:模糊查询; n-gram;字符串分割;编辑距离;数据挖掘
中图分类号：TP391文献标识码：A文章编号：1009-3044(2012)23-5530-04
Implementation of Algorithm Based on n-gram Chinese-English String Segmentation
HE Xiao-ming，HONG Qin，CAI Jian-yong，LIN Hong
(College of Photonic and Electronic Engineering of Fujian Normal University Cangshan Campus, Fuzhou 350007, China)
Abstract: Similar string of fuzzy query is an important part of the information retrieval, has been the hotspot of the research. The keyword search technology is the prefix matching, unable to find similar results with the search string. This paper presents a n-gram based in the Chi? nese-English string segmentation algorithm, the technique is mainly to string recognition based on n-gram in Chinese-English, then in ac? cordance with the specified length of segmentation, the technique is realized based on keywords fuzzy query technology based. The tech? nology in data cleaning and dissertations TMLC system and spam filtering has important application prospect.
Key words: fuzzy query; n-gram; string segmentation; edit distance; data mining
自从改革开放以来，中国与世界各国的联系一步一步地加强。这种不断加强的联系表现在信息的表达形式上是凸显的。在日常生活查找信息时，我们很容易看到一些中英文混合使用的表达方式。比如：中国各省人均GDP，windows操作系统，3G手机，3D电影，做CT，ICU病房等。面对这样一个新形势的信息爆炸时代，如何从互联网的海量信息中快速准确地找到我们所需的信息成为一个难题[1]。
在信息爆炸时代里，搜索引擎已经成为千千万万网民上网的必备工具。但是随着信息量的不断增长，人们在在进行查询的时候,有可能输入错误的信息（比如错误的字母，错误的数字，错误的同音汉字）。在这些一种情况下,用户可能就无法得到想要的查询结果。尽管目前已经有些搜索引擎中加入了“您是否要找***”等类似的功能[2],但这依然无法快速准确的满足用户的查询要求。
因此,如何从海量的中英文数据中查找出与查询字符串相类似的查询结果,是该文努力研究的方向。目前，已经有人提出了基于n-gram的字符串分割的算法实现[3]。该算法只针对英文字符串，能解决在英文信息检索中基于关键词的查询技术前缀精确匹配问题[4],也就是检索结果是“错误的输入,错误的输出”,还能解决用户因记忆模糊或误输入单词中的个别字母,甚至在数据库中可能存在某些不正确的数据即“脏数据”的这些情况下可能无法得到用户所期待的查询结果[5]。已有的算法针对的是英文数据，对中英文这样的数据束手无策。为此，该文提出一种改进的解决方法,首先对关键词进行中英文识别,然后根据指定长度对字符串进行分割。综上所述，该文对基于关键词的传统查询方法和基于n-gram的字符串分割的算法进行了分析，提出了基于n-gram的中英文字符串分割的算法。
1基于关键词的查询
1.1传统的查询方法
随着网络通信的快速发展,信息爆炸已经成为一个不可避免的趋势。当人们面对如此巨大的信息量时如何从互联网的海量信息中快速准确地找到我们所需的信息成为一个难题。此时，搜索引擎已经成为千千万万网民上网的必备工具。互联网上已有的搜索引擎可分为两种：目录式搜索引擎和基于关键词的搜索引擎，后者处于主流地位[6]。基于关键词查询一般都是精确匹配，其不足之处是：当检索者因为记忆错误或操作错误而输入错误查找信息，甚至因为数据库本来已存有错误的信息，而无法找到想要的信息。为此该文对原有算法进行了改进，提出了基于n-gram的中英文字符串分割的算法实现，可对中英文信息实现基于关键词的模糊搜索。
1.2基于n-gram的字符串分割技术的查询方法
该查询方法可以避免基于关键词查询技术的完全匹配的问题。当用户在操作失误或记忆不清时输入有误的查询信息时,利用基于n-gram的中英文字符串分割技术的查询方法，用户将可以找到自己需要的信息。现将显示基于关键词查询的主要流程图（如图1）[7]和基于n-gram的字符串分割技术查询的主要流程图（如图2）。
其中，分割后的字符串可通过编辑距离[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.1 n-gram
n-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）ChechInsert_Function(参量cPtr,参量iSegmentationLen,参量id)
这个函数是用来判断是否可以插入ID，因为有的分割字符串的ID已经存在于目标文件中，我们就不需要再插入ID。cPtr表示分割好的字符串，iSegmentationLen表示分割长度，id表示行号。
（7）Search_Function(参量Dest_fp,参量cPtr,参量iSegmentationLen,参量id)
这个函数是利用函数（1）（5）（6）查找分割的字符片段在不同行是否有重复，如不重复则写入到输出文件；如果在不同行重复则在该行的文本后加上当前的行号输出；如果在同行重复则不改变原先的输出。Dest_fp表示目标文件，cPtr表示分割完成的字符串，iSegmentation表示分割长度，id表示行号。
以下是本算法的实现过程：
If源文件存在
打开目标文件，没有则新建一个
获取分割长度
识别字符串中的字符，按照指定长度分割
取出一行字符串中分割的字符串片段，并写入ID存入目标文件（重复字符串片段只保存一次）
利用Search_Function（）函数
Else退出程序
2.3实验结果与分析
本实验在运行环境为Intel(R) Core(TM)2 Duo CPU T5450 @1.66GHZ 1.66GHZ,1.50G内存的Windows XP系统通过对包含不同记录数的文该文件，设定不同的分割长度进行分割，程序运行时间比较如图4所示：
说明：横轴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] Kukich K. Techniques for automatically correcting words intext [J]. ACM Comput. Surv. , 1992,24 (4):377-439.
[5] Ji Shengyue,Li Guoliang,Li Chen, et al. Efficient interactive fuzzy keyword search [C] . InternationalWorld Wide Web Conference,2009: 371-380.
[6] Behm Alexander, Ji Shengyue,Li Chen, et al. Space-constrained gram-based indexing for efficient approximate string search[C].ICDE, 2009: 604-615.
[7]沈文婷.数据库关键字查询清理技术研究[J].电脑知识与技术, 2011(34).
[8] L i C, Lu J, Lu Y. Efficient merging and filtering algorithms for approximate string searches [C] .ICDE,2008:257-266.
[9] Wang J, Li G, Feng J. Fast-join: An efficient method for fuzzy token matching based string similarity join[C] .ICDE, 2011: 458-469.
[10]潘磊.基于权重的Jaccard相似度度量的实体识别方法[J].北京交通大学学报, 2009(6).
[11] Jiannan Wang, Guoliang Li, Jianhua Feng : Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints. [J]. PVLDB 2010 PVLDB 3 (1) :1219-1230.
[12] ChaudhuriS, GantiV, Kaushik R. Aprimitive operator for similarity joins in data cleaning[C] .ICDE,2006.
[13] Wagner R A, FischerM J. The string2to2string correction problem[J]. ACM, 1974, 21 (1) : 168-173.
[14]张旻浩.国内外学术不端文献检测系统平台的比较研究[J].中国科技期刊研究, 2011(4).
[15]常凯.基于TF*IDF垃圾邮件过滤改进算法的研究[J].电脑知识与技术, 2010(25).