UESTC/test

高效均匀的打字方式

1 题目

由于不同汉字的使用频率和输入方式不同，使用全拼输入法撰写文章时，26个字母键盘的使用频率并不均衡。假设给定一篇中文文章素材（附件文章），使用全拼输入法（不考虑词组缩写）输入这篇文章中的文字。请你评价使用全拼时26字母按键的均衡性和输入效率，并尝试设计一种新的拼写编码方法，使得输入同样文章时按键使用更加均衡、输入更加高效。

具体要求：

给定一篇中文文章（附件中的文章），统计出使用全拼输入法录入这篇文章时26个字母键的使用频率，绘制热力图。
- 输入: 一篇中文文章（附件文章）
- 输出: 录入这篇文章的26字母键使用热力图
设计评价标准来分别评价使用全拼录入这篇文章时的按键使用均衡性和输入效率（请根据个人理解自行定义，建议使用明确的量化指标）。
- 输出: 量化评价标准或方法，以及对全拼输入方案的评价结果
基于你在题目2中制定的标准，尝试在全拼基础上改进打字编码方案，使得输入该文章时字母键的使用更加均衡、输入更加高效，展示改进的结果并分析。
- 输入: 一篇中文文章（附件文章）
- 输出: 新的打字编码方案、新旧方案在均衡性和输入效率方面的对比

2 问题的假设

针对问题的具体内容，为了简化求解思路，本文作出以下假设：

输入文章时使用qwert键盘
输入文章时使用标准指法
只考虑中文文字的输入，排除特殊符号、空格、回车等
输入文章时不出现失误的情况
输入方式为“看打”
假设输入某一读音的编码后，待选字出现概率相等且不相关
键盘反应速度足够快，可以准确识别快速输入时按键的顺序
打字时熟悉编码方案

3 思路

3.1 第一题

3.1.1 问题分析

题目要求求出全拼输入文章时各按键的使用频率。

附件给出文章中包含中文、标点符号、换行空格等，由于本文模型只考虑中文文字的输入，所以首先需要处理附件文章，去掉标点符号等，然后将每个文字处理成对应的拼音，最后根据拼音字符串统计各个字母出现的次数，即可得到各按键使用的频率。

3.1.2 实现

以下为实现思路的部分细节

去标点符号将文章读入作为字符串后，利用Python的re模块进行正则表达式匹配即可提取出所有的中文。中文字符在unicode的编码范围为*[\u4e00-\u9fa5]*，故可用unicode编码匹配出中文。
中文->拼音利用库pypinyin实现。该库可将中文转换成对应拼音的列表。

3.2 第二题

3.2.1 问题分析

题目要求设计评价准则来量化均衡性和输入效率。

对于均衡性，首先应该考虑到“均衡”和“平均”的差异。平均是指不考虑分配对象的任何特质或属性，只追求数字上的一致，比如忽略男女身体素质的差异，分配给每个人同样多的食物。对于部分抽象问题，平均是有一定意义的，但对于本文讨论的文字输入等现实问题，仅“平均”显然是不合理的，应该考虑到分配对象的性质。那么什么性质可以作为分配的参考呢，本文提出了==基于手指灵活性的均衡性评价准则==。依据常识，人左右手的十个手指具有不同的灵活性，对于按键输入的问题，分配给相对较灵活的手指更多的输入量是非常合理的。

对于输入效率，针对同一篇文章，效率的最直观的表示即是时间。而时间会受到许多不同因素的影响，由于本文所有讨论均是以上文提到的手指灵活性作为基础，所以按键的距离、手指输入顺序等人体工程学问题是需要纳入对时间影响的讨论之中的，除此之外，中文输入的编码方式对于效率也有影响。综合考虑以上两点，本文提出了基于手指灵活性的效率评价准则。

3.2.2 基于手指灵活性的评价准则

基于手指灵活性的均衡性评价准则

