官連軍, 丁光耀, 張燕妮

(西南交通大學(xué),四川成都610031)

0 研究背景

預(yù)提示輸入技術(shù)有著廣泛的用途,如智能輸入法、語音檢索與語音輸入、文本搜索、信息與多媒體檢索、互聯(lián)網(wǎng)搜索引擎。高效率和高容錯是輸入技術(shù)必須解決的主要問題,預(yù)提示輸入的提出,成為輸入技術(shù)的轉(zhuǎn)折點,極大地提高了輸入效率,而模糊匹配技術(shù)的應(yīng)用以及聯(lián)想詞的生成,為用戶帶來更多的方便性與靈活性,并解決用戶輸入中的鍵盤誤擊以及拼寫錯誤。目前,中文輸入引擎中該技術(shù)已得到一定程度的應(yīng)用,在英文輸入環(huán)境中也逐漸被認知,如現(xiàn)有手機產(chǎn)品上的英文單詞預(yù)提示、編譯器環(huán)境的英文單詞預(yù)提示、搜索檢索詞預(yù)提示等。

現(xiàn)有的英文預(yù)提示中采用的匹配技術(shù),主要基于精確匹配[1-2]或者相似性匹配[3-5]。精確匹配預(yù)提示,對用戶輸入的精確程度要求很高;基于相似性匹配[6-7]的預(yù)提示技術(shù),允許用戶輸入過程中,存在鍵盤誤擊以及單詞拼寫錯誤,將是未來的發(fā)展方向,目前英文輸入法在糾錯功能上主要基于Levenshtein距離[4]進行糾錯以及針對按鍵范圍進行糾錯,如搜狗輸入法、QQ輸入法、百度輸入法、觸寶輸入法、T9輸入法,訊飛輸入法等,都是基于上述方式實現(xiàn)。而DCN(Discrete/Cross/Non Complete)字符串匹配理論與技術(shù)[8]提出了基于離散(Discrete)、交叉(Cross)、非完全(Non complete)3種特性參數(shù)的DCN字符串相似性計算方法,建立了基于特性參數(shù)的字符串匹配的8種分類模型。技術(shù)解決了用戶輸入方式單一的問題,可提供8種信息模糊輸入方式的選擇,8種方式分別為:精確、離散、交叉、離散交叉、非完全、離散非完全、交叉非完全、離散交叉非完全。在實際的輸入應(yīng)用中主要特點表現(xiàn)為:離散方式允許輸入時任意省略單詞中的字符,交叉方式允許輸入時可以從單詞后面進行補齊,非完全方式允許輸入單詞中存在錯誤。

1 DCN英文智能預(yù)提示輸入引擎

圖1 DCN智能預(yù)提示輸入引擎

1.1 何謂DCN英文智能預(yù)提示輸入引擎

DCN英文智能預(yù)提示輸入引擎(DCN English Intelligent Pre-prompt Input Engine,DCN-EIPIE)是一處理程序,對輸入的英語查詢詞(可以是完整的,也可以是部分的或有錯誤的),通過智能的處理方式(包括DCN相似性計算[8]、頻度計算、前文相關(guān)性計算、自學(xué)習(xí)、聯(lián)想輸出等手段),綜合考慮相關(guān)性因素,從已有單詞庫或短語庫中,按相關(guān)度由高到低輸出N個候選單詞或短語,提交給使用者,參見圖1。

1.2 智能預(yù)提示輸入相關(guān)因素

影響預(yù)提示效果的主要因素有:單詞相似性計算、單詞頻度處理、前文相關(guān)處理、詞庫完備性、自定義單詞處理等。

單詞相似性計算確定了詞庫單詞與輸入單詞的相似度,直接決定了預(yù)提示的候選單詞列表;頻度處理是在候選單詞列表確定后,根據(jù)相似度與頻度,進行綜合相關(guān)度計算,并由相關(guān)度決定候選單詞列表中單詞的排列順序;由于輸入的連續(xù)性,前文輸入會對后一次輸入有一定的作用;詞庫完備性直接決定能否查詢到想要的詞,而自定義詞庫能增強詞庫的完備性。

2 DCN-EIPIE系統(tǒng)介紹

2.1 引擎功能

DCN-EIPIE主要提供如下功能:預(yù)提示輸出功能,聯(lián)想輸出功能,自學(xué)習(xí)功能,輸入模式設(shè)置功能,候選列表單詞數(shù)設(shè)置功能。

預(yù)提示功能是對輸入詞進行相關(guān)度綜合計算,產(chǎn)生預(yù)提示候選詞列表;聯(lián)想輸出功能是對輸入詞進行智能預(yù)測,產(chǎn)生用戶下一次可能輸入的候選詞列表;自學(xué)習(xí)功能實現(xiàn)對輸入詞的自學(xué)習(xí)處理;輸入模式設(shè)置功能實現(xiàn)用戶對輸入模式的選擇;候選列表單詞數(shù)設(shè)置功能決定返回給用戶的候選詞列表中單詞的最大數(shù)目。

