pychai 1.0.1
A System for Automatic Chinese Character Decomposition
Requires Python: >=3.6

欢迎使用汉字自动拆分系统「拆」！本文档分为用户文档和开发者文档两部分，您可以首先阅读用户文档，如果对其中具体的实现细节感兴趣，再进一步了解开发者文档。

<center style="font-size: 3em">用户文档</center>

# 一、安装

您可以在 PyPI 上下载汉字自动拆分系统：

```bash
pip3 install pychai
```

该系统依赖 PyYAML，如您尚未安装，将在安装「拆」时自动安装。您也可以通过命令 `pip3 install PyYAML` 手动安装。

# 二、配置文件编写

由于本系统的高度模块化特性，您可以通过编写简单的配置文件的方式来指定一个输入方案的绝大部分信息。让我们以 98 五笔 `wubi98.schema.yaml` 为例进行解说。

## 1 获取示例

您可以用两行简单的程序将本系统的预置方案的配置文件和编码程序调用出来。例如，您可以编写

```python
from Chai import example
example('wubi98')
```

这会将 `wubi98.schema.yaml` 拷贝到您的当前工作目录下。一同拷贝的还有 `wubi98.py`，它是适用于该方案的编码程序，我们现阶段还暂时用不到。

除了传入参数 `wubi98` 之外，您也可以传入 `fingertip`（一个二分风格形码方案）或 `xiaoqing`（一个二笔方案）来获得相应的文件。

## 2 理解 `schema`

配置文件的第一部分是方案基本信息。这一部分不会对方案的制作产生影响，但出于方便交流考虑，建议您留下您的个人信息。例如：

```yaml
schema:
  name: 五笔字型 98 版
  version: "0.1"
  author:
    - 发明人 王永民
    - 重建人 蓝落萧 2320693692@qq.com
  description: |
    用于测试自动拆分
```

---

下面我们来指定方案的拆分规则。

## 3 理解 `degenerator`

`degenerator` 者，中文名曰「退化映射」也。退化映射是本系统最重要的概念，没有之一。这是因为：「拆」的数据库中精确存储了汉字的图形信息，退化映射决定了您希望不同的图形在何种程度上可以被视为同一个字根。例如：

```yaml
degenerator:
  - 笔画序列
  - 笔画拓扑
```

笔画序列的含义是，当待拆分的汉字中含有与给定字根相同的笔画顺序时，我们才能够从该字中拆出给定的字根。例如，对于「月」字根，「用」字中包含该字根，而「青」字中不含有该字根，因为「青」的下部第一笔为「竖」。

笔画拓扑的含义是，在笔画序列的基础上，我们还要进一步考虑笔画之间的关系。例如，「工」和「土」具有完全相同的笔画序列，但「土」的第一二笔为相交关系，「工」为相连关系，它们并不相同。添加「笔画拓扑」之后，这种情况就能够得以区分。

目前，我们仅预设了这两个组件，如果您希望指定更细致的退化映射，请您了解开发者文档并进行相关算法的编写。

## 4 理解 `selector`

`selector` 者，中文名曰「择优函数」也。经过 `degenerator` 处理后，我们得到了汉字的多种可能拆分方式。此时，我们根据一系列规则确定选取哪种拆分方式。例如：

```yaml
selector:
  - 根少优先
  - 笔顺优先
  - 能连不交、能散不连
  - 取大优先
```

- 根少优先，即拆出的字根数应该尽量少。
- 笔顺优先，即拆分应该尽可能符合笔顺。
- 能连不交、能散不连，即拆出的字根应该尽量为「散」关系，其次为「连」关系，最次为「交」关系。
- 取大优先，即拆分出的字根排在前面的笔画应该尽量多。

同样，我们目前仅预设了这四个组件，如果您希望指定更细致的择优函数，请您了解开发者文档并进行相关算法的编写。

值得注意的是，`degenerator` 各组件的顺序对拆分结果无影响，但 `selector` 各组件的顺序对拆分结果有影响。作为实例，请考虑「平」的拆分：给定字根「一、丷、十、干」，若组件的顺序如上，则拆为「干、丷」；若「笔顺优先」调整到最前面，则拆为「一、丷、十」。

