基于遺傳算法的形聲輸入法訓練樣本生成研究與實現(xiàn)

李錕華，段利華，桑志強

（大理學院數(shù)學與計算機學院，云南大理 671003）

基于遺傳算法的形聲輸入法訓練樣本生成研究與實現(xiàn)

李錕華，段利華，桑志強

（大理學院數(shù)學與計算機學院，云南大理 671003）

在用戶利用輸入法練習軟件學習時，輸入法練習軟件使用的訓練樣本設(shè)計是否合理，是影響學習好壞的重要因素。討論以形聲編碼輸入法練習軟件訓練樣本生成作為研究對象，根據(jù)用戶設(shè)定的訓練目標，通過遺傳算法生成符合訓練要求的最優(yōu)訓練樣本，來滿足用戶訓練要求。

輸入法；訓練樣本；遺傳算法

隨著科學技術(shù)的不斷發(fā)展，計算機被廣泛應(yīng)用于人們的生產(chǎn)生活。在我國，計算機應(yīng)用主要圍繞中文信息處理展開，中文信息處理就是通過計算機對漢字的音、形和意等信息進行加工和處理的技術(shù)。使用計算機對中文信息處理時，最基礎(chǔ)和最重要的一個環(huán)節(jié)就是把漢字輸入到計算機中，轉(zhuǎn)換成內(nèi)碼的過程。如果中文信息沒有輸入到計算機中轉(zhuǎn)換成內(nèi)碼，就談不上后期的中文信息處理。

目前，漢字輸入到計算機的方法很多，有基于鍵盤輸入的漢字編碼方案，有基于模式識別的聯(lián)機手寫識別、脫機手寫識別和語音識別等。其中應(yīng)用得最廣泛的是鍵盤輸入法，到2011年為止，國家專利局批準與鍵盤漢字輸入相關(guān)的編碼方案專利為757個。想要更好地掌握和推廣這些鍵盤輸入漢字的編碼方案，目前主要存在以下問題：不同的鍵盤輸入方案，編碼規(guī)則和拆分漢字規(guī)則不一致，導致用戶不便于記憶和使用。這時就需要漢字輸入法練習軟件和輸入法編碼方案設(shè)計同步推出，以便于用戶利用輸入法練習軟件快速掌握該種輸入法。

在設(shè)計輸入法練習軟件時，設(shè)計是否合理，主要看訓練樣本的生成是否具有目標性和智能性。部分練習軟件大都是通過隨機的方法產(chǎn)生訓練樣本，對練習的要求和目標因素不進行考慮，不能更好地為練習者提供個性化的訓練樣本。本文通過形聲漢字編碼輸入法練習軟件樣本生成為研究對象，根據(jù)用戶設(shè)定的訓練目標，利用遺傳算法為形聲編碼輸入法練習軟件生成最優(yōu)化的訓練樣本。

1 形聲漢字編碼方案

形聲漢字編碼方案是一種主要通過漢字筆畫和結(jié)構(gòu)之間的關(guān)系，以及漢字和筆畫部首的讀音組合進行漢字編碼的方案。

1.1 漢字結(jié)構(gòu)劃分 我們把漢字按自然結(jié)構(gòu)劃分為兩類，一類是兩塊字，它包含上下結(jié)構(gòu)、左右結(jié)構(gòu)、內(nèi)外結(jié)構(gòu)3種。如“：類、形”等；另一類為獨體字，其特點是不能再次進行拆分的漢字。如：“大、中”等。

1.2 字塊筆畫的歸類 通過漢字的自然結(jié)構(gòu)劃分為字塊，每個字塊都有首筆畫和次筆畫，如果只有一個筆畫，這首筆畫和次筆畫都用它自身〔1〕。歸類后筆畫分類如下①首筆畫：劃分為斜類（包含撇、捺、點、提4種筆畫）、橫類、豎類（包含豎和折2種筆畫）3類；②次筆畫：劃分為橫（提）、豎、撇、點（捺）、單折、復折6種；③兩筆畫的關(guān)系：首筆畫和次筆畫關(guān)系構(gòu)成交叉型、方框型2種。