2.2 引擎系統(tǒng)結(jié)構(gòu)圖

引擎系統(tǒng)結(jié)構(gòu)圖如圖2所示。

圖2 引擎系統(tǒng)結(jié)構(gòu)圖

2.3 動態(tài)鏈接庫以及引擎功能接口函數(shù)

DCN-EIPIE設(shè)計為動態(tài)鏈接庫[9],可以簡化產(chǎn)品中英文預(yù)提示輸入的設(shè)計,降低工程復(fù)雜性,縮短設(shè)計周期,可應(yīng)用于各種需要智能英文預(yù)提示輸入的相關(guān)產(chǎn)品的開發(fā),尤其適合高性能智能手機的鍵盤或手寫英文預(yù)提示輸入、英文預(yù)提示聊天軟件、英文預(yù)提示相關(guān)字處理軟件等產(chǎn)品的開發(fā)。

DCN-EIPIE提供以下主要接口函數(shù):

(1)智能預(yù)提示接口

int PredictOutList(char*inputstring,wordType*outlist)

inputstring為輸入字串,outlist為候選詞列表,函數(shù)返回候選詞列表中單詞的個數(shù)。

(2)聯(lián)想與自學(xué)習(xí)接口

int LearningFrom(char*inputstring,wordType*outlist)

inputstring為聯(lián)想輸入字串,outlist為聯(lián)想詞列表,函數(shù)返回聯(lián)想詞列表中單詞的個數(shù),同時對輸入的單詞inputstring進行自學(xué)習(xí)處理。

(3)候選單詞個數(shù)設(shè)置接口

void SetOutNum(int num)

num為候選詞列表中單詞的最大數(shù)目。

(4)模糊查詢方式設(shè)置接口

void SetFuzzyMode(int mode)

mode為引擎的模糊輸入方式的設(shè)置參數(shù),1≤mode≤7。根據(jù)設(shè)置不同的mode參數(shù),引擎可以輸出8種不同效果的預(yù)提示候選單詞列表。

3 引擎主要技術(shù)介紹

3.1 相關(guān)度綜合計算

3.1.1 相似性計算

DCN-EIPIE選用DCN字符串模糊匹配技術(shù)進行相似性計算,可以提供8種不同分類模型的相似性計算方法,技術(shù)以動態(tài)鏈接庫DCN-Fuzzy.dll的形式,提供各分類模型的匹配計算[8]。

單詞的相似性計算通過調(diào)用DCN-Fuzzy.dll動態(tài)鏈接庫中的DCNMatching(p,t,dcn)函數(shù)實現(xiàn),其中p代表輸入串,t表示詞庫中的一個單詞,dcn為模糊匹配方式參數(shù)設(shè)置,函數(shù)返回單詞p與單詞t的相似度。dcn參數(shù)設(shè)置的不同,決定了不同匹配方式的相似度計算方法。具體內(nèi)容如表1所示。

其中,D、DN、DC、DCN 4種匹配模式,在輸入應(yīng)用中有較為明顯的操作特征與輸入效果,也是本引擎限定選擇的4種輸入模式;符號D代表可以任意省略單詞中的字符,C代表可以任意交叉單詞中的字符,N代表允許輸入中存在錯誤字符。

3.1.2 頻度處理

相似度和頻度是單詞相關(guān)度計算的兩個重要因素。當(dāng)輸入詞長度較小,頻度起著主要作用,隨著輸入詞長度的增加,相似度影響更為明顯。通過相關(guān)度綜合計算公式,可實現(xiàn)相關(guān)度權(quán)重的平滑過度。

給定詞庫單詞與查詢詞的相似度 A,頻度 f,庫中詞的最大頻度 M,查詢詞長度L,詞庫單詞與查詢詞相似度與頻度的相關(guān)度綜合計算公式為:

表1 DCNMatching(p,t,dcn)匹配函數(shù)功能列表

其中α為0到1的系數(shù),用于調(diào)節(jié)頻度對相關(guān)度影響的權(quán)重。

3.1.3 前文處理

由于輸入存在連續(xù)性,前一次輸入對后一次輸入有一定程度的影響,基于這種原理對模糊查詢進行前文處理。

設(shè)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)即可求得含有前文的相關(guān)度。

3.2 聯(lián)想處理

為了提高用戶的輸入效率,通過聯(lián)想處理,智能預(yù)測用戶的下一個輸入詞。通過精確匹配方式從短句庫以及自定義庫中進行查詢,把滿足條件的詞放入聯(lián)想詞候選列表,并按單詞的使用頻度從高到低排序。設(shè)輸入串p,短句庫LS,自定義庫LU,短句文本 wi,聯(lián)想詞列表L,聯(lián)想輸出為:

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