那么，我们如何确定我们给出的规则一定能确定唯一的拆分方式呢？对于这个问题我们没有一般的回答，但可以证明，当「笔顺优先」和「取大优先」均出现（不管顺序如何，也不管有什么其他的组件）时，能确定唯一的拆分方式。因此，如果您没有详细地考虑过其余选择方案的唯一性，建议保证包含这两者。

拆分规则至此结束，下面我们来指定方案的字根。

---

## 5 理解 `classifier`

我们注意到，许多方案将汉字的笔画进行了分类，这使得作者和用户可以笼统地掌握笔画而不用掌握每一种情况。在国家标准黑体类字形中，笔画共有 31 种，但绝大多数方案将它们分为 5 至 7 类。最流行的划分方案是国家标准、五笔、二笔等采用的五分法：

```yaml
classifier:
  1: [横, 提]
  2: [竖, 竖钩]
  3: [撇]
  4: [点, 捺]
  5: [横钩, 横撇, 横折, 横折钩, 横斜钩, 横折提, 横折折, 横折弯, 横撇弯钩, 横折弯钩, 横折折撇, 横折折折, 横折折折钩, 
      竖提, 竖折, 竖弯, 竖弯钩, 竖折撇, 竖折折钩, 竖折折, 
      撇点, 撇折, 弯钩, 斜钩]
```

进行分类意味着同一类中的笔画将放置在相同的键位上。

## 6 理解 `mapper`

在这一步，我们将字根映射到指定的键位上。例如：

```yaml
mapper:
  g: [1, 11, 王, 青上, 五, 夫, 夫上, 举下, 年下, 舛右]
  ...
  x: [幺, 双折, 纟, 母, 彖上, 贯上, 弓, 匕, 化右, 比左]
```

这里「键位」不一定需要为实体按键，也可以是虚拟的键名。作为实例，请参考 `fingertip.schema.yaml`。

## 7 理解 `aliaser`

您可能已经注意到了：在 `mapper` 中，字根分为两类：

- 一类为单个字符，如「王」；
- 一类为多个字符，如「年下」；

单个字符所描述的字根就是它本身，而多个字符所描述的字根是非成字字根，可以任意命名。那么，我们何从知道多个字符描述的具体是什么字根呢？这就需要通过「别名注册器」进行注册：

```yaml
aliaser:
  ...
  夫上: [夫, [0, 1, 2]]
  ...
```

这里，我们指定「夫上」是由源字「夫」的第 0 笔至第 2 笔构成的字根（**请注意：这里从 0 开始计数！字的笔画为第 0 笔、第 1 笔、……**）。这样，系统通过结合图形数据，即可知道「夫上」的形状如何了。

请注意，别名注册器所接受的源字必须是一个基本部件，否则将无法识别。为了防止生成码表时出现错误，您可以先用我们提供的测试工具进行测试：

```python
from Chai import lookup
lookup('夫', [0, 1, 2])
```

此时有可能出现三种情况。本例中「夫」是一个基本部件，所以返回成功信息：

```
恭喜！您现在可以为该字根起一个名字，在 mapper 中添加这个字根的名字，并在 aliaser 中注册，语法如下：
【名字】: [夫, [0, 1, 2]]
```

但如果您使用的源字是「规」，虽然规的前三笔也是夫的前三笔，但是它会提示：

```
提供的汉字「规」不是基本部件，它的结构为：[h, 夫, 见]。请尝试将您需要的字根定位到这些基本部件中，然后重新查询。
```

这表明您必须先将字根定位到基本部件中才能进行查询。最后，如果您提供的是一个非 GB 汉字，则本系统无法帮您查询，将提示「您提供的汉字「X」不在 GB 字集内。请您使用常用汉字查询字根。」。

不过，在查看 `wubi98.schema.yaml` 时，您可能注意到，有一部分多个字符描述的字根无需注册。这是因为，这些名称已经是数据库中存储基本部件时使用的名称。您可以参考该方案的 `mapper` 模块找出您所需要的名称，如果没有发现再进行定义。

# 三、码表输出

然而，仅仅编写配置文件并不能满足每个人对于取码编码的不同需求。因此，本系统仍然要求使用者编写一定量的代码（小于五十行）来自定义编码工作。下面我们就来看一下在拆分结束后用户如何取码。

