周迪　周曉聰　候婷

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

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

文章編號(hào)： 2095-2163（2021）07-0202-04中圖分類號(hào)：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ī)中文文本輸入法，以拼音輸入法為主，鍵盤(pán)主要采用九宮格鍵盤(pán)和26鍵全鍵盤(pán)兩種。其中，九宮格輸入法通常把26個(gè)字母順序放置在2～8這8個(gè)數(shù)字鍵上，每個(gè)鍵上有3～4個(gè)字母，數(shù)字鍵0和1作為它用。由于手機(jī)屏幕大小的限制，26鍵全鍵盤(pán)使用率不如九宮格鍵盤(pán)高。以蘋(píng)果IOS輸入法為例，對(duì)中文輸入不太友好，經(jīng)過(guò)改進(jìn)后采用了九宮格輸入法。

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

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

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

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

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

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

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

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

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

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

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

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

2 模擬退火和哈希映射

2.1 模擬退火算法

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

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

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

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

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

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

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

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

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

（5）溫度T逐漸減少。

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

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

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

2.3 哈希映射

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

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

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

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

鍵盤(pán)布局1是目前使用的順序布局，在搜集的語(yǔ)料庫(kù)基礎(chǔ)上，統(tǒng)計(jì)的平均擊鍵次數(shù)為5.892 5，此時(shí)的布局如圖4所示。最優(yōu)鍵盤(pán)布局見(jiàn)圖5，平均擊鍵次數(shù)為5.866 4。可以看到，使用頻率高的字母p和r分在了不同的鍵上。

4 結(jié)束語(yǔ)

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

參考文獻(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ù)字鍵盤(pán)智能拼音漢字輸入方法：中國(guó)，CN1556452[P]. 2004-12-22.

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

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

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

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

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

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

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

收稿日期： 2021-03-15