算法层

给定任意一个汉字，它要么是一个部件，要么是由几个部件构成的复合体。因此，汉字的自动拆分是一个两步的过程：先将汉字分离为部件，然后再将部件逐一拆分为字根。我们首先研究后者。

部件拆分算法

如前所述，部件由多个笔画构成，这些笔画的顺序可以由《通用规范汉字笔顺规范》或其他规范性文件给出。如果我们能够将这些笔画不重不漏地分为几组，并且每组笔画正好形成一个字根，那么我们就完成了对部件的拆分。例如，部件「天」具有 4 个笔画，可以分为两组：第一组是第 1 笔，第二组是第 2、3、4 笔，分别对应字根「一」和字根「大」，因此「一」「大」就是一个对于「天」的拆分。

我们将这样的笔画组称为部件的一个「切片」。这个名字来自于 Python 等编程语言里对列表的一个操作符。利用这个新的术语，我们可以这样说：如果一个部件能被划分成好几个切片，每个切片都与一个字根等同，那么这就是对部件的拆分。

但是，这引出了两个问题：

1. 汉字字形的变化是非常多样的，如何判断某个切片就等同于某个字根？
2. 将部件不重不漏地分为几个切片的方式有很多种，如何判断哪个是正确的拆分？

这两个问题分别引出了部件拆分算法的两大部分：寻根算法和择优算法。

部件拆分之一、寻根算法

寻根算法的输入是一个部件和一个字根，输出是部件的哪些切片等同于这个字根。如果有多种构成这个字根的方式，就返回多个切片；如果这个部件里的任何切片都没办法构成这个字根，就返回一个空的列表。

例：我们考虑字根「口」 部件「十」不含有字根「口」，返回一个空列表

部件「中」的第 1、2、3 笔的切片可以构成「口」，因此返回这种组合方式

部件「串」的第 1、2、3 笔，或者第 4、5、6 笔的切片都可以构成「口」，所以返回两种组合方式

那么，「中」的第 1、2、3 笔的切片等同于「口」这件事情，如何让计算机自动地推导出来呢？我们设立以下标准：

1. 只有当「部件的切片」中的笔画和「字根」中的笔画依次属于同一类别，才能认为这组笔画构成了这个字根；
2. 只有当「部件的切片」中的笔画两两之间的拓扑关系，和「字根」中的笔画两两之间的拓扑关系相同时，才能认为这组笔画构成了这个字根。

第一条规则的意思是说，「中」的前三笔是「竖、横折、横」，而字根「口」也是「竖、横折、横」，所以才能说「中」的前三笔这个切片就是「口」字根。但只比较笔画的名字肯定不够完善，所以我们还要运用第二条规则，继续比较笔画之间的关系。在「中」字里，第一笔竖和第二笔横折是头碰头相连的，而「口」的第一笔竖和第二笔横折也是头碰头相连的；第二笔横折和第三笔横是尾碰尾相连的，而「口」的第二笔横折和第三笔横也是尾碰尾相连的；诸如此类，直到把每对笔画都比较一遍。因为这些也全部相同，所以我们就认为「中」确实包含「口」这个字根。

规则 1 的细节说明（第一遍看可跳过）

规则 1 要求的「属于同一类别」，是采取的 GF 2001-2001 规定的 31 种笔画类别。但是，我们观察到，当部件参与构成复合体的时候，有的时候它的笔画会发生变化。比如，「可」在构成「歌」的时候，第一个「可」的竖钩变成了竖；「九」在构成「鸠」的时候，竖折弯钩变成了竖折提；诸如此类。这说明笔画似乎不应该区分得这么细致，至少有些笔画之间是存在「规则变体的关系」。以下梳理了所有的规则变体：

1. 「横」作为基本形式，可以变成「提」
2. 「捺」作为基本形式，可以变成「点」
3. 「竖钩」作为基本形式，可以变成「竖」、「横折钩」可以变成「横折」、「竖折折钩」可以变成「竖折折」，「横折折折钩」可以变成「横折折折」；
4. 「竖弯钩」可以变成「竖提」或者「竖弯」、「横折弯钩」可以变成「横折提」或者「横折弯」

所以，在考虑切片和字根的等同性时，这些规则变体之间应该是可以合并处理的。当前拆分系统中接受横变提、捺变点，但对于 (3) (4) 还没有处理，因为「竖」和「竖钩」这对笔画关系比较暧昧。比如，如果「歌」有字根「可」，那「正」是不是有字根「丁」呢？「于」中是不是有字根「十」呢？后三个好像没有那么像，容易造成不直观的拆分结果。所以为了安全起见，这些并没有强制合并，需要找到一种更好的办法来处理。

需要改进的地方：

把不同的规则变体是否合并提供给用户作为一个选项

规则 2 的细节说明（第一遍看可跳过）