## 1 读入方案

安装好 `Chai.py` 后，我们需要在自己的文件中导入 `Schema` 类，用它读入自己的方案（这里以 `wubi98` 为例），运行拆分：

```python
from Chai import Schema

wubi98 = Schema('wubi98')
wubi98.run()
```

当 `Schema('wubi98')` 执行时，系统会首先查看当前文件夹（也就是这行语句所在的程序所在的文件夹）是否含有 `wubi98.schema.yaml`，如果没有，则在内置文件夹中寻找。由于 `Schema` 是一个类，这个操作相当于实例化一个 `Schema` 对象，我们将其命名为 `wubi98`。

然后，`wubi98.run()` 则代表的是根据配置文件中所包含的拆分规则和字根选取运行拆分。取决于您的字集大小和拆分规则，这一过程可能会耗时 5 至 10 秒。

## 2 `Schema.component` 属性

运行结束后，`wubi98` 对象将会生成一个 `wubi98.component` 属性，它的结构如下：

```python
{
    nameChar1: (objectRoot1, objectRoot2, ...),
    ...
}
```

其中，`nameChar` 是「名义字」，即一个字符串，如 `'的'`。而 `objectRoot1, ...` 则是「对象字根」，它们是自定义类 `Char` 的实例。我们接下来就会看到如何利用这些 `Char` 类对象进行编码。

但在这之前，我们有必要提醒读者：`wubi98.run()` 并没有生成所有字的拆分，而是生成了所有「基本部件」的拆分。例如「里」是一个基本部件，它是 `wubi98.component` 的键之一，但「理」、「锂」等并不在 `wubi98.component` 中。它们的拆法由下面给出的办法定义：

## 3 `Schema.tree` 属性

例如，`wubi98.tree` 的结构如下：

```python
{
    nameChar1: tree1
    ...
}
```

其中 `nameChar` 和上面相同，而 `tree` 则是一个自定义类 `Tree` 的实例。`Tree` 具有如下属性：

- `Tree.name`：字名，例如「理」；
- `Tree.structure`：字的结构，例如「理」为左右结构，代码为 `h`；
- `Tree.first` 和 `Tree.second`：字按该结构进行二分之后，得到的第一部分（如王）和第二部分（如里）。

注意，这些部分仍然是一个 `Tree` 对象，如此不断迭代拆分，直到不可再分（即某一部分为基本部件）为止，此时基本部件对应的 `Tree` 的 `first` 和 `second` 属性均为 `None`，其结构为空。

## 4 顺序风格编码示例

这里，「顺序风格」指的是类似于五笔的顺序取字根的方式。此时，基本部件按顺序拆分，而其他字先表示为基本部件的序列，然后依次取各个部件的拆分，再合并到一起。这种取码方式用代码表达就是：

```python
for nameChar in wubi98.charList:
    if nameChar in wubi98.component:
        scheme = wubi98.component[nameChar]
    else:
        tree = wubi98.tree[nameChar]
        componentList = tree.flatten()
        scheme = sum((wubi98.component[component] for component in componentList), tuple())
```

在这里，我们获得合体字的树后，将其打平（`Tree.flatten()`）为基本部件的列表，它不含有任何嵌套；然后再将各个基本部件的拆分连接起来。显然此时 `scheme` 是一个含有若干「对象字根」的元组。然后：

```python
code = ''.join(wubi98.rootSet[objectRoot.name] for objectRoot in scheme)
```

这里表示，我们取每个对象字根的名字（实际上此时变成了名义字根），然后用 `wubi98.rootSet` 转为编码，就完成了编码。

当然，实际的规则要略为复杂一些，例如我们如何对字根字进行编码呢？假设普通字根字的编码规则为：字根所在键位 + 第一、二、末笔。那么我们可以写：

```python
if len(scheme) == 1:
    objectRoot = scheme[0]
    nameRoot = objectRoot.name
    firstStroke = objectRoot.strokeList[0].type
    secondStroke = objectRoot.strokeList[1].type
    lastStroke = objectRoot.strokeList[-1].type
    info = [nameRoot, firstStroke, secondStroke, lastStroke]
    code = ''.join(wubi98.rootSet[nameRoot] for nameRoot in info)
```