该准则由两个部分组成：
1. 根据不同手指的灵活度差异分配的按键数
2. 同一类手指各按键的数量平均度
- 不同手指
  
  文献[1]通过实验，以动作此书的多少和动作准确性的高低作为评价手指灵活性的两个准则，得出量化结果：
  
  右食指：0.9802；右中指：0.9700；右无名指：0.9514；右小指：0.8964 左食指：0.9094；左中指：0.8954；左无名指：0.8815；左小指：0.8388
  
  本文以各类手指左右手灵活度的平均值来代表该类手指的灵活性。
  
  由于该数据并没有量纲，所以不能直接使用其作为评价均衡性的元素之一，但是我们可以得到每类手指相对于另外手指的灵活度差异，差值大则说明分配更多的按键数。
  
  观察数据可知，灵活度数值有明显的上下界，为了使其间的差异更加明显，本文先将灵活度做归一化处理，将其分配在[0, 1]中，再进行依次做差等一系列处理后，根据全文的总按键数（英文字符数），即可得到每个手指理论最佳敲击数，而根据文章可得实际的每个手指敲击数，绘制折线图可以看到每个手指敲击数的变化趋势，实际的变化趋势越接近于理论，该方案就越均衡。对于变化趋势的相似程度，本文使用皮尔逊相关系数量化表示。越大，均衡性越好。
- 同一类手指
  
  针对每一类手指，准则规定，每个按键（英文字母）使用次数越平均越好。也可以说，每类手指中每个按键使用数量离散程度越小，该方案就越均衡。
  
  离散程度的量化方式有很多：极差、标准差、方差、变异系数等等，由于方差、标准差和极差都会被变量的大小影响，所以本文使用变异系数来量化表示离散程度。越小，均衡性好。
综合以上两点，该准则可以表示为：
基于手指灵活性的效率评价准则

该准则由两个部分组成：
1. 人体工程学计算出的输入理论时间
2. 汉字编码方式所影响的输入时寻找正确中文字符的时间
- 人体工程学
  
  为了提高键入文章的速度，通常可以采用以下原则：双手交替击键，食指、中指、无名指、小指的击键频度依次降低，尽量减少同一手指的越排操作等。文献[2]给出了上述原则的量化指标。文献[2]经过实验获取大量数据，处理出了键盘键位相关速度当量表，表中的数据为连续击键的时间相对值，采用向最小值归一，即击键速度最快的键位搭配的击键相对时间为1.0，表纵坐标表示先行键，横坐标表示后续键。部分表格如下图：
获取了文章的拼音后，根据编码顺序，可由上表得到输入该文章所需的时间当量。

为了更加准确得量化值，还需获得上表当量对应的真实时间长度。文献[3]指出，左右手各手指的敲击频率一般均在3-5.5次/秒的范围内，为了获得较为平均的值，本文取4次/秒为右手食指的敲击频率，对照当量表，右手食指连续击键一次（例如J-J、N-N）的时间当量均为1.3，简单计算可的表中每个连续键位所需击键时间。于是可以得到键入一篇文章的大概时间，符号表示为，越小，效率越高。
- 汉字编码方式
  
  在编码方式方面，与输入效率密切相关的因素主要有：易学性、规范性、编码长度、平均码长、重码率，还有文献[4]提出的荷码量等等。
  
  由于本文假设输入时均熟悉编码方式，所以易学性和规范性不在本文考虑范围内。编码长度和平均码长已在体现在输入文章的理论时间中，所以本部分也不予考虑。
  
  荷码量表示编码方案中平均每个编码所对应的汉字或词的个数，可用公式表示为：，其中，L表示荷码量，W表示参加编码的字词总数，C表示编码方案中的编码总数。荷码量反映的是重码率和重码密度的综合情况。荷码量越高，那么键入一个编码备选的汉字就越多，选择的时间就越长。所以荷码量可以转换成选择正确汉字的时间。
  
  但是荷码量与时间并不是呈线性关系。海曼法则指出：选择反应时间应该与单个刺激的平均信息量成线性关系，即，由假设6：输入某一读音的编码后，待选字出现概率相等且不相关，可将上式简化为：，简单取a=0, b=1，可得，越小，效率越高。
综合以上两点，该准则可以表示为：

3.3 第三题

3.3.1 问题分析

题目要求在全拼的基础上改进打字编码方案，使输入该文章时字母键的使用更加均衡、输入更加高效。

显然的，该问题可以看成是一个双目标优化问题，目标分别为：键入该文章的高均衡性、高效率，变量为中文编码方案。

汉字编码类型可分为四种：1.纯音码2.纯形码3.音形码4.数字码。基于全拼，本文选择纯音码作为编码方式。受双拼启发，本文将汉字拼音的编码方式以下述规则拆分为两部分：

