跳到主要内容

拆分表的定量评价

引言​

给定一张码表，可以用各种方法来评测码表的性质；但是，给定一张由各个编码对象的元素构成的序列表，却很少有定量的手段来评估序列表的性质。本文中将讨论几个能够定量计算的序列表指标。

数学标记​

我们记 S={s1,⋯ ,sn}S=\{s_1,\cdots,s_n\} 为待编码对象的集合，R0={r1,⋯ ,rm}R_0=\{r_1,\cdots,r_m\} 为元素的集合。在编码的规则确定了以后，存在一个「序列映射」把一个待编码对象 ss 映射为最长不超过 LL 个元素的序列。为了处理那些长度小于 LL 的序列，我们向这些序列后面增加符号 μ\mu 直到长度达到 LL，这样所有的序列就都是长度 LL 的了，并且我们把 ε\varepsilon 视为 RR 的一部分，即 R=R0∪{μ}={μ,r1,⋯ ,rm}R=R_0\cup\{\mu\}=\{\mu,r_1,\cdots,r_m\}。这样，这个序列映射可以表示为

f:S→RLf:S\to R^L

若符号映射也确定了，则可以把每个元素指定到一个符号，从而完成编码及输入。设可用的符号集是 Σ0={σ1,⋯ ,σd}\Sigma_0=\{\sigma_1,\cdots,\sigma_d\}，为了方便分析我们也可以引入一个空符号 ε\varepsilon 让 Σ=Σ0∪{ε}\Sigma=\Sigma_0\cup\{\varepsilon\} 那么符号映射可以写作 g:R→Σg:R\to\Sigma。编码映射是序列映射和符号映射的复合，即

h=g∘f:S→RL→ΣLh=g\circ f:S\to R^L\to\Sigma^L

离散性指标​

编码的第一要义就是能把编码对象离散开，如果编码对象的元素序列相同，那么最终编码也一定相同。因此我们此前提出了「零阶重码（原始重码）」的概念，即假设 SS 在映射 ff 下的像是 Q⊂RLQ\subset R^L，那么 ∣S∣−∣Q∣|S|-|Q| 就是零阶选重数。相应的，如果 SS 在编码映射 hh 下的像是 V⊂ΣLV\subset\Sigma^L，那么 ∣S∣−∣V∣|S|-|V| 就是实际选重数。但是，这个指标还比较粗糙，因为零阶选重数往往远小于实际选重数，所以不能很好地解释为什么其他对象发生重码。

所以接下来我们定义一阶、二阶、三阶甚至更高阶的重码。给定一个符号映射 g:R→Σg:R\to\Sigma，检视由其生成的编码映射 h=g∘fh=g\circ f 产生的实际重码。当 sis_i 和 sjs_j 重码时，

  • 如果它们的序列完全相同，那么就是零阶重码；
  • 如果它们的序列有一个不同，那么就是一阶重码；
  • 如果它们的序列有最多两个不同，那么就是二阶重码；
  • 如果它们的序列有最多三个不同，那么就是三阶重码；
  • ……

也就是说，零阶、一阶、二阶和三阶重码是定义在 SS 上的二元关系，d0,d1,d2,d3∈S×Sd_0,d_1,d_2,d_3\in S\times S，它们具有反身性、交换性，但是除了零阶重码外不具有传递性，所以不是等价关系。

在符号映射还不存在的情况下，如何对一阶、二阶甚至更高阶的重码进行估计呢？这就需要我们引入一个新的概念，就是序列空间上的边际分布。考虑一个序列 p=(r1,r2,r3)∈RLp=(r_1,r_2,r_3)\in R^L，可能有零个、一个或者多个编码对象对应这个序列，我们把这个定义为序列空间上的数分布，即

ρ(p)=ρ(r1,r2,r3)=size of {s∈S∣f(s)=p}\rho(p)=\rho(r_1,r_2,r_3)=\text{size of }\{s\in S|f(s)=p\}

