汉字自动拆分原理

引言

基于汉字编码的输入方案是用户向计算机中输入汉字的重要渠道。在一个典型的输入方案制作过程中，作者首先根据一定的规则完成给定字集下汉字的手动拆分，得到一张「拆分表」，然后将字根在键盘上进行布局，得到最终的编码。这样做的不便之处是显而易见的：

• 初次拆分需要消耗大量人力；
• 增减字根需要进行大量调整；
• 无法自由改变拆分规则；
• 人工拆分导致了很多汉字拆分的随意性，导致用户难以快速掌握。

因此，一种高效通用的自动拆分方法将有利于汉字编码输入方案的发展。下面我们将从理论上给出一种可能的自动拆分算法。为简化问题，我们假定我们所处理的拆分以笔画为最小单位。

汉字自动拆分系统原理

拆分三要素

定义 (笔画) 由一段或多段曲线首尾相接组成的几何图形，通常记作 $s$。

定义 (汉字) 由一个或多个笔画在平面上按一定顺序在给定位置上排布组成的几何图形，通常记作 $c$。本文中「汉字」特指 GB 字集内的汉字。

定义 (笔画序列) 汉字 $c$ 所包含的笔画形成的序列 $\operatorname{str}c=(s_1,s_2,\cdots,s_n)$。

定义 (切片) 由汉字 $c$ 中的一个或多个笔画在平面上按一定顺序在给定位置上排布组成的几何图形，且这一顺序与汉字 $c$ 的笔顺相同。记由第 $i_1,\cdots,i_n$ 个笔画构成的切片为 $p_i=c[i_1,\cdots,i_n]$，我们同样定义它的笔画序列为

$$\operatorname{str}(c[i_1,\cdots,i_n])=(s_{i_1},\cdots,s_{i_n})$$

定义 (拆分) 给定汉字 $c$，我们称由 $k$ 个切片构成的 $k$ 元组 $d=(p_1,\cdots,p_k)$ 是一个拆分，当且仅当任两个切片无共同笔画，且所有切片所含的笔画的并集等于汉字 $c$ 的所有笔画。

定义 (拆分集) 给定汉字 $c$，由所有可能拆分 $d$ 构成的集合 $D$。

拆分第一要素：字根集

定义 (字根) 我们指定某些汉字以及某些汉字的切片作为字根，通常记作 $r$。

定义 (字根集) 所有我们指定的字根构成一个集合 $R$。

拆分第二要素：退化映射

定义 (退化映射) $\mathcal O$ 将一个切片或一个字根映射为含有较少信息的对象，且满足：

$$\forall r_1,r_2\in R,r_1\ne r_2\Rightarrow \mathcal O(r_1)\ne \mathcal O(r_2)$$

即 $\mathcal O$ 在字根集 $R$ 上是单射。

定义 (可行拆分集) 给定汉字 $c$，它的拆分集是 $D$，则它的可行拆分集 $W$ 定义为：

$$W=\{d|d\in D;\forall p\in d, \exists r\in R\text{ s.t. }\mathcal O(r)=\mathcal O(p)\}$$

即：对于该拆分中的每一个切片，都存在一个字根使得该字根退化后得到的对象与该切片退化后得到的对象一致。

拆分第三要素：择优函数

定义 (择优函数) 给定汉字 $c$ 和它的可行拆分集 $W$，我们可以给 $W$ 中的每一个拆分指定一个实数，由此确定的映射为 $\mathcal H$。我们进一步要求这个映射是单射。

$$\mathcal H:W\to\mathbb R$$

拆分三要素完全决定了一个字的拆分结果

定义 (汉字集) 设我们感兴趣的所有汉字构成一个集合 $C$。

定义 (字根集的扩展集) 由任意多个字根构成的序列所构成的集合 $R^+$。

给定一个汉字 $c$，我们首先获得它的拆分集 $D$，再根据字根集 $R$ 和退化映射 $\mathcal O$ 确定可行拆分集 $W$。注意：可行拆分集中，每一个拆分中的每一个切片都与恰好一个字根关于退化映射有相同的像，因此每一个拆分都对应着一个「多个字根构成的序列」。又因为每一个拆分都被指定了一个不同的实数，我们总能找到数最大的一个拆分。上述讨论证明了我们能够建立这样的映射：