由于折画可能包含多个线段，所以笔画之间的关系要归约为线段之间的关系处理。两个线段之间可能是

1. 相交
2. 相连
3. 离散

其中，相连可以进一步分为「前前连」（如厂）、「中前连」（如丁）、后前连（如反的前两笔）等 8 种细节情况，这些都很直观。关于「离散」是否要细分，可以思考下面这个例子：

「再」是否含有字根「巾」？

可以看到，离散关系有进一步细分的必要。目前把离散关系进一步分析为 x 轴上的位置关系和 y 轴上的位置关系，每个轴各 5 种，详情参见 topology.ts。

需要改进的地方：

25 种离散关系分得太细了，需要简化

（以下为程序实现细节，可暂跳过）

在程序的具体实现中，简便起见，我们把每种组合方式都用一个数字来表达。计算这个数字的方式是这样的：假设一个部件含有 N 笔，我们认为它的倒数第一笔的「价值」是 1，倒数第二笔的价值是 2，倒数第三笔的价值是 4，倒数第四笔的价值是 8，依此类推，每往前一笔价值就翻倍，直到第一笔的价值是 2 的 N-1 次方。然后，一个笔画组的价值是它包含的所有笔画之和。（也可以这样理解：如果把笔画组包含或不包含某个笔画看作数字 1 和 0，一个笔画组的价值，就是把这串 1 和 0 看作二进制数的数值。）还是考虑刚才那个例子：

部件「中」有 4 笔，价值分别为 8、4、2 和 1，那么「口」对应前 3 笔，前 3 笔之和是 14，所以寻根算法返回数字 14； 部件「串」有 7 笔，价值分别为 64、32、16、8、4、2 和 1，那么「口」对应第 1、2、3 笔或第 4、5、6 笔，其和分别为 112 和 14，所以寻根算法返回 112 和 14。

部件拆分之二、择优算法

择优算法的输入是一系列可行拆分，输出是最符合规则的那一个。我们经常能够在形码方案的教程中看到「能连不交」「取大优先」这样的规则术语，这样的规则其实就是择优。那么如何把择优算法编码到计算机中呢？

我们可以把择优算法想象成一个多层的结构，每一层是一个「筛子」。例如，这一层的「筛子」是「能连不交」，那么只有那些笔画不相交的拆分方式才能通过这个「筛子」，进入到下一层，而笔画相交的就被筛掉了。当然，如果所有的拆分方式都是相交的或者都是不相交的，那「筛子」就没有区分能力了，它只能把这些方式交给后面的那些筛子继续加以筛选。所以，「筛子」的特点就是：

「筛子」对一众拆分方式分别给出一个打分，只有打分最高的那些才能通过本轮筛选，进入下一轮。很多个「筛子」共同运作，最后给出一个唯一的拆分结果。

「筛子」的思想并非自动拆分系统所独创，很多输入方案都运用这种方式来讲解拆分规则，比如这是三码郑码的教程：https://www.yuque.com/smzm/zhengma/otb32d

目前，系统里有以下几种筛子，下面给出一些定性的描述，不过实现细节还要看 selector.ts。在自动拆分系统中，用户可以自由组合并排序这些筛子，来创建自己的拆分规则。很容易证明，如果「笔顺优先」和「取大优先」这两条规则同时存在于用户定义的规则中，不管它们的顺序如何，那么拆分结果一定是唯一的。

根少优先 length

筛选出拆分出字根数量最少的拆分方式。

取大优先 bias

筛选出使拆分出的第一个字根笔画数量最多的拆分方式。如果有多个拆分方式中第一个字根笔画数量都一样多，那么就再看第二个，等等。

笔顺优先 order

筛选出拆分最符合笔顺的方式。

避免相交 crossing

筛选出字根之间相交次数最少的拆分方式。

避免相连 attaching

筛选出字根之间相连次数最少的拆分方式。

同向笔画优先 orientation

让方向相同的笔画汇聚在同一个字根里。例：「兀」=「一」「儿」，「兰」=「丷」「三」。真码的拆分规则里有这一条。

结构完整 integrity

避免框类部件被拆散。

避免变形字根 distortion

尽量少使用变形字根。

复合体拆分算法

从部件的拆分结果可以推导出复合体的拆分结果。一般来说，复合体的拆分结果就是部件的拆分结果顺次连接起来。不过，如果遇到部件顺序和笔顺不一样的情况，需要特殊处理。例如，如果没有「戊」这个字根，「咸」应该拆成「厂一口丶」，这和先拆部件再连起来的顺序不一样。所以，从部件的拆分结果组装起来的时候，要考虑笔画信息。

需要改进的地方：

支持分部取码等逻辑，例如第一部取一根，第二部取一根（类似张码的取码逻辑）

取码算法

待完成