1.3 筆畫和鍵盤之間的映射關(guān)系 首筆畫斜分別對應(yīng)鍵盤中的Q至P行、橫分別對應(yīng)鍵盤中的A至L行、豎分別對應(yīng)鍵盤中的Z至M行，次筆畫分別對應(yīng)列及交叉對應(yīng)Q、A、Z列，方框?qū)?yīng)W、S、X列，橫對應(yīng)E、D、C列，豎對應(yīng)R、F、C列，撇對應(yīng)T、G、B列，捺對應(yīng)Y、H、N列，折對應(yīng)U、J、M列，復折對應(yīng)I、K、L列，通過首筆定義行，第二筆定義列，在3×8矩陣中確定一個按鍵位置。

1.4 編碼規(guī)則 兩體字的編碼為：編碼順序為（第一體首筆，次筆）+（第二體首筆，次筆）+（第一體拼音首字母）+（漢字拼音首字母）。

單體字的編碼規(guī)則：順著筆順取3組首筆畫和次筆劃組合+漢字拼音首字母。當組成漢字的編碼長度小于4時，在漢字拼音首字母編碼后加字母“o”表示結(jié)束編碼。

2 傳統(tǒng)輸入法訓練樣本生成

2.1 隨機生成法 用戶運行輸入法練習軟件后，系統(tǒng)統(tǒng)計出練習編碼數(shù)據(jù)庫中記錄數(shù)k，通過隨機函數(shù)在1至k之間隨機選擇，選擇出記錄號后，在數(shù)據(jù)庫中查找對應(yīng)字符生成訓練樣本，提供給用戶進行練習。該方法隨機性因素和不確定因素對訓練樣本生成影響很大，有時出現(xiàn)常用漢字的訓練樣本出現(xiàn)概率低，不常用的漢字訓練樣本出現(xiàn)概率高的現(xiàn)象，不具有智能的特點〔2〕，對訓練樣本無法控制。

2.2 回溯生成法 在用戶進行訓練時，設(shè)定一個訓練要求后，隨機選擇產(chǎn)生一個訓練樣本個體，把每個個體狀態(tài)記錄下來，來分析是否滿足訓練要求，不滿足訓練要求，就釋放該個體，重新進行隨機選擇出滿足訓練要求的個體〔3〕。該方法不足之處在于生成訓練樣本的時間復雜度有時很短，有時很長，甚至有時會出現(xiàn)死機情況，時間復雜度沒有辦法控制。

針對傳統(tǒng)輸入法訓練樣本生成的不足，我們利用遺傳算法，來對形聲輸入法練習軟件的訓練樣本進行生成。

3 基于遺傳算法形聲輸入法訓練樣本生成

遺傳算法是從代表問題可能存在的解集合出發(fā)，選擇解集合作為一個種群，對該種群進行基因編碼，建立基因編碼序，形成一定數(shù)量的染色體。染色體是基因序作為遺傳信息的主要載體，即多個基因的集合組成。第一代種群產(chǎn)生后，按照適者生存和優(yōu)勝劣汰的原則，根據(jù)問題域的適應(yīng)度函數(shù)來選擇基因，通過遺傳算子對染色體中基因序進行選擇、交叉和變異操作，產(chǎn)生出優(yōu)化了的新種群，然后通過適應(yīng)度函數(shù)對種群進行分析，是否達到預先規(guī)定的技術(shù)指標，如果達不到指標，繼續(xù)進化種群，產(chǎn)生下一代新種群，直到求出滿足要求的最優(yōu)化解〔4〕。我們利用遺傳算法，對形聲編碼輸入法練習軟件的訓練樣本進行生成。

3.1 目標特征值 在形聲編碼輸入法練習軟件中，衡量一個用戶掌握該種編碼方案的情況，考慮的因素比較多，我們選擇其中三個主要的指標①速度：反映每個字符用戶訓練時該字符的平均速度特征值；②正確率：反映每個字符用戶練習時鍵入該字符的正確率特征值；③常用度：反映每個字符在實際應(yīng)用中該字符的常用頻率特征值。