哈！原来一个对象字根（`objectRoot`）不仅有名字属性，还有「笔画序列」（`strokeList`）属性。例如，`objectRoot.strokeList[0]` 就取到了该字的第一笔。每一笔都是一个 `Stroke` 对象，它具有一个 `type` 属性，如「横」，我们将它用 `rootSet` 进行映射，就得到了字根字的编码。

本系统还能轻而易举地完成识别码的添加。具体细节请看 GitHub 仓库中的 `wubi98.py`。

## 5 二分风格编码示例

待续。

## 6 二笔类编码示例

待续。

<center style="font-size: 3em">开发者文档</center>

# 一、汉字自动拆分总论

如果您认真阅读了用户文档，一定会对汉字自动拆分的实现感到惊奇。的确，汉字的形状变化万千，各种编码方案对其的拆分也各不相同，数不胜数，异常复杂。

然而，汉字的可能拆分方式是无穷无尽的吗？我们知道，汉字的笔画数量是有限的，如果我们限制拆分以笔画为最小单位，拆出的字根中每个字根至少包含一个笔画，则汉字的可能拆分方式的数量必然是一个有限大——尽管确实很大——的数。枚举出有限多的拆分方式中，我们再根据确定的规则自动化选取最佳的拆分，就实现了汉字自动拆分。本系统之所以可行，正是基于如此简单的原理。

那么汉字的可能拆分数量大约有多大呢？经过简单的计算，它大约略小于笔画数量的阶乘。一个十笔的字有数十万种拆分，而一个二十笔的字的拆分数量已经超出了任何计算机所能存储的极限。因而如上原理的直接应用又是不可能的。

所幸，基于汉字作为表意文字的特性，绝大多数汉字内在地划分成多个部件（例如形声字、会意字等），部件又可以划分为更小的部件，经过逐级分解之后可以用六七百个基本部件以简单的几何关系组合而成。而对于绝大多数的形码而言，字根数量不过二三百个，所进行的拆分也基本上是针对基本部件的拆分，极少出现一个字根横跨两个基本部件的情况。因此我们引入了本系统最重要的一个假设：

> 分部假设：含有多个部件的汉字的拆分结果，可以近似地由每个部件的拆分结果，以及这些部件相互组合的几何关系决定。

基本部件的笔画数量少，因而对它们进行枚举是可以做到的。由此我们引出了本系统的顶层架构：

1. 基本部件拆分为字根：由于不同编码方案天差地别，为了最大程度满足它们的需求，我们针对基本部件枚举所有可能的拆分，然后以拆分规则筛选出唯一的拆分；
2. 用基本部件确定其他汉字：将其他汉字表示为由基本部件构成的树状结构；
3. 根据「基本部件的拆分」和「其他汉字的树状结构」进行编码。

【这里需要图片】

# 二、基本部件拆分

## 1 「文」数据库简介

基本部件是拆分算法所要处理的对象。处理过程中，我们可能需要用到许多种可能的信息，但任何信息都是可以基于图形信息推导得出的。因此，本系统仅存储最原始的数据，即「这个基本部件是怎么写出来的」。

具体而言，我们：

- 将基本部件表达为多个笔画；
- 将笔画表达为笔画类别和多个绘制命令；
- 每个绘制命令由绘制种类和绘制参数组成，具体可参见 Wiki 页面中的「「文」数据库开发规范」。

```yaml
一:
  - [横, [m, 25, 470], [h, 967]]
丁:
  - [横, [m, 52, 130], [h, 918]]
  - [竖钩, [m, 508, 132], [v, 833]]
```

在程序中，为了实现上述数据的封装，每个笔画由一个 Stroke 对象表示，每个字由一个 Char 对象表示。当我们取一个字的其中一部分笔画构成一个新字时，我们称新字是源字的「切片」，切片也用一个 Char 对象表示。

## 2 退化映射

