周迪　周曉聰　候婷

摘 要： 九宮格輸入法是手機(jī)端常用的中文輸入法之一，可將26個英文字母按順序布局在8個數(shù)字鍵上，每個鍵上有3～4個字母。然而順序布局顯然不是最優(yōu)的。本文采用統(tǒng)計(jì)自然語言處理計(jì)算鍵盤布局的平均擊鍵次數(shù)，并采用模擬退火算法優(yōu)化，在搜尋鍵盤數(shù)據(jù)時，對其實(shí)行哈希計(jì)算，避免重復(fù)搜索，最終找到九宮格輸入法的最優(yōu)鍵盤布局方案。結(jié)果顯示，本文的最優(yōu)鍵盤布局方案比順序布局的輸入效率明顯提升，可以提高生活的便利程度和工作效率。

關(guān)鍵詞： 九宮格輸入法; 最優(yōu)鍵盤布局; 擊鍵次數(shù); 統(tǒng)計(jì)自然語言處理; 模擬退火

文章編號： 2095-2163（2021）07-0202-04中圖分類號：TP391.1 文獻(xiàn)標(biāo)志碼： A

Optimal keyboard layout of nine-grid

input method based on statistical natural language analysis

ZHOU Di1， ZHOU Xiaocong2， HOU Ting2

（1 College of Internet of Things Engineering， Hohai University， Changzhou Jiangsu? 213022， China;

2 College of Science， Hohai University， Nanjing? 211100， China）

【Abstract】Nine-grid input method is one of the Chinese input methods commonly used in mobile phone terminal. It lays out the 26 English letters in order on eight numeric keys， each with 3～4 letters. However， sequential layout is clearly not optimal. In this paper， statistical natural language processing is used to calculate the average keystroke times of keyboard layout，? Simulated Annealing algorithm is used to optimize the keyboard data， and hash calculation is implemented to avoid repeated search， so as to find the optimal keyboard layout scheme of the nine-grid input method. The results show that the input efficiency of the optimal keyboard layout in this paper is significantly higher than that of the sequential layout， which can improve the convenience of life and work efficiency.

【Key words】nine-grid input method; optimal keyboard layout; keystroke times; statistical natural language processing; Simulated Annealing

0 引 言

現(xiàn)有的手機(jī)中文文本輸入法，以拼音輸入法為主，鍵盤主要采用九宮格鍵盤和26鍵全鍵盤兩種。其中，九宮格輸入法通常把26個字母順序放置在2～8這8個數(shù)字鍵上，每個鍵上有3～4個字母，數(shù)字鍵0和1作為它用。由于手機(jī)屏幕大小的限制，26鍵全鍵盤使用率不如九宮格鍵盤高。以蘋果IOS輸入法為例，對中文輸入不太友好，經(jīng)過改進(jìn)后采用了九宮格輸入法。

出于歷史原因，PC端鍵盤的26個字母并不是按順序排列的。26鍵全鍵盤是根據(jù)電腦鍵盤來布局的，九宮格鍵盤輸入法是按字母表順序排列的。但這種按英文字母順序布局的鍵盤是不合理的，并不適合中文輸入，沒有考慮漢字的頻率分布特征，對漢字拼音輸入的速度具有一定的限制作用。例如漢語拼音中，字母s的使用頻率很高，但卻跟p、q、r共用一個數(shù)字鍵，導(dǎo)致選候選詞時擊鍵次數(shù)太多。且還要選拼音，當(dāng)輸入7426的時候，可能的拼音有pian、piao、qian、qiao、shan、shao等。

