基于汉字编码的输入方案是用户向计算机中输入汉字的重要渠道。在一个典型的输入方案制作过程中,作者首先根据一定的规则完成给定字集下汉字的手动拆分,得到一张「拆分表」,然后将字根在键盘上进行布局,得到最终的编码。这样做的不便之处是显而易见的:
- 初次拆分需要消耗大量人力;
- 增减字根需要进行大量调整;
- 无法自由改变拆分规则;
- 人工拆分导致了很多汉字拆分的随意性,导致用户难以快速掌握。
因此,一种高效通用的自动拆分方法将有利于汉字编码输入方案的发展。下面我们将 从理论上给出一种可能的自动拆分算法。为简化问题,我们假定我们所处理的拆分以笔画为最小单位。
汉字自动拆分系统原理
拆分三要素
定义 (笔画) 由一段或多段曲线首尾相接组成的几何图形,通常记作 s。
定义 (汉字) 由一个或多个笔画在平面上按一定顺序在给定位置上排布组成的几何图形,通常记作 c。本文中「汉字」特指 GB 字集内的汉字。
定义 (笔画序列) 汉字 c 所包含的笔画形成的序列 strc=(s1,s2,⋯,sn)。
定义 (切片) 由汉字 c 中的一个或多个笔画在平面上按一定顺序在给定位置上排布组成的几何图形,且这一顺序与汉字 c 的笔顺相同。记由第 i1,⋯,in 个笔画构成的切片为 pi=c[i1,⋯,in],我们同样定义它的笔画序列为
str(c[i1,⋯,in])=(si1,⋯,sin)
定义 (拆分) 给定汉字 c,我们称由 k 个切片构成的 k 元组 d=(p1,⋯,pk) 是一个拆分,当且仅当任两个切片无共同笔画,且所有切片所含的笔画的并集等于汉字 c 的所有笔画。
定义 (拆分集) 给定汉字 c,由所有可能拆分 d 构成的集合 D。
拆分第一要素:字根集
定义 (字根) 我们指定某些汉字以及某些汉字的切片作为字根,通常记作 r。
定义 (字根集) 所有我们指定的字根构成一个集合 R。
拆分第二要素:退化映射
定义 (退化映射) O 将一个切片或一个字根映射为含有较少信息的对象,且满 足:
∀r1,r2∈R,r1=r2⇒O(r1)=O(r2)
即 O 在字根集 R 上是单射。
定义 (可行拆分集) 给定汉字 c,它的拆分集是 D,则它的可行拆分集 W 定义为:
W={d∣d∈D;∀p∈d,∃r∈R s.t. O(r)=O(p)}
即:对于该拆分中的每一个切片,都存在一个字根使得该字根退化后得到的对象与该切片退化后得到的对象一致。
拆分第三要素:择优函数
定义 (择优函数) 给定汉字 c 和它的可行拆分集 W,我们可以给 W 中的每一个拆分指定一个实数,由此确定的映射为 H。我们进一步要求这个映射是单射。
H:W→R
拆分三要素完全决定了一个字的拆分结果
定义 (汉字集) 设我们感兴趣的所有汉字构成一个集合 C。
定义 (字根集的扩展集) 由任意多个字根构成的序列所构成的集合 R+。
给定一个汉字 c,我们首先获得它的拆分集 D,再根据字根集 R 和退化映射 O 确定可行拆分集 W。注意:可行拆分集中,每一个拆分中的每一个切片都与恰好一个字根关于退化映射有相同的像,因此每一个拆分都对应着一个「多个字根构成的序列」。又因为每一个拆分都被指定了一个不同的实数,我们总能找到数最大的一个拆分。上述讨论证明了我们能够建立这样的映射:
定义 (拆分映射) 拆分映射 D 是一个汉字集 C 到字根集的扩展集 R+ 的映射,这个映射的像由每一个汉字 c 的可行拆分集 W 上择优函数取最大值的拆分确定。
D:C→R+
笔画的代数表示
数学知识准备
定义 (二维参数曲线) 设参数 t 的取值范围是 [a,b],在该范围内存在两个函数关系 x(t) 和 y(t),我们记二维向量函数 b(t)=(x(t),y(t)),则当 t 从 a 变化到 b 时,向量函数所代表的平面上的点将绘制出 xOy 平面上的一条曲线,我们称为参数曲线。
Bezier 曲线
Bezier 曲线是一类用于计算机绘图的平滑曲线。我们记二维平面上的点为 P=(x,y),则一次 Bezier 曲线可以表示为:
b1(t)=P1(1−t)+P2t0≤t≤1
它的几何直观是:t=0 时,函数位于 P1 处,而 t=1 时,函数位于 P2 处,且它是连接 P1,P2 的一条直线。
同理,二次 Bezier 曲线可以表示为:
b2(t)=(1−t)2P1+2(1−t)tP2+t2P30≤t≤1
Bezier 曲线的切向量
参数曲线在某一点的切向量由它的导函数在该点取值给出。具体来讲,一次 Bezier 曲线的切向量是
b1′(t)=P2−P1
也即它的切向量的方向就是直线本身。二次 Bezier 曲线的切向量是
b2′(t)=2(1−t)P0+2(1−2t)P1+2tP2
Bezier 曲线与参数插值
现在我们反过来考虑:给定平面上的三个点,如何求得过三点的二次 Bezier 曲线?
我们记这三个点中起点为 P0,终点为 P2,经过点为 Pc,现在要求点 P1,使得由 P0,P1,P2 三点所确定的 Bezier 曲线经过 Pc。经过一定的推导,P1 由以下公式给出:
P1=Pc−21∣P0−Pc∣∣P2−Pc∣[∣P0−Pc∣P0−Pc+∣P2−Pc∣P2−Pc]
笔画与 Bezier 曲线
根据国标规范,共有 31 种基本笔画,它们可以用一条 Bezier 曲线或多条相接的 Bezier 曲线描述。这一部分详见 Wiki 页面。
从代数表示中获取笔画拓扑信息