定义 (拆分映射) 拆分映射 $\mathcal D$ 是一个汉字集 $C$ 到字根集的扩展集 $R^+$ 的映射，这个映射的像由每一个汉字 $c$ 的可行拆分集 $W$ 上择优函数取最大值的拆分确定。

$$\mathcal D:C\to R^+$$

笔画的代数表示

数学知识准备

定义 (二维参数曲线) 设参数 $t$ 的取值范围是 $[a,b]$，在该范围内存在两个函数关系 $x(t)$ 和 $y(t)$，我们记二维向量函数 $\mathbf b(t)=(x(t),y(t))$，则当 $t$ 从 $a$ 变化到 $b$ 时，向量函数所代表的平面上的点将绘制出 $xOy$ 平面上的一条曲线，我们称为参数曲线。

Bezier 曲线

Bezier 曲线是一类用于计算机绘图的平滑曲线。我们记二维平面上的点为 $\mathbf P=(x,y)$，则一次 Bezier 曲线可以表示为：

$$\mathbf b_1(t)=\mathbf P_1(1-t)+\mathbf P_2t\qquad 0\le t\le 1$$

它的几何直观是：$t=0$ 时，函数位于 $\mathbf P_1$ 处，而 $t=1$ 时，函数位于 $\mathbf P_2$ 处，且它是连接 $\mathbf P_1,\mathbf P_2$ 的一条直线。

同理，二次 Bezier 曲线可以表示为：

$$\mathbf b_2 ( t ) = ( 1 - t ) ^ { 2 }\mathbf P _ { 1 } + 2 ( 1 - t ) t\mathbf P _ { 2 } + t ^ { 2 }\mathbf P _ { 3 }\qquad0\le t\le 1$$

Bezier 曲线的切向量

参数曲线在某一点的切向量由它的导函数在该点取值给出。具体来讲，一次 Bezier 曲线的切向量是

$$\mathbf b_1'(t)=\mathbf P_2-\mathbf P_1$$

也即它的切向量的方向就是直线本身。二次 Bezier 曲线的切向量是

$$\mathbf b_2 ^ { \prime } ( t ) = 2 ( 1 - t ) \mathbf P _ { 0 } +2(1-2t)\mathbf P _ { 1 } + 2 t \mathbf P _ { 2 }$$

Bezier 曲线与参数插值

现在我们反过来考虑：给定平面上的三个点，如何求得过三点的二次 Bezier 曲线？

我们记这三个点中起点为 $\mathbf P_0$，终点为 $\mathbf P_2$，经过点为 $\mathbf P_c$，现在要求点 $\mathbf P_1$，使得由 $\mathbf P_0,\mathbf P_1,\mathbf P_2$ 三点所确定的 Bezier 曲线经过 $\mathbf P_c$。经过一定的推导，$\mathbf P_1$ 由以下公式给出：

$$\mathbf P_{1}=\mathbf P_c-\frac{1}{2} \sqrt{\left|\mathbf P_{0}-\mathbf P_{c}\right|\left|\mathbf P_{2}-\mathbf P_{c}\right|}\left[\frac{\mathbf P_{0}-\mathbf P_{c}}{\left|\mathbf P_{0}-\mathbf P_{c}\right|}+\frac{\mathbf P_{2}-\mathbf P_{c}}{\left|\mathbf P_{2}-\mathbf P_{c}\right|}\right]$$

笔画与 Bezier 曲线

根据国标规范，共有 31 种基本笔画，它们可以用一条 Bezier 曲线或多条相接的 Bezier 曲线描述。这一部分详见 Wiki 页面。

从代数表示中获取笔画拓扑信息

先考虑较简单的情况，两个由一条 Bezier 曲线构成的笔画之间的关系。此时我们首先解方程：

$$\mathbf b_i(t_i)=\mathbf b_j(t_j)$$

若求得这样的解，检验是否有 $0\le t_i,t_j\le 1$。

• 若无解，两笔画相离；
• 若有解，且 $t_i,t_j$ 中的一个约等于 0 或 1，那么两笔画相接，一笔画的端位接到另一笔画的中间；
• 若有解，且 $t_i,t_j$ 都约等于 0 或 1，那么两笔画相接，一笔画的端位接到另一笔画的端位；
• 若有解，且上述条件不满足，则两笔画相交。