根据架构，我们首先需要将基本部件拆分为字根。但是，当我们利用上述坐标数据时，我们就面临着一个问题：用户可能希望将不同的字中不同的切片视为同一字根，尽管这些切片的坐标数据不完全一样。例如，「串」中的两个「口」上面的小、下面的大，坐标数据并不相同，但通常用户会将其看作同一字根。如何实现呢？

一种思路是，直接利用上述全部信息，结合人工智能的分类方法进行分类。然而，这将会花费巨大的运算资源（例如，请了解手写数字的神经网络分类模型），于是我们思考的是，上述信息中是否存在某些简单、信息量少的「关键部分」，使得我们仅通过这些关键部分就能有效的区分不同字根？

「拆」为此进行了尝试，将这种对一个切片提取关键信息的函数称为「退化映射」，得到的关键信息称之为「特征」。这样，我们将一个切片经退化映射处理，得到的特征与字根的特征进行比较，如果它的特征与某个字根的特征相等，就可以将它等同于该字根。相反，如果它不与任何字根的特征相等，它就是一个无效切片，不能作为拆分的一部分。

在实际操作中，我们可能会提取多种不同的关键信息，然后将它们组合起来成为一个字的特征。此时每种信息称为一个「域（field）」，生成这个域的函数称为域函数。

为了便于查询，我们计算所有字根的特征，形成一个以特征索引用户字根的字典；此后，每当我们获得了一个基本部件的切片，我们就能取其特征并在字典中查找，查找得到则为有效切片，否则为无效切片。

以下为伪代码：

```python
def degenerator(objectChar):
    '''
    功能：退化函数
    输入：objectChar 是一个 Char 类型的对象，可以是字、字根或切片，里面存储着笔画序列信息
    输出：特征
    '''
    characteristicString = '' # 用字符串表达特征
    for fieldFunction in fieldFunctionList:
        field = fieldFunction(objectChar) # 使用某种域函数，获得一个域
        characteristicString += field # 将域加到特征上
    return characteristicString

def genDegeneracy(rootSet):
    '''
    功能：用于生成用户字根退化字典的函数
    输入：rootSet 字根集，每个字根是一个 Char 对象
    '''
    degeneracy = {} # 一个{退化对象:用户字根}字典
    for objectRoot in rootSet:
        characteristicString = degenerator(objectRoot) # 退化用户字根的对象字
        degeneracy[characteristicString] = objectChar # 写入退化字典
    return degeneracy        
```

## 3 幂字典生成

我们现在讨论：给定一个基本部件，我们可以从其中拆出哪些字根？为了满足不同方案的需求，「拆」采用了比较激进的方案——枚举一个基本部件的所有切片，计算该切片的特征，然后在退化字典中查找它所对应的字根，如果能够找到则标记为有效切片，找不到则标记为无效切片。

那么，一个基本部件最多能形成多少种切片？显然，对于一个 n 笔的字，每个笔画都有取和不取两种状态，因而切片就有 2 的 n 次方种可能性。我们因此可以用 n 个布尔值（即 0 或 1）组成的向量来表达这一切片。例如：

- 设字 c 是含有 5 笔的字，则它的所有切片都可以用一个**含有 5 个布尔值的向量**表达；
- 取字 c 前 2 笔和最后一笔作为一个切片 s，我们对每个笔画将「取」标记为 1，「不取」标记为 0，那么 s 对应的向量应该是 (1, 1, 0, 0, 1)；
- 取完切片 s 之后，余下部分 r 对应的向量应该是 (0, 0, 1, 1, 0)。


进一步抽象之后，我们很自然地联想到可以使用二进制数来表达切片，这样的好处是我们可以通过位运算来快速处理切片。例如：

- 设字 c 是含有 5 笔的字，则它的所有切片都可以用一个**含有 5 个位的二进制数**表达；
- 取字 c 前 2 笔作为一个切片 s，我们对每个笔画将「取」标记为 1，「不取」标记为 0，那么 s 对应的二进制数应该是 11001，转换为十进制数是 25；
- 取完切片 s 之后，余下部分 r 对应的向量应该是 00111，转换为十进制数是 6。

现在，我们就可以通过遍历 1 ~ 2<sup>n</sup>-1 的所有数字来寻找一个字的所有有效切片：

