前缀码及其局限
五笔字型 86 版
诞生于 1986 年的五笔字型可能是除全拼外最知名的汉字编码输入方案，这里我们利用它来介绍「前缀码」这个概念。
五笔字型大致的编码规则为：在 a-y 25 个键上布局了字根、笔画、识别码等编码元素，单字的完整编码（即「全码」）为 3 ~ 4 个字母，词语的全码为 4 个字母，且对于单字还存在取全码的前一、前二或者前三个编码作为「简码」的情况。另外，五笔字型规定对于 4 个字母的全码可以自动上屏，而 1 ~ 3 个字母的简码或全码需要加空格才能上屏。
接下来，为了方便讨论，我们把依编码规则直接得到的全码和简码称为「原始编码」，而标注了空格和其他选择键的编码称为「实际编码」。也就是说，我们这里暂且把上屏用的空格看成是编码的一部分，举例来说，五笔字型中存在以下几条「实际编码」：
g_一gg_五ggg_玨gggg王
在连续的输入中，输入平台接受到用户输入的一串按键，需要将其切分并把每一部分对应到用户所希望输入的字词。例如当用户输入了 g_gg_，输入平台可以将其切分为 g_|gg_ 并给出「一五」这两个汉字。这种切分显然是无歧义的，因为输入平台不可能切分出 g_g|g_ 或者 g_gg|_ 这种无意义的编码串。可以看到，空格在这种切分中扮演了非常重要的角色，如果没有空格的存在，ggg... 连起来就会有很多种切分方式。
前缀码的定义
我们把类似于上面这样的编码结构称为「前缀码」，它的正式定义是：
我们说一个方案是前 缀码输入方案，如果其中任何一个实际编码都不是另一个实际编码的前缀。
显然，如果一个方案是前缀码，那么当用户在连续输入时，不管一串按键有多长，输入平台总能给出准确的切分：这是因为任何一个编码都不是另一个编码的前缀，所以当用户输入完某个编码之后，输入平台知道它肯定不属于另一个编码的一部分，因此可以直接在此处进行切分。例如，当用户输入完 gg_ 之后，输入平台知道不会有其他的编码以 gg_ 开头（也就是说打完空格之后就不会有其他的按键）了，因此可以上屏「五」。
前缀码的局限
前缀码不好吗？不，前缀码太好了！在除了汉字编码输入方案以外的领域，前缀码得到了十分广泛的应用，例如 Unicode 中著名的 UTF-8 编码就是一种前缀码。使用这种编码，常用的字符只需要占 1 个字节空间，不常用的占 2, 3, 4 个字节空间，却不会因此而发生任何的混淆或者解码失败的情况。不仅如此，信息论还证明了用前缀码可以构造出给定信源上的最高效（也就是码长最短）的编码：Huffman 编码。
既然如此，为什么还说前缀码有局限性呢？这是因为，在汉字编码输入方案这个领域来说，执行编码任务的并不是机器或者程序，而是人脑。在学习成本的限制下，用于汉字输入的前缀码通常不能像 Huffman 编码那样高效。为了理解这一点，让我们回过头来继续研究一下五笔字型输入方案。
首先我们忽略掉少部分三码全码的情况，假定字词的全码都是 4 个字母，而简码是 1, 2, 3 个字母加上空格。这些空格是不携带编码信息的，显然输入大量的空格是一种冗余，使得码长会比较高。那么我们要问：能否在保持前缀码的特性下，让简码的最后一码也是字母键，让它去携带一些编码信息？例如，如果全码是 abcd，那么简码是 af 可以吗？
答案是：可以，但会比较奇怪。在这种情况下，打完编码 a 之后，必须要知道当前这个字是不是简码，才能决定是继续打到 abcd 还是 af 这两条不同的路径上。这使得简码的使用变得非常困难。所以，大部分传统输入方案都采取了和五笔字型相同的简码设置逻辑，也就是将最后一码定为不携带信息的空格，这样在输入这个空格之前，想要的字就已经显示在候选框中了，用户只需要观察这个字是不是自己想要的（如果是则击空格上屏，如果不是则继续输入剩下的编码）。
说到这里，你可能会觉得最自然的思路是：全码是 abcd，简码是 a, ab, abc... 这样一来，既不需要打无意义的空格，也不需要去记忆不同的输入路径。然而，这本身就和前缀码中「任何一个编码都不是另一个编码的前缀」是矛盾的。
总结一下，我们把我们刚才的论证浓缩为下面 3 个命题：
- 命题 1：汉字编码中，一个词按照规则导出的最基本的编码称为全码，而比全码更短的编码称为简码，简码的存在可以提高输入效率；
- 命题 2：简码和全码最自然的关系就是「简码是全码的前缀」，这样可以在输入过程中自然地熟悉简码；
- 命题 3：前缀码中，不允许一个编码是另一个编码的前缀。
可以看到，上述 3 个命题是互相矛盾的，这说明前缀码无法高效地安排简码。
〇九五笔：前缀码提高效率的尝试
看到这里，所有前缀码方案都有一个天然的缺陷：除了最大码长的编码之外，其他编码（简码）的末码都不能携带任何信息，否则就会造成严重的易学性问题。然而，较短的编码正是效率的关键所在，简码的末码不携带信息必然损失编码效率。
为了把这种编码效率补回来，我们会看到，以〇九五笔为首的「多重简码」派一直在试图增大末码的数量，从 091 的一二简三重到 092 的一二简十重，都是在增加这个「不携带信息的选择键」的数量，从而增加较短编码的空间大小。但是，这种多重简码需要额外记忆，指法也不是很好。
如何解决这个矛盾？欢迎来到顶功的世界！