基于统计自然语言分析的九宫格输入法最优键盘布局

周迪　周晓聪　候婷

摘 要： 九宫格输入法是手机端常用的中文输入法之一，可将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