支持多种模糊处理的英文智能预提示输入引擎

官连军, 丁光耀, 张燕妮

(西南交通大学,四川成都610031)

0 研究背景

预提示输入技术有着广泛的用途,如智能输入法、语音检索与语音输入、文本搜索、信息与多媒体检索、互联网搜索引擎。高效率和高容错是输入技术必须解决的主要问题,预提示输入的提出,成为输入技术的转折点,极大地提高了输入效率,而模糊匹配技术的应用以及联想词的生成,为用户带来更多的方便性与灵活性,并解决用户输入中的键盘误击以及拼写错误。目前,中文输入引擎中该技术已得到一定程度的应用,在英文输入环境中也逐渐被认知,如现有手机产品上的英文单词预提示、编译器环境的英文单词预提示、搜索检索词预提示等。

现有的英文预提示中采用的匹配技术,主要基于精确匹配[1-2]或者相似性匹配[3-5]。精确匹配预提示,对用户输入的精确程度要求很高;基于相似性匹配[6-7]的预提示技术,允许用户输入过程中,存在键盘误击以及单词拼写错误,将是未来的发展方向,目前英文输入法在纠错功能上主要基于Levenshtein距离[4]进行纠错以及针对按键范围进行纠错,如搜狗输入法、QQ输入法、百度输入法、触宝输入法、T9输入法,讯飞输入法等,都是基于上述方式实现。而DCN(Discrete/Cross/Non Complete)字符串匹配理论与技术[8]提出了基于离散(Discrete)、交叉(Cross)、非完全(Non complete)3种特性参数的DCN字符串相似性计算方法,建立了基于特性参数的字符串匹配的8种分类模型。技术解决了用户输入方式单一的问题,可提供8种信息模糊输入方式的选择,8种方式分别为:精确、离散、交叉、离散交叉、非完全、离散非完全、交叉非完全、离散交叉非完全。在实际的输入应用中主要特点表现为:离散方式允许输入时任意省略单词中的字符,交叉方式允许输入时可以从单词后面进行补齐,非完全方式允许输入单词中存在错误。

1 DCN英文智能预提示输入引擎

图1 DCN智能预提示输入引擎

1.1 何谓DCN英文智能预提示输入引擎

DCN英文智能预提示输入引擎(DCN English Intelligent Pre-prompt Input Engine,DCN-EIPIE)是一处理程序,对输入的英语查询词(可以是完整的,也可以是部分的或有错误的),通过智能的处理方式(包括DCN相似性计算[8]、频度计算、前文相关性计算、自学习、联想输出等手段),综合考虑相关性因素,从已有单词库或短语库中,按相关度由高到低输出N个候选单词或短语,提交给使用者,参见图1。

1.2 智能预提示输入相关因素

影响预提示效果的主要因素有:单词相似性计算、单词频度处理、前文相关处理、词库完备性、自定义单词处理等。

单词相似性计算确定了词库单词与输入单词的相似度,直接决定了预提示的候选单词列表;频度处理是在候选单词列表确定后,根据相似度与频度,进行综合相关度计算,并由相关度决定候选单词列表中单词的排列顺序;由于输入的连续性,前文输入会对后一次输入有一定的作用;词库完备性直接决定能否查询到想要的词,而自定义词库能增强词库的完备性。

2 DCN-EIPIE系统介绍

2.1 引擎功能

DCN-EIPIE主要提供如下功能:预提示输出功能,联想输出功能,自学习功能,输入模式设置功能,候选列表单词数设置功能。

预提示功能是对输入词进行相关度综合计算,产生预提示候选词列表;联想输出功能是对输入词进行智能预测,产生用户下一次可能输入的候选词列表;自学习功能实现对输入词的自学习处理;输入模式设置功能实现用户对输入模式的选择;候选列表单词数设置功能决定返回给用户的候选词列表中单词的最大数目。

2.2 引擎系统结构图

引擎系统结构图如图2所示。

图2 引擎系统结构图

2.3 动态链接库以及引擎功能接口函数