在手機(jī)中文輸入法的改進(jìn)方面，國內(nèi)外的一些研究者進(jìn)行了相關(guān)的研究。如Lin 和 Sears等人以筆畫輸入法為基礎(chǔ)， 研究了手機(jī)鍵盤的中文輸入效率， 研究結(jié)論表明： 只需重新設(shè)計(jì)手機(jī)按鍵上的圖標(biāo)， 就能提高手機(jī)鍵盤的中文輸入效率 [1-2]。王曉龍等人[3]發(fā)明了數(shù)字鍵盤智能拼音漢字輸入方法，自動處理漢字輸入過程中的數(shù)字鍵位歧義、拼音組合歧義和同音多字歧義。用戶只需輸入對應(yīng)漢字拼音的數(shù)字鍵，系統(tǒng)便根據(jù)上下文在整個語句范圍內(nèi)調(diào)整相應(yīng)的漢字，保證漢字語句的正確。在《手機(jī)鍵盤文本輸入法研究綜述》中，何燦群等人[4]從手機(jī)鍵盤文本輸入法的改進(jìn)研究、中文文本輸入法的研究、模型預(yù)測與評價等多個角度歸納了國內(nèi)外有關(guān)手機(jī)鍵盤文本輸入法的研究動態(tài)。在此基礎(chǔ)上，指出了目前研究存在以下不足：基于西方文字設(shè)計(jì)的手機(jī)鍵盤不適合中文輸入;新的中文輸入法在應(yīng)用上存在諸多不足;大多數(shù)手機(jī)的鍵盤改進(jìn)沒有考慮用戶的操作特點(diǎn)。此外，又提出了今后的研究發(fā)展方向：根據(jù)用戶操作特征以及中文輸入特點(diǎn)來優(yōu)化現(xiàn)有中文手機(jī)鍵盤的設(shè)計(jì)，對提高中文文本輸入績效具有很高的應(yīng)用價值和較強(qiáng)的可操作性。

本文用統(tǒng)計(jì)自然語言方法考慮了漢語的詞頻，將26個字母重新布局到數(shù)字鍵上。采用模擬退火優(yōu)化，找到了最優(yōu)鍵盤布局。顯著提高了中文輸入法效率。

1 統(tǒng)計(jì)自然語言分析

1.1 統(tǒng)計(jì)自然語言分析

自然語言[5]，是日常生活中使用的語言類型，包括漢語、日語和英語等。通過計(jì)算機(jī)技術(shù)對自然語言加以處理和運(yùn)用，整體上可歸屬于人工智能和語言領(lǐng)域的分支學(xué)科。自然語言充當(dāng)語料庫與統(tǒng)計(jì)學(xué)研究領(lǐng)域的主要方向，自然語言處理技術(shù)則旨在完成人類和計(jì)算機(jī)之間的交互[6]。對于語料庫的信息處理和語言學(xué)習(xí)，可以將以統(tǒng)計(jì)學(xué)為基礎(chǔ)的自然語言處理技術(shù)作為重要方式，從而獲得信息數(shù)據(jù)的來源，提取主要語料庫信息，得到多種知識。

通過搜集不同的文本對漢語語料庫進(jìn)行統(tǒng)計(jì)，為九宮格最優(yōu)鍵盤布局研究提供強(qiáng)有力的數(shù)據(jù)支撐。想要利用統(tǒng)計(jì)自然語言分析，設(shè)計(jì)出最優(yōu)的九宮格鍵盤布局方案，就要對語料庫進(jìn)行清洗和統(tǒng)計(jì)詞頻。詞頻統(tǒng)計(jì)[7]是數(shù)據(jù)與信息處理、知識挖掘與傳播中的中心和基礎(chǔ)性工作，只有比較準(zhǔn)確地在文章中統(tǒng)計(jì)出詞及其詞頻，才能進(jìn)行下一步的工作。

1.2 詞頻統(tǒng)計(jì)

利用Python編程，對語料庫進(jìn)行清洗，剔除符號并將文本進(jìn)行分詞，統(tǒng)計(jì)每個詞的頻率，再將詞頻表導(dǎo)出為表格文件。此次搜集的漢語語料庫共有857 276個詞，通過詞頻統(tǒng)計(jì)后，最終可得42 535個不同的詞，在考慮詞頻的基礎(chǔ)上得到每個詞平均字?jǐn)?shù)為 1.582個。