退化映射初探

退化映射是一种非常重要的看法，它能够将每一个具体的字中的切片转化为抽象的切片，也即在不同字中有微小形变的切片 $p,p', p''\cdots$ 在输入方案的角度来看可以看作是一个字根 $r$。

笔画归类与排序

在 31 种笔画中，有一些笔画从字源上讲是同源的，出于不违反人们的文字习惯考虑，我们可能会将几种不同的笔画归为一个笔画类，例如竖钩和竖可能归为一类。给定一种分类方法，对于笔画 $b$ 来说，我们记它所属的类为 $\operatorname{cat}(b)$。所有笔画类构成一个集合 $X$。

我们现在可以定义一种最简单的退化映射。记切片或字根 $p$ 的笔画序列为 $\operatorname{str}(p)=(b_1,\cdots,b_n)$，则这个映射可以表示为

$$\mathcal O:p\to X^n$$ $$\mathcal O(p)=(\operatorname{cat}(b_1),\cdots,\operatorname{cat}(b_n))$$

实例 假设我们只分横竖撇点折五类，$X=\{1,2,3,4,5\}$，设 $p_1$ 是由「土」的全部笔画构成的切片，$p_2$ 是由「工」的全部笔画构成的切片，则

$$\mathcal O(p_1)=\mathcal O(p_2)=(1,2,1)$$

笔画关系

显然，这种分类是非常粗糙的，我们还需要加入更多信息。我们可以定义一个关系映射，将两个笔画映射到它们之间的关系：

$$\mathcal R:B^2\to R$$

这样我们就可以定义更好一点的退化映射：

$$\mathcal O:P\to X^{n}\times R^{n^2}$$ $$\mathcal O(p)=\left[(\operatorname{cat}(b_1),\cdots,\operatorname{cat}(b_n)),(\mathcal R(b_1,b_1),\cdots,\mathcal R(b_n,b_n))\right]$$

实例 我们记「散（$\odot$）、连（$\oplus$）、交（$\otimes$）」是三种关系，并且笔画和自己没有关系、两个笔画的关系是相互的。则上述的 $p_1,p_2$ 会变为

$$\mathcal O(p_1)=[(1,2,1),(1\otimes2,1\odot3,2\oplus3)]$$ $$\mathcal O(p_2)=[(1,2,1),(1\oplus2,1\odot3,2\oplus3)]$$

可见我们实现了区分。

笔画长度

不过，我们还是区分不开「土」和「士」。为此我们可以给所有同类笔画定义笔画长度序，用 ABCD 标记。然后记「士」为 $p_3$，则我们大致可以写成

$$\mathcal O(p_1)=\rm[(1B,2A,1A),(1\otimes2,1\odot3,2\oplus3)]$$ $$\mathcal O(p_3)=\rm[(1A,2A,1B),(1\otimes2,1\odot3,2\oplus3)]$$

择优函数初探

笔画数量和顺序择优

回顾一下择优函数的定义：将可行拆分集 $W$ 单射到实数集 $\mathbb R$。我们首先将一个字的笔画数计为 $L$，则任何一个字根不可能有 $L+1$ 个笔画。那么我们定义

$$\mathcal H(d)=\sum_{i=1}^k\operatorname{len}(p_i)(L+1)^{-i}$$

就实现了「取大优先」。

字根关系择优

我们可以基于笔画关系定义字根关系。如果两个字根间有笔画相交，则为交；不交但有笔画为连，则为连；其余为散。这样定义出来的映射记为 $\tilde{\mathcal R}(r_1,r_2)$，然后定义发生交、连、散的次数分别为 $u_1,u_2,u_3$。字根数量不可能超过 $L$，所以我们定义

$$\mathcal H(d)=u_1(L+1)^2+u_2(L+1)+u_3+\sum_{i=1}^k\operatorname{len}(p_i)(L+1)^{-i}$$

这样，我们就能把「天」拆成「一大」，把「夫」拆成「二人」。

字根数量择优

例如在有笔顺限制的情况下把「区」拆成「匚乂」，如果我们定义 $\operatorname{len}(d)$ 为其中含字根的个数，那么我们设法把 $\operatorname{len}(d)$ 加入 $\mathcal H$ 中即可。