當速度越快，正確率越高，常用字輸入越熟練，則反映用戶的練習效果越好。然而速度、正確率和常用度不是編碼自身的特性值，而是通過練習編碼參加練習時對用戶統(tǒng)計得出的特征值，特征值和用戶的實際情況有不可分割的聯(lián)系。首先，我們在學校學生或單位用戶中使用練習軟件，根據(jù)不同學生和用戶進行練習，得到每個字符的統(tǒng)計特征值，對訓練樣本表中特征值進行調(diào)整，作為該形聲編碼初始化特征值，根據(jù)遺傳算法生成新的訓練樣本，又提供給學生或單位用戶進行練習，經(jīng)過實際應(yīng)用證明是可行的。

3.2 遺傳算法編碼選擇 目前常用的有二進制編碼、數(shù)字編碼、灰度編碼和字符編碼等，編碼要求簡單明確，但是在選擇操作、交叉操作和變異操作中又能夠快速精確定位。針對于形聲輸入法練習軟件訓練樣本的生成，我們直接采用形聲漢字數(shù)據(jù)表中的記錄號作為遺傳算法的編碼，它在數(shù)據(jù)表中是一個整數(shù)，又是關(guān)鍵字字段，它和字符是一對一的對應(yīng)關(guān)系，可以進行快速定位。

3.3 遺傳算法適應(yīng)度函數(shù)設(shè)計 適應(yīng)度函數(shù)是否合理是能否找到最優(yōu)解的關(guān)鍵〔5〕。訓練樣本評價指標體系中最重要的指標為速度（用v表示）、正確率（用r表示）和常用度（用u表示），我們通過這三個指標設(shè)計適用度函數(shù)。用戶定義練習目標值，設(shè)定速度（用v′表示）、正確率（用r′表示）和常用率（用u′表示），采用染色體的特征值和目標值之間的差值作為適用度函數(shù)（fx），兩者之間的差值越小，越符合目標要求，通過最小化問題來實現(xiàn)訓練樣本的約束模型，表示為：

通過約束模型，我們得到形聲輸入法樣本生成的適應(yīng)性函數(shù)為：

其中，0.01是對速度指標調(diào)整的系數(shù)，（fx）值越小，解集進化度越高，優(yōu)化度也越高。

3.4 遺傳算子設(shè)計

3.4.2 交換操作 交換操作主要是進行染色體重新組合，將兩個染色體中互相配對的個體按照某種形式實現(xiàn)部分基因個體互換，形成兩個新的染色體過程。常用的交叉算子主要包括單點交叉、多點交叉、均勻交叉、算數(shù)交叉等。在形聲輸入法訓練樣本生成中，我們對于橫、豎、斜三種結(jié)構(gòu)的基因個體進行單點交叉，算法思想如下：①在〔0，1〕區(qū)間內(nèi)產(chǎn)生一個隨機數(shù)R，R小于交換概率Pc；②根據(jù)隨機數(shù)R，在訓練樣本中確定一個交叉點，把兩個基因中交叉點后的個體進行整體交換，產(chǎn)生兩個新的訓練樣本，見圖1。

圖1 染色體交換操作之前

經(jīng)過交叉互換后得到新的群體，見圖2。

圖2 染色體交換操作之后

3.4.3 變異操作 就是將訓練樣本中染色體編碼的某些基因位置上的基因編碼，通過隨機產(chǎn)生變異點，用其他的等位基因進行替換，從而形成一個新的訓練樣本。主要的變異算子有：基本位變異、均勻變異、邊界變異以及非均勻變異。形聲輸入法訓練樣本生成中采用基本位變異法，算法實現(xiàn)如下：①針對訓練樣本中每個基因，產(chǎn)生一個〔0，1〕范圍內(nèi)的一個隨機數(shù)Ri；②Ri和Pm進行比較，如果Ri＜Pm，則該基因為變異點，用其他的等位基因進行替換，如果Ri≥Pm，則該基因不產(chǎn)生變異。