显然，如果 ρ(p)>1\rho(p)>1，就发生了零阶重码。下面我们考虑一个三码方案，令第一、第二元素的边际分布为

ρ12(r1,r2)=∑r3∈Rρ(r1,r2,r3)\rho_{12}(r_1,r_2)=\sum_{r_3\in R}\rho(r_1,r_2,r_3)

可以想见，如果对于某个特定的 r1,r2r_1,r_2，ρ12\rho_{12} 的数值很大，那么即使不存在零阶重码，也非常容易产生一阶重码。在极端情况下，如果 ρ12(r1,r2)>∣Σ∣\rho_{12}(r_1,r_2)>|\Sigma|，那么根据抽屉原理可知，一定会存在一阶重码。所以，我们得到了以下的重要观察：

序列空间上的边际分布反映了非零阶重码的信息。

对于这个三码方案而言，存在两类可以计算的边际分布：

  • 二元边际分布 ρ12,ρ13,ρ23\rho_{12},\rho_{13},\rho_{23}: 即消除掉一个元素后的边际分布
  • 一元边际分布 ρ1,ρ2,ρ3\rho_1,\rho_2,\rho_3: 即消除掉两个元素后的边际分布

在零阶重码一样的情况下，如果边际分布均匀，那么非零阶重码往往比较少；如果边际分布不均匀，那么非零阶重码往往比较多。

那么，怎么衡量边际分布是否均匀呢？我们可以采用重码估计方法。注意到，前两码为 r1,r2r_1,r_2 的字能利用的空间总量为 ∣Σ∣|\Sigma|，那么由此产生的重码数量估计为 ρ122(r1,r2)/2∣Σ∣\rho_{12}^2(r_1,r_2)/2|\Sigma| 。因此，一阶重码的估计值为

D1=12∣Σ∣(∑r1,r2ρ122(r1,r2)+∑r1,r3ρ132(r1,r3)+∑r2,r3ρ232(r2,r3))D_1=\frac1{2|\Sigma|}\left(\sum_{r_1,r_2}\rho_{12}^2(r_1,r_2)+\sum_{r_1,r_3}\rho_{13}^2(r_1,r_3)+\sum_{r_2,r_3}\rho_{23}^2(r_2,r_3)\right)

同理，二阶重码的估计值为

D2=12∣Σ∣2(∑r1ρ12(r1)+∑r2ρ22(r2)+∑r3ρ32(r3))D_2=\frac1{2|\Sigma|^2}\left(\sum_{r_1}\rho_{1}^2(r_1)+\sum_{r_2}\rho_{2}^2(r_2)+\sum_{r_3}\rho_{3}^2(r_3)\right)

而「三阶重码」也就自然退化为了整体重码估计，验证了本理论的有效性。

D=D3=∣S∣22∣Σ∣3D=D_3=\frac{|S|^2}{2|\Sigma|^3}

下面用这个理论来分析 c42 和易码的重码情况，其中 c42 为 27 键方案，易码为 26 键方案，字集为通用规范汉字（8105）和 GB2312（6763）的交集，共 6638 字：

指标c42易码奕码
零阶重码255619
一阶重码估计93014181395
一阶重码实际299488397
二阶重码估计104913041205
二阶重码实际624749661
整体重码估计111912541254
整体重码实际849942870