```python
def genPowerDict(objectChar):
    """
    输入：对象字
    输出：幂字典
    """
    objectChar.powerDict = {}
    # 获取对象字的笔画数，我们不妨仍设为 5；
    l = objectChar.charLen
    # 生成掩码列表，<< 为位左移运算，得到的结果为 [10000, 01000, 00100, 00010, 00001]
    mask = [1 << (l-i-1) for i in range(l)]
    for k in range(1, 2**l):
        sliceStrokeList = []
        # 对于每个数 k，我们遍历所有掩码，如果数 k 与某个掩码按位与后不为 0，那么说明该数的这一位为 1，这等价于该切片取了这一位对应的笔画
        for idx, item in enumerate(mask):
            if k & item:
                sliceStrokeList.append(objectChar.strokeList[idx])
        # 根据切片的笔画序列生成一个 Char 对象，然后经过 degenerator 运算获取特征；在退化字典中查找该特征：
        #   - 如果查找到了，则将数 k 及对应的字根作为一个键值对存储在幂字典中；
        #   - 如果查找不到，其值将会记为 None。
        characteristicString = degenerator(Char('', sliceStrokeList))
        objectChar.powerDict[k] = degeneracy.get(characteristicString)
```

现在，幂字典中记录了每个切片分别对应哪个字根（或者不对应任何字根），由此我们可以正式进入一个字的拆分环节。

## 4 可行拆分集生成

在未开始拆分之前，我们将一个字的状态用 2<sup>n</sup>-1 表示，我们将它称为剩余数。每当我们从这个字上取下一个切片时，我们就将这个切片对应的数从剩余数中减去，得到新的剩余数。那么给定任意一个剩余数，我们如何知道从它身上能取下哪些切片呢？

首先，我们要引入一个限定原则（首笔序原则），即拆分得到的字根列表是按它们首笔笔顺排列的。因此，在每次从没有拆完的部分中取切片的过程中，必须取到该部分的第一笔。例如，第一次拆分时必须取到该字的第一笔。

```python
def nextRoot(n):
    '''
    给出从剩余数中取下一个切片的可能性列表，每个切片都应该包含该部分的第一笔
    '''
    powerList = [0]
    # 这里我们假设剩余数 n 为 00110，那么我们每次考虑 n 的一个非零位（即剩余部分的一个笔画，计算
    while n: # 直到当前序列所有「1」位都被置0之前，做：
        t = n & (n-1) # n - 1 = 00101，位与运算得到 t = 00100，含义是删除剩余部分的最后一笔
        m = n - t # m = 00010，含义是剩余部分的最后一笔
        powerList += [x + m for x in powerList] # 该笔画可取可不取，所以列表应该扩增为原来的两倍，前一半不含该笔画，后一半含有该笔画，这里我们得到 [0, 10]
        n = t # 将 00100 设为
    # 经过两次迭代，powerList 变为 [0, 10, 100, 110]，这恰好是从剩余数 00110 中所能取出的所有切片，又因为首笔序的限制，必须取到第一笔，所以我们删除这个列表中的前一半
    return powerList[len(powerList)//2:]
```

所以，拆分算法可以概括为：

- 建立两个列表记录拆分状态，一个为未完成列表，一个为完成列表，向未完成列表中加入初始值 (2<sup>n</sup> - 1)，即将整个部件作为一个剩余数；
- 取未完成列表中的某个拆分，将它的最后一个数（即剩余数）经由 `nextRoot` 函数处理，得到所有可能切片，用幂字典检验它们的有效性，如果无效则予以剔除，有效则保留；
- 如果切片恰好等于剩余数，说明这个基本部件被拆完了，我们将它添加到已完成列表中；否则用剩余数减去新切片，将它添加到未完成列表中，形成堆栈；
- 重复上述过程，直到未完成列表全部被清空。