3.5 實驗數(shù)據(jù)結(jié)果與分析 在形聲輸入法訓練樣本生成中，我們利用Visual Basic 2005進行代碼設(shè)計和算法實現(xiàn)，相關(guān)數(shù)據(jù)如下。

圖3 染色體初始化數(shù)據(jù)

3.5.1 實現(xiàn)數(shù)據(jù) 首先，初始化數(shù)據(jù)，產(chǎn)生4個染色體組成第一代種群，每個染色體由15個基因組成，見圖3。其中c1-c15為產(chǎn)生第一代種群的基因，迭代次數(shù)初始化為1，適用函數(shù)的染色體值為0.042，0.053，0.057，0.055。

其次，設(shè)定遺傳算法的參數(shù)。迭代次數(shù)為20，交叉概率0.4，變異概率為0.4，設(shè)置目標速度：60字/分鐘，目標正確率為0.8，目標常用程度：0.8，保留染色體精英數(shù)：4。點擊開始遺傳操作，經(jīng)過20次迭代進化后，生成第21代種群，數(shù)據(jù)見圖4。

圖4 第21代種群數(shù)據(jù)

生成的訓練樣本，見圖5。

圖5 訓練樣本字符

3.5.2 實驗結(jié)果分析 種群4個染色體經(jīng)過20次迭代產(chǎn)生新種群的適應(yīng)性函數(shù)返回值，見圖6。

從4個染色體經(jīng)過20次迭代，經(jīng)過遺傳算法的選擇操作、交叉操作和變異操作，適應(yīng)性函數(shù)的返回值，見表1。

表1 對比數(shù)據(jù)表

從實驗結(jié)果可以看出，種群根據(jù)約束條件，經(jīng)過遺傳算法20次迭代進化，數(shù)據(jù)被優(yōu)化，取得滿足條件的樣本。

4 總結(jié)

在形聲編碼輸入法練習軟件的設(shè)計中，通過遺傳算法生成符合用戶設(shè)定目標合理訓練樣本，提供給用戶進行使用，為用戶快速掌握該種輸入法創(chuàng)造了條件，為漢字編碼的學習和推廣打下良好的基礎(chǔ)。

〔1〕施冰，段利華.基于字塊特征的漢字分類方法〔J〕.大理學院學報，2009，8（4）：22-23.

〔2〕何振亞.自適應(yīng)信號處理〔M〕.北京：科學出版社，2002.

〔3〕薛方，蘇虞磊.基于改進遺傳算法的試卷生成算法研究〔J〕.現(xiàn)代電子技術(shù)，2010（6）：143-148.

〔4〕肖連，崔杜武.基本遺傳算法的試卷生成系統(tǒng)的設(shè)計與實現(xiàn)〔J〕.計算機應(yīng)用，2008，28（5）：1362-1364.

〔5〕沈崇圣.遺傳算法中常用選擇算子在Matlab中的實現(xiàn)〔J〕.上海應(yīng)用技術(shù)學院學報，2003，9（3）：200-202.

〔6〕王凌著.智能優(yōu)化算法及其應(yīng)用〔M〕.北京：清華大學出版社，2001.

Research for Methods Generating Training Samples about Keyboard Exercise Based on Genetic Algorithm

LI Kunhua,DUAN Lihua,SAN Zhiqiang
（College of Mathematics and Computer,Dali University,Dali,Yunnan 671003,China）

When users learn software with input method,it is an important factor whether the training sample design of input method software is reasonable.In this paper,based on the genetic algorithm,phonetic encoding IM software training generation,as a study sample,is studied to generate the best sample that can meet the training requirements set by users.

input method(IM);training samples;genetic algorithms

TP312［文獻標志碼］A［文章編號］1672-2345（2012）04-0014-04

云南省教育廳基金項目（07Y41171）

2011-08-15

2012-01-08

李錕華，副教授，主要從事中文信息處理和人工智能技術(shù)研究.

（責任編輯 袁 霞）