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

摘要

本发明得到了输入效率比顺序布局有明显提升九宫格键盘最优布局方案，主要经过了python编程清洗语料库、统计词频、计算每个布局的平均击键次数等前期预备工作；以平均击键次数为目标函数，将26个字母重新分配到8个数字键上，采用哈希算法判重和模拟退火算法迭代，得到平均击键次数最少的九宫格键盘布局。本发明改变了传统九宫格键盘布局，解决了现有传统九宫格不符合中文输入特点，提高了九宫格输入法中文输入的速率。

说明书

技术领域

本发明属于最优化键盘布局领域，具体涉及统计自然语言处理、退火算法、哈希映射等。

背景技术

现有的手机中文文本输入法，以拼音输入法为主，键盘主要采用九宫格键盘和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等。

在手机中文输入法的改进方面，国内外的一些研究者进行了相关的研究。如MinLin和Andrew Sears以笔画输入法为基础,研究了手机键盘的中文输入效率,他们的研究表明:只需重新设计手机按键上的图标,就能提高手机键盘的中文输入效率。哈尔滨工业大学的王晓龙等发明了数字键盘智能拼音汉字输入方法，自动处理汉字输入过程中的数字键位歧义、拼音组合歧义和同音多字歧义。用户只需输入对应汉字拼音的数字键,系统便根据上下文在整个语句范围内调整相应的汉字,保证汉字语句的正确。在《手机键盘文本输入法研究综述》中，何灿群等从手机键盘文本输入法的改进研究、中文文本输入法的研究、模型预测与评价等多个角度归纳了国内外有关手机键盘文本输入法的研究动态。在此基础上，指出了目前研究存在以下不足：基于西方文字设计的手机键盘不适合中文输入；新的中文输入法在应用上存在诸多不足；大多数手机的键盘改进没有考虑用户的操作特点。提出了今后的研究发展方向：根据用户操作特征以及中文输入特点来优化现有中文手机键盘的设计，对提高中文文本输入绩效具有很高的应用价值和较强的可操作性。

发明内容

本发明的目的是针对现有技术存在的问题，提供一种基于统计自然语言分析的输入效率比顺序排布大大提升的九宫格最优键盘布局，为实现上述目的，本发明采用的技术方案包括以下步骤：

步骤1：统计自然语言分析，自然语言分析即日常生活中使用的语言类型，包括汉语、日语和英语等。通过计算机技术给予自然语言加以处理和运用。通过搜集不同的文本对汉语语料库进行统计，为九宫格最优键盘布局研究提供强有力的数据支撑。想要利用统计自然语言分析，设计出最优的九宫格键盘布局方案，需要对语料库进行清洗和统计词频。词频统计是数据与信息处理、知识挖掘与传播中的中心和基础性工作，只有比较准确地在文章中统计出词及其词频，才能进行下一步的工作。

获取GB2312国标码中一级常用汉字和二级不常用汉字的拼音，进而生成每个词的拼音。得到完整的统计文档后，将候选词按照词频降序排列，统计自然语言处理到此完成。

步骤2：词频统计。利用Python编程，对语料库进行清洗，剔除符号并将文本进行分词，统计每个词的频率并将词频表导出为表格文件。获取GB2312国标码中一级常用汉字和二级不常用汉字的拼音，进而生成每个词的拼音。得到完整的统计文档后，将候选词按照词频降序排列，统计自然语言处理到此完成。

步骤3：了解每个键盘布局平均击键次数的计算方法。对给定的键盘布局，查询每个词中汉字的拼音，再将每个字母转成数字键，得到每个词的击键数字序列。将击键数字序列相同的词作为一组，计算候选词排布。排布方式为每页4行，每行不超过8个汉字。每个词的击键次数为数字序列长度+页码+1。将所有词的击键次数与词频相乘再求和，就是平均击键次数；

步骤4：模拟退火算法。模拟退火算法(SA)包含两个部分即Metropolis算法和退火过程。Metropolis算法就是如何在局部最优解的情况下让其跳出来，是退火的基础。1953年Metropolis提出重要性采样方法，即以概率来接受新状态，而不是使用完全确定的规则，称为Metropolis准则，计算量较低。

