基于統計自然語言分析的九宮格輸入法最優鍵盤布局

周迪　周曉聰　候婷

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

關鍵詞： 九宮格輸入法; 最優鍵盤布局; 擊鍵次數; 統計自然語言處理; 模擬退火

文章編號： 2095-2163（2021）07-0202-04中圖分類號：TP391.1 文獻標志碼： 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 引 言

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

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

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

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

1 統計自然語言分析

1.1 統計自然語言分析

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

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

1.2 詞頻統計

利用Python編程，對語料庫進行清洗，剔除符號并將文本進行分詞，統計每個詞的頻率，再將詞頻表導出為表格文件。此次搜集的漢語語料庫共有857 276個詞，通過詞頻統計后，最終可得42 535個不同的詞，在考慮詞頻的基礎上得到每個詞平均字數為 1.582個。

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

1.3 平均擊鍵次數計算

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

2 模擬退火和哈希映射

2.1 模擬退火算法

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

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

假設前一個狀態為X（n），狀態變為X（n+1）時，同時系統的能量（平均擊鍵次數）由Y（n）變為Y（n+1），定義系統由Y（n）變為Y（n+1）的接受概率P為：

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

2.2 模擬退火算法的設計

（1）初始化。給定初始溫度T（充分大），產生初始鍵盤布局（初始解狀態n），同時計算當前鍵盤布局平均擊鍵次數為Y（n）。

（2）判斷迭代次數是否達到要求：是，轉（7）;否則轉（3）。

（3）產生新解n′。隨機選擇2個數字鍵，從中各選一個字母，交換（如圖1右所示）。或者將其中一個字母移動到另一個數字鍵上（如圖1左所示），保證移動后每個鍵上的字母數在2～5之間。

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

（5）溫度T逐漸減少。

（6）轉（2）。

（7）退出程序，打印最優鍵盤布局。

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

2.3 哈希映射

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

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

3 布局比較及結果分析

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

鍵盤布局1是目前使用的順序布局，在搜集的語料庫基礎上，統計的平均擊鍵次數為5.892 5，此時的布局如圖4所示。最優鍵盤布局見圖5，平均擊鍵次數為5.866 4。可以看到，使用頻率高的字母p和r分在了不同的鍵上。

4 結束語

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

參考文獻

[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]王曉龍，劉秉權，關毅，等. 數字鍵盤智能拼音漢字輸入方法：中國，CN1556452[P]. 2004-12-22.

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

[5]彭偉. 語料庫和面向統計學的自然語言處理技術分析[J]. 科技創新導報，2019，16（34）：253-254.

[6]楊彥，查建華，周怡，等. 基于模糊綜合法的光伏發電項目風險評價方法及其應用研究[J]. 常州大學學報（自然科學版），2019，31（3）：63-70.

[7]熱西旦·玉素甫. 初中數學維吾爾文教材詞頻統計分析[J]. 語文學刊，2014，（2）：37-38.

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

作者簡介： 周 迪（2002-），女，本科生，主要研究方向：機器學習、集成電路設計、芯片; 周曉聰（2001-），女，本科生，主要研究方向：優化算法、計算科學; 候 婷（2000-），女，本科生，主要研究方向：優化算法、分布式計算與處理。

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

收稿日期： 2021-03-15