DCN-EIPIE设计为动态链接库[9],可以简化产品中英文预提示输入的设计,降低工程复杂性,缩短设计周期,可应用于各种需要智能英文预提示输入的相关产品的开发,尤其适合高性能智能手机的键盘或手写英文预提示输入、英文预提示聊天软件、英文预提示相关字处理软件等产品的开发。

DCN-EIPIE提供以下主要接口函数:

(1)智能预提示接口

int PredictOutList(char*inputstring,wordType*outlist)

inputstring为输入字串,outlist为候选词列表,函数返回候选词列表中单词的个数。

(2)联想与自学习接口

int LearningFrom(char*inputstring,wordType*outlist)

inputstring为联想输入字串,outlist为联想词列表,函数返回联想词列表中单词的个数,同时对输入的单词inputstring进行自学习处理。

(3)候选单词个数设置接口

void SetOutNum(int num)

num为候选词列表中单词的最大数目。

(4)模糊查询方式设置接口

void SetFuzzyMode(int mode)

mode为引擎的模糊输入方式的设置参数,1≤mode≤7。根据设置不同的mode参数,引擎可以输出8种不同效果的预提示候选单词列表。

3 引擎主要技术介绍

3.1 相关度综合计算

3.1.1 相似性计算

DCN-EIPIE选用DCN字符串模糊匹配技术进行相似性计算,可以提供8种不同分类模型的相似性计算方法,技术以动态链接库DCN-Fuzzy.dll的形式,提供各分类模型的匹配计算[8]。

单词的相似性计算通过调用DCN-Fuzzy.dll动态链接库中的DCNMatching(p,t,dcn)函数实现,其中p代表输入串,t表示词库中的一个单词,dcn为模糊匹配方式参数设置,函数返回单词p与单词t的相似度。dcn参数设置的不同,决定了不同匹配方式的相似度计算方法。具体内容如表1所示。

其中,D、DN、DC、DCN 4种匹配模式,在输入应用中有较为明显的操作特征与输入效果,也是本引擎限定选择的4种输入模式;符号D代表可以任意省略单词中的字符,C代表可以任意交叉单词中的字符,N代表允许输入中存在错误字符。

3.1.2 频度处理

相似度和频度是单词相关度计算的两个重要因素。当输入词长度较小,频度起着主要作用,随着输入词长度的增加,相似度影响更为明显。通过相关度综合计算公式,可实现相关度权重的平滑过度。

给定词库单词与查询词的相似度 A,频度 f,库中词的最大频度 M,查询词长度L,词库单词与查询词相似度与频度的相关度综合计算公式为:

表1 DCNMatching(p,t,dcn)匹配函数功能列表

其中α为0到1的系数,用于调节频度对相关度影响的权重。

3.1.3 前文处理

由于输入存在连续性,前一次输入对后一次输入有一定程度的影响,基于这种原理对模糊查询进行前文处理。

设pre为前文,t为候选词列表中的单个字串,p为输入串,A为相似度,∑*为库中满足条件的短句集合,wi为短句,LS为短句库,LU为自定义库,fi为短句wi的频度,f为满足条件的短句的频度总和。

前文处理计算方法如下:

(1)∑*={wi|(pre+t)为 wi的前缀子串且wi∈(LS∪LU)}

(3)A=DCNMatching(pre+p,pre+t,dcn);

(4)将 A和f代入式(1)即可求得含有前文的相关度。

3.2 联想处理

为了提高用户的输入效率,通过联想处理,智能预测用户的下一个输入词。通过精确匹配方式从短句库以及自定义库中进行查询,把满足条件的词放入联想词候选列表,并按单词的使用频度从高到低排序。设输入串p,短句库LS,自定义库LU,短句文本 wi,联想词列表L,联想输出为:

L={wi-p|p为wi的前缀子串且wi∈(LS∪LU)}其中wi-p为wi去掉p剩下的字串。

3.3 自学习

由于单词库和短句库的词汇涵盖量有限,并且不同用户在不同领域使用词汇也不尽相同,为了满足不同用户的特殊需求,引擎通过创建用户自定义库来实现该功能。

给定短句库 LS,单词库L W,用户自定义库LU,最大使用频度M,设 w为自定义单词,s为自定义短句,频度赋值函数Freq(p)。

(1)自定义单词处理