可以看到，考虑上用键数的差异之后（将易码的重码水平乘以 (26/27)3(26/27)^3），两者实际重码几乎完全一致（849 : 841），但是在一阶和二阶和三阶上的分布以及理论预测值非常不同。（此处我们忽略零阶重码的差异，因为形音码显然更容易做到零阶重码少，而且零阶也不是本文的重点）

  • c42 是二阶重码占主导（(624−299)/849=38%(624-299)/849=38\%），易码是一阶重码占主导（(488/942=52%(488/942=52\%）；这主要是因为后者是乱序方案，当两个序列有 2 处不同的时候更容易通过排布的方式化解重码；
  • 只看一阶重码，无论是估计还是实际值，c42 都有巨大的优势，也就是说 c42 的序列中前两元都相同的字数不会太多，第一元和第三元相同的字数不会太多，第二元和第三元相同的字数也不会太多
  • 由于在实际的方案设计中都会考虑到尽可能规避重码，因此所有的估计数据都高于实际数据，也即前者可以认为是后者的一个上界；其中，一阶的估计离实际最远，整体的离实际最近，这主要是因为一阶重码比较有规律，可以通过合理放置元素来规避（例如，合理安排构字能力强的大部首就可以规避掉大部分一阶重码），整体重码的规律性就比较弱，接近估计时使用的随机极限
  • 从三阶到一阶，c42 的重码估计是递减的，说明每增加一个元素，对字的分离程度比按键的数量（27）更加显著，因此说明拆分的质量比较高。

不过，c42 是用未归并的 400 根参与计算的，易码是归并后的 300 根，导致估计值严重偏低，需要重新归并才能确认上述结论。尽管如此，上述讨论还是给设计高离散性能的拆分打开了新的思路。

递归性指标​

汉字本身具有递归的性质，例如在形声字、会意字中一个字可以作为另一个字的构成部分。下面我们分别称为部分字和整体字。那么，一个自然的问题就是，部分字和整体字的编码之间是否有关系？

我们记具有构字能力的字的集合为 T⊂ST\subset S。对于其中的每个字 tit_i，我们可以找到它所构成的字（假设共有 nin_i 个），并用一个函数表示它，des 表示 descendants：

des⁡ti=(si1,si2⋯ ,sini)\operatorname{des} t_i=(s_{i_1},s_{i_2}\cdots,s_{i_{n_i}})

如果 tt 构成字 ss，我们记 t≺st\prec s 或者 s≻ts\succ t。

完美递归​

完美递归是指，若 t≺st\prec s，那么 ss 的元素序列完整包含了 tt 的元素序列。例如，「笔画输入法」的元素序列就是依笔顺排列的各个笔画，在绝大多数情况下都满足完美递归。一些基于双编码的纯形码方案，往往也在一些情况下能满足这个条件

但是，这个标准比较严苛，不适用于单编码形码、形音码等有补码的情形。另外，在 ss 的元素序列没有完整包含了 tt 的元素序列的时候，这个标准不能给出比较合理的中间结果。

不完美递归​

在上面这个条件不完全满足的情况下，我们希望找到一个 tt 的元素序列 ptp_t 的一个子序列 qq，使得这个子序列被更多的 tt 的后代所包含，并且这个子序列还要尽量长，也就是转化为下式的极大化问题：

R(q)=(∑s∈des⁡tI(ps includes q))×len⁡qR(q)=\left(\sum_{s\in\operatorname{des}t}\mathbb I(p_s\text{ includes }q)\right)\times\operatorname{len}q qt=arg⁡max⁡qR(q)q_t=\arg\max_q R(q)

我们把找到的这个 qtq_t 称为 ptp_t 的最佳子序列，相应的 L(qt)L(q_t) 称为 tt 的递归得分。这样，我们可以进一步计算在整个具有构字能力的字的集合 TT 上的递归得分之和：

Rtotal=∑t∈TL(qt)R_{\rm total}=\sum_{t\in T}L(q_t)

在上述的 6638 字的字集中，易码得分为 9203 分，c42 得分为 8256 分，说明易码的递归性优于 c42。

连续性指标​

连续性指标关注字根类形码中一个字选取的字根在这个字的所有字根中的顺序关系。这个顺序可以是纯粹的笔顺，也可以是人为定义的其他顺序。（例如，郑码规定「辶」优先取。）

指定顺序之后，可以考察一个字 ss 的序列 psp_s 是由多少个连续的区段构成的，我们把这个量定义为 itv⁡ps\operatorname{itv}p_s。定义总跳跃数为 JJ，

J=∑s(itv⁡ps−1)J=\sum_s(\operatorname{itv}p_s-1)