李錕華，段利華，桑志強(qiáng)

（大理學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，云南大理 671003）

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

李錕華，段利華，桑志強(qiáng)

（大理學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，云南大理 671003）

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

輸入法；訓(xùn)練樣本；遺傳算法

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

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

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

1 形聲漢字編碼方案

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

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

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

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

1.4 編碼規(guī)則 兩體字的編碼為：編碼順序?yàn)椋ǖ谝惑w首筆，次筆）+（第二體首筆，次筆）+（第一體拼音首字母）+（漢字拼音首字母）。

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

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

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

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

針對(duì)傳統(tǒng)輸入法訓(xùn)練樣本生成的不足，我們利用遺傳算法，來(lái)對(duì)形聲輸入法練習(xí)軟件的訓(xùn)練樣本進(jìn)行生成。

3 基于遺傳算法形聲輸入法訓(xùn)練樣本生成

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

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

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

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

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

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

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

3.4 遺傳算子設(shè)計(jì)

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

圖1 染色體交換操作之前

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

圖2 染色體交換操作之后

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

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

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

3.5.1 實(shí)現(xiàn)數(shù)據(jù) 首先，初始化數(shù)據(jù)，產(chǎn)生4個(gè)染色體組成第一代種群，每個(gè)染色體由15個(gè)基因組成，見(jiàn)圖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è)置目標(biāo)速度：60字/分鐘，目標(biāo)正確率為0.8，目標(biāo)常用程度：0.8，保留染色體精英數(shù)：4。點(diǎn)擊開(kāi)始遺傳操作，經(jīng)過(guò)20次迭代進(jìn)化后，生成第21代種群，數(shù)據(jù)見(jiàn)圖4。

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

生成的訓(xùn)練樣本，見(jiàn)圖5。

圖5 訓(xùn)練樣本字符

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

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

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

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

4 總結(jié)

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

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

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

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

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

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

〔6〕王凌著.智能優(yōu)化算法及其應(yīng)用〔M〕.北京：清華大學(xué)出版社，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［文獻(xiàn)標(biāo)志碼］A［文章編號(hào)］1672-2345（2012）04-0014-04

云南省教育廳基金項(xiàng)目（07Y41171）

2011-08-15

2012-01-08

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

（責(zé)任編輯 袁 霞）