3.3 自學(xué)習(xí)

由于單詞庫和短句庫的詞匯涵蓋量有限,并且不同用戶在不同領(lǐng)域使用詞匯也不盡相同,為了滿足不同用戶的特殊需求,引擎通過創(chuàng)建用戶自定義庫來實現(xiàn)該功能。

給定短句庫 LS,單詞庫L W,用戶自定義庫LU,最大使用頻度M,設(shè) w為自定義單詞,s為自定義短句,頻度賦值函數(shù)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

隨著自定義庫使用時間的增加,自定義庫中將出現(xiàn)垃圾詞匯,即用戶很少使用的自定義詞匯。為了對垃圾詞匯進行自動清理,采用減頻策略對自定義庫進行處理,即每次載入動態(tài)鏈接庫時,自定義庫中詞匯的頻度自動減一,當(dāng)詞匯的頻度減為零時,就從自定義庫中刪除該詞。

自學(xué)習(xí)功能需要解決的另一個問題是處理用戶的錯誤自定義單詞,在引擎中采用二次記憶法進行詞匯的自定義處理,即一個詞匯在同一時間段連續(xù)出現(xiàn)兩次輸入,才會進行詞匯的自定義處理。二次記憶法的自定義效果較差,但自定義詞的有效性得到很大提升。

4 引擎效果

DCN-EIPIE通過運行測試,主要效果如圖3～圖7所示。

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

DCN-EIPIE提供4種輸入模式選擇,分別為D模式、DN模式、DC模式、DCN模式。

例如,在D模式下,用戶期望得到目標(biāo)單詞”synchronous”或短句”what can I do for you”時,其效果如圖3所示。

在DN、DC、DCN模式下,用戶期望得到單詞”intelligent”時,其效果如圖4所示。

4.2 前文效果

用戶期望得到單詞”condition”時輸入”condi”,在沒有前文和有前文”good”時的效果如圖5所示。

4.3 聯(lián)想效果

用戶輸入”united”以后產(chǎn)生的聯(lián)想詞效果如圖6所示。

4.4 自定義效果

用戶自定義”SWJTU”前后的效果如圖7所示。

圖5 前文效果圖

圖6 聯(lián)想詞效果圖

圖7 自定義效果圖

5 結(jié)束語

基于DCN字符串模糊匹配理論與技術(shù),實現(xiàn)了多模式輸入的英文智能預(yù)提輸入引擎。該引擎可為用戶提供更加靈活、方便、高效的英文預(yù)提示輸入手段;同時,可以簡化商家產(chǎn)品的英文預(yù)提示輸入的設(shè)計,降低工程復(fù)雜性,縮短設(shè)計周期。其主要創(chuàng)新內(nèi)容體現(xiàn)在以下幾個方面:

(1)提供4種輸入模式的選擇,即D、DN、DC、DCN。用戶可以根據(jù)自身的實際情況,選擇不同的輸入模式。

(2)引擎設(shè)計為動態(tài)鏈接庫,為廠商提供預(yù)提示輸入的核心處理技術(shù)支持,以縮短開發(fā)周期,降低工程的復(fù)雜性。

(3)采用了更加綜合的智能處理計算,以實現(xiàn)更好的預(yù)提示效果。智能處理包括相似性計算、頻度計算、前文相關(guān)性處理、聯(lián)想詞生成、自定義詞匯等。

(4)引擎可應(yīng)用于英文的鍵盤以及手寫預(yù)提示輸入,聊天軟件的預(yù)提示輸入,編譯器的預(yù)提示輸入,檢索詞的預(yù)提示等。

[1] 鄭志宏,鄭志高,王玉婷.模糊查找算法的設(shè)計實現(xiàn)[J].情報科學(xué),2010,(6).

[2] 王海峰,李生,趙鐵軍,等.機器翻譯中模式匹配算法的研究[J].哈爾冰工業(yè)大學(xué)學(xué)報,1998,(4).

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

[4] 苗蘭芳,楊傳斌.模糊串匹配算法及應(yīng)用[J].小型微型計算機系統(tǒng),1996,(10).

[5] 楊思春.一種改進的句子相似度計算模型[J].電子科技大學(xué)學(xué)報,2006,(6).

[6] 何畏,汪榮貴,查全民.一種新的快速移動單模式匹配算法[J].合肥工業(yè)大學(xué)學(xué)報,2010,(5).

[7] 金博,史彥軍,滕弘飛.基于語義理解的文本相似度算法[J].大連理工大學(xué)大學(xué)報,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].華中科技大學(xué)學(xué)報:自然科學(xué)版(增刊),2005,33.