由声母和韵母组成的拼音包括整体认读音节（比如：zh-i）拆分成声母和韵母
没有声母的零声母音节（比如：ao）变化为第一个字母加韵母（比如：ao->a-ao），并拆分成第一个字母和韵母
特殊字符er没有声母但本身不是韵母，输入规则规定为e-r

如此便可将每个汉字用两个字母编码表示。音节一共有55个。

根据易得的文章拼音字符串，可通过正则匹配将其转换为以新编码方案组成的新按键字符串。例如：字符w由字母键x打出，字符o由字母键y打出，那么键入字“我”将按下字母键“xy”。得到新的按键字符串后，可传入问题二函数中获得对应的评价。

由以上分析，很容易可以想到利用现代算法以启发式的方式优化编码方案。

3.3.2

在众多现代算法中，性能较好的算法有PSO算法和遗传算法，这两个算法均是为了解决单目标问题而生，如果要用他们解决多目标问题，通常需要对多个目标的适应度函数做处理使其降为一维，常用的方法有平均法、加权法等，但本问题中涉及的两个目标适应度函数数量级差距较大，不适合将其简单平均或加权。于是遗传算法的改进型算法成为首选，它通过对个体进行非支配排序和拥挤度距离计算，可以在多个目标的方向上寻找最优解，其解通常不是一个确定的解而是一组目标侧重不相同的解组成的解集。

对于该算法的详细步骤本文不再赘述，仅根据步骤顺序列出本文采用的方案。本文使用的NSGA2算法流程图如下：

初始化种群

初始化种群有两种方式。

方式一：为了保证每个字母键在种群初始化时都被分配到，反过来将拆分的55个音节分配给26个字母键，分配两圈后还剩3个音节未分配，此时再随机分配字母键给这三个音节。

方式二：简单随机分配。每个音节都是在26个字母范围内随机分配。

经测试，上述两种方法经过优化后结果相差不大，选取哪一种都可以。本文代码中使用的第一种。

交叉算子

算法的选择、交叉、变异算子都与传统的遗传算法相同。

结合题目，本问题可选择的交叉算子主要有以下几种：离散重组、中间重组、线性重组、重排列。离散重组是指，子代个体的每一个位，都从父代个体中对应的位随机选择；中间重组是指，子个体=父个体 + k * (父个体B-父个体A)；线性重组与中间重组类似；重排列中的部分匹配交叉是指随机确定父个体上的两个交叉点，以为匹配点，互换匹配段的部分，得到新的两个个体，重排列其他算子也与此类似。

考虑到编号为0-25的字母键的整数特性，同时为了保证父代的充分交叉，本文采用离散重组的方式生成子代。

变异算子

变异算子通常分为二进制变异、实数变异和序号变异。本文采用序号变异。

序号变异又包括互换变异、逆序变异。互换变异是指随机选择个体基因的两个位点，并交换这两个点；逆序变异是指随机选择两个位点，并点到这两点之间的基因值次序。

本文中，变异操作先进行逆序变异，再进行互换变异。

快速非支配排序和拥挤度计算

非支配排序是指，赋予种群每个个体两个属性，被支配个数与支配的个体集合。并按照的值依次将种群分成多层，层数值越小，该层的个体的性状在种群相对更优秀。

拥挤度排序是指根据给定个体周围的个体密度，对个体进行排序，拥挤度值越高，即该个体在种群中的多样性越好（与他相似的少）。

根据以上两个属性，可以从父子两代的种群中选出更优良的个体组成新一代种群。

其他参数

种群数：种群数大，系统可能更容易找到全局最优解，但种群也不可过大，不然会导致算法运行缓慢。根据经验，本文程序中种群值设为30

交叉概率：为了使父代充分交叉，本文将交叉率设为1

变异概率：变异是遗传算法中非常重要的部分，它可以让种群跳出当前区域，在更大的范围内搜索，寻找全局最优解。本文根据个体的适应度值，采取动态变化的变异率。如果适应值大于平均值，说明该个体优良，以更小的概率变异，以防止破坏种群的优良基因；如果适应值小与平均值，说明该个体相对较差，以更大的概率变异，寻求全局最优。公式如下：