若w ∈LU,令Freq(w)=M;若 w∉LU 且w∉LW,令Freq(w)=M,w∈LU

(2)自定义短句处理

若s∈ LU,令Freq(s)=M;若s∉ LU 且s∉ LS,令Freq(s)=M,s∈ LU

随着自定义库使用时间的增加,自定义库中将出现垃圾词汇,即用户很少使用的自定义词汇。为了对垃圾词汇进行自动清理,采用减频策略对自定义库进行处理,即每次载入动态链接库时,自定义库中词汇的频度自动减一,当词汇的频度减为零时,就从自定义库中删除该词。

自学习功能需要解决的另一个问题是处理用户的错误自定义单词,在引擎中采用二次记忆法进行词汇的自定义处理,即一个词汇在同一时间段连续出现两次输入,才会进行词汇的自定义处理。二次记忆法的自定义效果较差,但自定义词的有效性得到很大提升。

4 引擎效果

DCN-EIPIE通过运行测试,主要效果如图3～图7所示。

4.1 不同输入模式的输入效果

DCN-EIPIE提供4种输入模式选择,分别为D模式、DN模式、DC模式、DCN模式。

例如,在D模式下,用户期望得到目标单词”synchronous”或短句”what can I do for you”时,其效果如图3所示。

在DN、DC、DCN模式下,用户期望得到单词”intelligent”时,其效果如图4所示。

4.2 前文效果

用户期望得到单词”condition”时输入”condi”,在没有前文和有前文”good”时的效果如图5所示。

4.3 联想效果

用户输入”united”以后产生的联想词效果如图6所示。

4.4 自定义效果

用户自定义”SWJTU”前后的效果如图7所示。

图5 前文效果图

图6 联想词效果图

图7 自定义效果图

5 结束语

基于DCN字符串模糊匹配理论与技术,实现了多模式输入的英文智能预提输入引擎。该引擎可为用户提供更加灵活、方便、高效的英文预提示输入手段;同时,可以简化商家产品的英文预提示输入的设计,降低工程复杂性,缩短设计周期。其主要创新内容体现在以下几个方面:

(1)提供4种输入模式的选择,即D、DN、DC、DCN。用户可以根据自身的实际情况,选择不同的输入模式。

(2)引擎设计为动态链接库,为厂商提供预提示输入的核心处理技术支持,以缩短开发周期,降低工程的复杂性。

(3)采用了更加综合的智能处理计算,以实现更好的预提示效果。智能处理包括相似性计算、频度计算、前文相关性处理、联想词生成、自定义词汇等。

(4)引擎可应用于英文的键盘以及手写预提示输入,聊天软件的预提示输入,编译器的预提示输入,检索词的预提示等。

[1] 郑志宏,郑志高,王玉婷.模糊查找算法的设计实现[J].情报科学,2010,(6).

[2] 王海峰,李生,赵铁军,等.机器翻译中模式匹配算法的研究[J].哈尔冰工业大学学报,1998,(4).

[3] Navarro.Soft String Matching[M].Publishing House of Electronics Industry,2007.

[4] 苗兰芳,杨传斌.模糊串匹配算法及应用[J].小型微型计算机系统,1996,(10).

[5] 杨思春.一种改进的句子相似度计算模型[J].电子科技大学学报,2006,(6).

[6] 何畏,汪荣贵,查全民.一种新的快速移动单模式匹配算法[J].合肥工业大学学报,2010,(5).

[7] 金博,史彦军,滕弘飞.基于语义理解的文本相似度算法[J].大连理工大学大学报,2005,(2).

[8] Guangyao Ding,Tianrui Li,Weili Zou.A Novel Calculation Model Of Approximate String Matching Based On Characteristic Parameters[C].Intelligent Decision Making System,Proceedings of the 4th International ISKE Conference 2009,11:556-561.

[9] Jeffrey Richter,Christophe Nasarre.Windows via c/C++Fifth Edition[M],2008.

[10] Breslauer D.Efficient String Algorithmics[D].Columbia University,NY,1992.

[11] 殷丽华,方滨兴.一种改进的多模式匹配算法[J].华中科技大学学报:自然科学版(增刊),2005,33.