獲取GB2312國標(biāo)碼中一級常用漢字和二級不常用漢字的拼音，進(jìn)而生成每個詞的拼音。得到完整的統(tǒng)計(jì)文檔后，將候選詞按照詞頻降序排列，統(tǒng)計(jì)自然語言處理到此完成。以初始鍵盤為例，通過統(tǒng)計(jì)自然語言處理的文本片段見表1。

1.3 平均擊鍵次數(shù)計(jì)算

對給定的鍵盤布局，查詢每個詞中漢字的拼音，再將每個字母轉(zhuǎn)成數(shù)字鍵，得到每個詞的擊鍵數(shù)字序列。將擊鍵數(shù)字序列相同的詞作為一組，計(jì)算候選詞排布。排布方式為每頁4行，每行不超過8個漢字。每個詞的擊鍵次數(shù)為數(shù)字序列長度+頁碼+1。將所有詞的擊鍵次數(shù)與詞頻相乘再求和，就是平均擊鍵次數(shù)。

2 模擬退火和哈希映射

2.1 模擬退火算法

模擬退火算法（Simulated Annealing，SA）[8]思想是在1997年由Steinbrunn 等人首次提出。 這是一種基于 Monte-Carlo迭代求解策略的隨機(jī)尋優(yōu)算法， 在局部最優(yōu)解的情況下能概率性地跳出，并最終趨于全局最優(yōu)。

模擬退火算法（SA）包含2個部分，即：Metropolis算法和退火過程。其中，Metropolis算法就是如何在局部最優(yōu)解的情況下讓其跳出來，是退火的基礎(chǔ)。1953年，Metropolis提出重要性采樣方法，即以概率來接受新狀態(tài)，而不是使用完全確定的規(guī)則，稱為Metropolis準(zhǔn)則，計(jì)算量較低。

假設(shè)前一個狀態(tài)為X（n），狀態(tài)變?yōu)閄（n+1）時，同時系統(tǒng)的能量（平均擊鍵次數(shù)）由Y（n）變?yōu)閅（n+1），定義系統(tǒng)由Y（n）變?yōu)閅（n+1）的接受概率P為：

從式（1）可以看到，如果平均擊鍵次數(shù)減小，那么新解狀態(tài)就被接受（概率為1），如果平均擊鍵次數(shù)增大，就說明系統(tǒng)偏離全局最優(yōu)值位置更遠(yuǎn)，此時算法不會立刻將其拋棄，而是進(jìn)行概率操作：首先在區(qū)間[0，1]產(chǎn)生一個均勻分布的隨機(jī)數(shù)t，如果t

2.2 模擬退火算法的設(shè)計(jì)

（1）初始化。給定初始溫度T（充分大），產(chǎn)生初始鍵盤布局（初始解狀態(tài)n），同時計(jì)算當(dāng)前鍵盤布局平均擊鍵次數(shù)為Y（n）。

（2）判斷迭代次數(shù)是否達(dá)到要求：是，轉(zhuǎn)（7）;否則轉(zhuǎn)（3）。

（3）產(chǎn)生新解n′。隨機(jī)選擇2個數(shù)字鍵，從中各選一個字母，交換（如圖1右所示）?；蛘邔⑵渲幸粋€字母移動到另一個數(shù)字鍵上（如圖1左所示），保證移動后每個鍵上的字母數(shù)在2～5之間。

（4）模擬退火算法計(jì)算是否接受。對于新布局方案n′，計(jì)算其平均擊鍵次數(shù)Y（n′），利用公式（1）判斷接受、還是拒絕該鍵盤布局。對于一個給定的鍵盤布局方案n，計(jì)算每個詞的拼音輸入和候選詞選擇的擊鍵次數(shù)。再根據(jù)詞頻加權(quán)計(jì)算所有詞的平均擊鍵次數(shù)，得到Y(jié)（n）函數(shù)，每次產(chǎn)生新解n′后，通過ΔT=Y（n′）-Y（n），計(jì)算ΔT的大小。

（5）溫度T逐漸減少。

（6）轉(zhuǎn)（2）。