```python
def genSchemeList(objectChar):
    '''
    形成包含所有可能拆分的列表
    '''
    l = objectChar.charlen
    # 建立两个列表记录拆分状态
    uncompletedList = [(2**l - 1, )] # 未拆完的拆分会留在这里，当这个列表不是空列的时候，迭代继续
    completedList = [] # 完成了的拆分会移动到这里，作为最后的输出
    while uncompletedList: # 当未拆完列表非空时，做：
        newUncompletedList = []
        for scheme in uncompletedList: # 对于每个未拆完的拆分
            residue = scheme[-1] # 选取最后一个对象，实际上即是「剩余」
            nrList = nextRoot(residue) # 找到所有可能的切片
            # 利用powerDict过滤出所有有效切片（无效切片的值是None，被滤除，参考genPowerDict）
            rootList = list(filter(lambda x: objectChar.powerDict[x], nrList)) 
            for root in rootList: # 对于每个有效切片
                if root != residue: # 如果跟「剩余」非等大，即还没拆完
                    newUncompletedList.append(scheme[:-1] + (root, residue - root)) # 扩张一个拆分
                else: # 新拆出的字根和原有剩余一样大，说明已拆完
                    completedList.append(scheme) # 移动到拆完列中
        uncompletedList = newUncompletedList
    objectChar.schemeList = completedList # 返回给对象字
```

## 5 择优函数

通过上面的流程，我们不难理解，实际上可能的拆分有很多，如何获取我们目标要求的那个，这就是择优函数需要做的事情。

择优函数应该如何表达？我们知道，大多数形码方案会提出几条拆分规则，例如「根少优先」等等。用数学的语言表达，每条规则定义了一个函数，这个函数的作用对象是拆分方案，而其作用结果是给出一个可比较的对象（例如整数或实数），在所有的拆分方案中只有取到最大值或最小值的才能通过此轮筛查，其余将被筛去。

例如，我们得到了 10 个拆分方案，令「根少优先」所定义的函数作用于这 10 个拆分方案时，我们得到其中 3 个方案将字拆为 2 个字根，5 个方案将字拆为 3 个字根，2 个方案将字拆为 4 个字根。那么，我们发现最小值为 2，筛去所有不为 2 个字根的拆分方案，剩余 3 个拆分方案；然后我们再应用其他规则处理剩余的 3 个方案直到唯一为止。

我们形象地将每个这样的函数称为「筛（sieve）」。

以下为伪代码：

```python
def selector(objectChar):
    # 对于每个筛，对拆分方案的列表进行过滤使得只保留那些函数值取到最小值的拆分
    for sieve in sieveList:
        evalList = [sieve(objectChar, scheme) for scheme in objectChar.schemeList]
        bestEval = min(evalList)
        objectChar.schemeList = list(filter(lambda scheme: sieve(objectChar, scheme) == bestEval, objectChar.schemeList))
    # 理论上经过选择器序贯处理后应该只剩下一个拆分方案。如果不是这样，报错
    if len(objectChar.schemeList) == 1:
        return tuple(objectChar.powerDict[x] for x in objectChar.schemeList[0])
    else:
        raise ValueError('您提供的拆分规则不能唯一确定拆分结果。例如，字「%s」有如下拆分方式：%s' % (objectChar.name, objectChar.schemeList))
```

如果成功，则每个基本部件都将产生一个最优拆分方案，存储到 `objectChar.bestScheme` 中。

# 三、部件树

所有不属于基本部件的汉字均以键值对的形式存储在 `字.yaml` 中，其值为一个表达式。一个表达式由一个二元运算符和两个操作对象组成，例如：

```yaml
他: [h, 亻, 也]
```

其中 `h` 为左右结构运算符，`亻` 和 `也` 为操作对象。当没有合适的部件来表达一个操作对象的时候，值也可以是另一个表达式，例如：

```yaml
前: [z, 前上, [h, 青下, 刂]]
```

在程序中，为了便于运算，我们定义了树类（`Tree`），将表达式处理为一个树对象。初始化该树对象时，我们不仅存储了该表达式的结构，还将每个值继续展开直到基本部件，例如：

```yaml
价: [h, 亻, 介]
```

这里 `亻` 是基本部件，而 `介` 不是，它由 `人` 和 `齐下` 两个更基本的部件组成。总而言之，`Tree` 对象以 `name` 储存汉字名称，`structure` 存储结构运算符，`first` 和 `second` 存储运算符的操作对象，这些对象仍然是一个 `Tree` 对象，如此迭代展到直到基本部件，它的 `first` 和 `second` 值为 `None`，也即基本部件是树的末端节点。

