2011-06-27 2:02| 
72 Comments | 本文内容遵从今天碰上一个非常有意思的问题。有一条通信线路，每次可以发送一个由数字 0 到 9 组成的任意长的数字串。怎样巧妙地利用这条通信线路，构造一种一次能够发送两个数字串的协议？注意到，直接将两个数字串相连是不行的，因为这将会产生歧义。如果对方收到的数字串是 1234 ，他没法知道你发送的是数字串 12 和 34 ，还是数字串 123 和 4 ，抑或是 1 和 234。
能否把第一个串的位数编码进去，比如把 12 和 34 编码成 21234 ，这样不就知道第一个数字串到哪儿截止了吗？不行，因为你不知道这个位数信息本身到哪儿截止，假如编码结果是 123456789012345 ，你就不知道第一个数字串是 1 位还是 12 位了。换一个思路，能否用几个非常特殊的数字当作分隔符呢？也不行，因为你要发送的数字串里有可能偏偏也包含了这几位数。怎么办呢？
一种非常容易想到的方法是，把两个数字串都转换为九进制，这样便把数字 9 腾了出来，它就能用作分隔符了。例如，要想发送数字串 12 和 34，只需要把 12 和 34 分别转成九进制，再在他们之间添加一个数字 9，得到数字串 13937，然后发送出去就可以了。即使要发送的数字串中有前导 0 ，问题也不大，我们可以在九进制数前面也加上相同数量的前导 0 。例如，把 012 和 0034 连在一起，也就成了 01390037 ，原始信息中的前导 0 也就很容易识别出来了。
注意到，把一个十进制数转化成九进制数，数字位数是要增加的。一个值得考虑的问题是，为了实现数字串的连接，采用上述方法需要多花费多少位数字？一个 n 位数的九进制表达，其位数大致可以记作 log(9, 10n) ，也就是 log(9, 10) · n ，大约等于 1.048 n 。因此，把一个 n 位数变成九进制，将会增加 0.048n 位数，似乎是相当节省了。不过，从计算机算法的角度来看，系数再小，它也是 O(n) 的；当数据规模非常大的时候，这个算法的效率并不让人满意。上述算法还有优化的余地吗？
一个优化方案是，既然首次出现的 9 一定是分隔符，后一个数字串就不必转成九进制了， 12 和 34 只需要编码成 13934 就行了。但是，渐近意义上看，所得数字串的附加长度仍然是 O(n) 。不过，如果和之前“写明第一个串的位数”的思路结合一下，我们就有了一个渐近意义上更优的方案：把第一个串的位数转化为九进制，再添加数字 9 标识出它的右边界即可。如果想要发送数字串 123456789012345 和 12345 ，就可以先数出前一个数有 15 位，再把位数本身转换成九进制 16 ，原始信息便可编码为 16912345678901234512345 。这样一来，附加长度就比原来小得多了，它只有第一个数的位数的 0.048 倍，也就是 0.048 log(n) 了。
同样是 log(n) 级别的附加长度，我们还有一种更加简单巧妙的方案。将第一个串的位数用“口吃”的方式表达出来，每个数字都重复说一遍，然后加上一对不相同的数字（比如“01”）作为结束标记。例如， 123456789012345 和 12345 就将被编码为 11550112345678901234512345 ，表示第一个数字有 15 位。这样一来，附加的长度就是 2 log(n) + 2 ，同样也是 log(n) 的级别，不过方法简便多了。而且更棒的是，这种方法能够直接扩展到一个更加一般更加困难——两个 01 串的连接！
大家还能想到什么其他有趣的方案？
Update: 在写上面的文字时，我显然还想得不够多，现在看来让人很不满意。看了大家的回复，我深受启发，决定继续往下说一说。上述方法说穿了就是，用 11 来表示 1 ，用 22 来表示 2 ，一直到用 99 来表示 9 ，然后用 01 来表示分隔。这背后的核心思想其实就是：用两位数字来表示一位数字，从而扩展字符集。因此，我们还可以构造出很多类似的方案来。比方说，用 01 表示 1 ，用 02 表示 2，等等，一直到用 09 表示 9 ，最后用 10 表示分隔符。因此， 123456789012345 和 12345 就可以编码为 01051012345678901234512345 。读取编码后的数字串时，如果读到的是 0?0?0?... 的模式，那么我们都是在读取第一个数字串的位数；什么时候模式被打破了，出现了一个 10 ，第一个数字串的位数也就读完了。
注意到，扩展字符集的根本动机，就是我们希望能够在字符集中新增加一个分隔符。不过，上面的方案把字符集扩展得太大了，绝大多数新字符其实都没用，实在有些浪费。有办法能够对 {0, 1, 2, ..., 9, 分隔符} 这 11 个字符重新编码，使得编码效率又高，连接起来又不会产生歧义吗？不少网友提到了 Huffman 编码，就是专门解决这个问题的。网友 hhb 提到，扩展字符集还有一个更简单的方法：直接把分隔符用 A 来表示，然后把带有分隔符的数字串看作 11 进制数，再转成 10 进制数即可（有前导 0 的话要做保留）。
转义符的功能不也是这样吗？由于字符串无法表示出换行的概念，于是用 \n 表示换行；为了不造成歧义，又规定 \\ 表示真正的 \ 。受转义符的启发，我们就有了更好的方案，比方说用 01 表示分隔符，用 00 表示真正的 0 。解码时，每读到一个 0 ，都看看它后面跟的是什么，如果还是一个 0，表明这是一个真正的 0 ；如果是 1 ，则表示分隔符。
如果看到了新的想法，我再接着补充。