（7）退出程序，打印最優(yōu)鍵盤布局。

至此，研究中給出了算法程序流程如圖2所示。

2.3 哈希映射

在模擬退火過程中，為避免搜索鍵盤布局重復(fù)，采用哈希映射（Hash Map）的方法進(jìn)行判重。鍵盤布局與鍵內(nèi)字母順序無關(guān)，也與數(shù)字順序無關(guān)。因此，先將每個數(shù)字鍵上的字符串排序，再將8個字符串排序后拼接成一個長度為26的字符串，最后求該字符串的哈希值。

定義一個集合容器來存儲搜索[XC周迪6]的鍵盤布局哈希值。對于一個新的鍵盤布局，先計(jì)算其哈希值，然后在集合中查找是否已有。如果已有，則繼續(xù)產(chǎn)生一個新的鍵盤布局;否則將該哈希值放入集合，并用模擬退火算法判斷是否接受該鍵盤布局。

3 布局比較及結(jié)果分析

利用模擬退火算法，迭代100萬次，得到最優(yōu)鍵盤布局，平均擊鍵次數(shù)下降曲線如圖3所示。

鍵盤布局1是目前使用的順序布局，在搜集的語料庫基礎(chǔ)上，統(tǒng)計(jì)的平均擊鍵次數(shù)為5.892 5，此時的布局如圖4所示。最優(yōu)鍵盤布局見圖5，平均擊鍵次數(shù)為5.866 4?？梢钥吹剑褂妙l率高的字母p和r分在了不同的鍵上。

4 結(jié)束語

本文利用統(tǒng)計(jì)自然語言分析和模擬退火算法，以平均擊鍵次數(shù)為目標(biāo)函數(shù)，采用模擬退火算法，將26個字母重新分配到8個數(shù)字鍵上，得到了九宮格鍵盤最優(yōu)布局方案。該鍵盤布局方案比順序布局的輸入效率有明顯提升。

參考文獻(xiàn)

[1]MACKENZIE S， KOBER H， SMITH D. LetterWise：Prefix-based disambiguation for mobile text imput[C]//U1ST 2001.Orlando：ACM，2001：111-120.

[2]RAN H， SKIENA S S. Dialing for documents：An experiment in information theory[J].Journal of Visual Languages& Computing，1996，7（1）：79-95.

[3]王曉龍，劉秉權(quán)，關(guān)毅，等. 數(shù)字鍵盤智能拼音漢字輸入方法：中國，CN1556452[P]. 2004-12-22.

[4]何燦群， 魏秀潔， 葛列眾. 手機(jī)鍵盤文本輸入法研究綜述[J]. 科技導(dǎo)報(bào)， 2012，30（1）：76-79.

[5]彭偉. 語料庫和面向統(tǒng)計(jì)學(xué)的自然語言處理技術(shù)分析[J]. 科技創(chuàng)新導(dǎo)報(bào)，2019，16（34）：253-254.

[6]楊彥，查建華，周怡，等. 基于模糊綜合法的光伏發(fā)電項(xiàng)目風(fēng)險(xiǎn)評價方法及其應(yīng)用研究[J]. 常州大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，31（3）：63-70.

[7]熱西旦·玉素甫. 初中數(shù)學(xué)維吾爾文教材詞頻統(tǒng)計(jì)分析[J]. 語文學(xué)刊，2014，（2）：37-38.

[8]何寒娜，方芳，王偉，等. 改進(jìn)模擬退火遺傳算法的3D NoC低功耗映射[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2019，31（4）：681-688.

作者簡介： 周 迪（2002-），女，本科生，主要研究方向：機(jī)器學(xué)習(xí)、集成電路設(shè)計(jì)、芯片; 周曉聰（2001-），女，本科生，主要研究方向：優(yōu)化算法、計(jì)算科學(xué); 候 婷（2000-），女，本科生，主要研究方向：優(yōu)化算法、分布式計(jì)算與處理。

通訊作者： 周曉聰Email： sailinwei@hhu.edu.cn

收稿日期： 2021-03-15