假设前一个状态为X(n),状态变为X(n+1)时，同时系统的能量(平均击键次数)由Y(n)变为Y(n+1),定义系统由Y(n)变为Y(n+1)的接受概率P为：

从上式可以看到，如果平均击键次数减小，那么新解状态就被接受(概率为1)，如果平均击键次数增大，就说明系统偏离全局最优值位置更远，此时算法不会立刻将其抛弃，而是进行概率操作：首先在区间[0,1]产生一个均匀分布的随机数t，如果t

在步骤4中，具体的退火算法为：

4.1初始化

首先给定初始温度T(充分大)，产生初始键盘布局(初始解状态n)，同时计算当前键盘布局平均击键次数为Y(n)。

4.2迭代次数是否达到要求，是则转(7)，否则转(3)。

4.3产生新解n′

随机选择两个数字键，从中各选一个字母，交换(如图2右所示)。或者将其中一个字母移动到另一个数字键上(如图2左所示)，保证移动后每个键上的字母数在2-5之间。

4.4模拟退火算法计算是否接受。

对于新布局方案n′，计算其平均击键次数Y(n′)，利用公式(1)判断接受还是拒绝该键盘布局。对于一个给定的键盘布局方案n，计算每个词的拼音输入和候选词选择的击键次数。再根据词频加权计算所有词的平均击键次数,得到Y(n)函数，每次产生新解n′后，通过ΔT＝Y(n′)-Y(n),计算ΔT的大小。

4.5温度T逐渐减少。

4.6转4.2。

4.7退出程序，打印最优键盘布局。

在步骤4中，为避免搜索键盘布局重复，采用哈希映射的方法进行判重。键盘布局与键内字母顺序无关，也与数字顺序无关。因此，先将每个数字键上的字符串排序，再将8个字符串排序后拼接成一个长度为26的字符串，最后求该字符串的哈希值。

定义一个集合容器来存储搜索

有益效果

1、本发明改善了不适合中文的传统九宫格键盘排列，探究了更适合中文语法和词组的键盘布局；

2、本发明能提高文字输入的速度，也可以提高生活的便利程度和工作效率。

附图说明

图1：本发明基于统计自然语言分析的九宫格最优键盘布局中模拟退火算法流程图

图2：本发明基于统计自然语言分析的九宫格最优键盘布局中的键盘布局变换

图3：本发明基于统计自然语言分析的九宫格最优键盘布局中的模拟退火曲线图

图4：本发明基于统计自然语言分析的九宫格最优键盘布局中的非最优键盘布局1

图5：本发明基于统计自然语言分析的九宫格最优键盘布局中的非最优键盘布局2

图6：本发明基于统计自然语言分析的九宫格最优键盘布局中的非最优键盘布局3

图7：本发明基于统计自然语言分析的九宫格最优键盘布局中的最优键盘布局图

图8：候选词示意图

具体实施方式

下面将结合本发明中的附图，对本发明的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动条件下所获得的所有其它实施例，都属于本发明保护的范围。

实施例

基于统计自然语言分析的九宫格最优键盘布局，结合流程图，包括以下步骤：

步骤1：汉语语料库研究。通过搜集不同的文本进行对汉语语料库的统计，为九宫格最优键盘布局研究提供强有力的数据支撑此次搜集的汉语语料库共有857276个词，通过词频统计以后，最终有42535个不同的词，在考虑词频的基础上得到每个词平均字数为1.582个，通过统计自然语言处理的文本片段如图8所示；

步骤2：平均击键次数研究。对于一个给定的键盘布局方案，研究计算平均击键次数；

步骤3：最优键盘布局方案研究。利用模拟退火算法，迭代1000000次，得到最优键盘布局，平均击键次数下降曲线如图3所示。可以得到众多键盘布局及其平均击键次数，比如图4、图5、图6的各个键盘布局的平均击键次数分别为5.8673、5.8666、5.8665；最终得到如图4的平均击键次数为5.8664的最优键盘布局方案，也可以看到该例中频率高的字母p和r分在了不同的键上。