# 四、Schema 类概览

到目前为止，您已经了解了本系统的所有要素，现在让我们将它们组装成一个 `Schema` 类。

1. 构造函数 `Schema.__init__()`
   - 功能：首先加载两个数据库，并将字数据库解析为树，存入 `Schema.tree` 字典中。然后根据方案名加载 `xxx.schema.yaml`，首先在当前工作目录下寻找，如果找不到则在模块包的预置文件夹中寻找，如果再找不到则报错。
   - 输入：方案名 `schemaName`；
   - 输出：存储为类成员 `Schema.wen`, `Schema.zi`, `Schema.tree`, `Schema.schema`, `Schema.charList`，然后调用 `Schema.parseSchema()`；
2. 解析方案函数 `Schema.parseSchema()`：
   - 功能：分析用户的配置文件，生成字根集和退化字典；同时还检验笔画是否定义完全，不完全则报错；
   - 输入：无；
   - 输出：存储为类成员 `Schema.rootSet` 和 `Schema.degeneracy`；
3. 自定义域与自定义筛函数 `Schema.setField()`, `Schema.setSieve()`：
   - 功能：在初始化时，对象引入了私有成员 `Schema.__fieldDict` 和 `Schema.__sieveDict`，它们负责把文字版的退化映射和择优函数与程序中具体的函数联系起来，例如「根少优先」关联到 `schemeLen` 函数；在这一步用户如果编写了自己的域函数或者筛，则可以通过这个函数进行注册；
   - 输入：函数中文名 `name` 和实际函数 `function`；
   - 输出：更新类成员 `Schema.__fieldDict()` 和 `Schema.__sieveDict()`
4. 幂字典生成函数 `Schema.genPowerDict()`：
   - 功能：找出基本部件的所有有效切片，构造切片到用户对象字的幂字典；
   - 输入：对象字 `objectChar`；
   - 输出：存储为对象字 `objectChar` 的类成员 `powerDict`；
5. 拆分方案列表生成函数 `Schema.genSchemeList()`：
   - 功能：根据幂字典生成；
   - 输入：带 `powerDict` 的对象字 `objectChar`；
   - 输出：存储为对象字 `objectChar` 的类成员 `schemeList`；
6. 最优拆分方案生成函数 `Schema.genBestScheme()`：
   - 功能：利用估值函数对一个拆分进行估值，然后利用优化函数将最优化的拆分筛选出来；
   - 输入：带 `schemeList` 的对象字 `objectChar`；
   - 输出：将在择优逻辑下最优拆分 bestScheme 传给对象字 `objectChar`；
7. 运行函数 `Schema.run()`：
   - 功能：对于每个基本部件，依次运行 `genPowerDict(), genSchemeList(), genBestScheme()`，所得到的最优拆分方案存入字典；
   - 输入：无；
   - 输出：存储为类成员 `Schema.component()`；

这样，用户只需要如下三行代码

```python
from Chai import Schema
my_schema = Schema('my_file_name')
my_schema.run()
```

即可运行拆分，得到 `my_schema.component` 和 `my_schema.tree` 用于自己编码。

<center style="font-size: 3em">更新记录</center>

# 0.1

经过一个月的艰苦奋斗，汉字自动拆分系统「拆」迎来了第一个预发布版本 `拆 0.1`！

请注意 `拆 1.0` 之前的版本全部为预发布版本，请避免将其应用于生产环境中，并报告所发现的一切问题。

## ��️特性

1. 支持 GB 字集内全部汉字的自动拆分；
2. 支持以笔画种类和笔顺为基准建立退化映射；
3. 支持以「根少优先」「笔顺优先」「取大优先」为基准建立择优函数；
4. 以 98 五笔为例构造了测试实例。

# 1.0

新年新气象，汉字拆分系统正式版 `拆 1.0` 发布！

## ��️特性

1. 支持以拓扑信息建立退化映射；
2. 支持以拓扑信息建立择优函数；
3. 添加测试实例「指尖鸽码」和「小轻二笔」；
4. 定义了完善的编码 API；
5. 编写了用户界面函数 `example()` 和 `lookup()`。

## ��️修复

1. 针对「口」和「囗」两个字根进行了特殊的区分。