今天碰上一个非常有意思的问题。有一条通信线路，每次可以发送一个由数字 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 串的连接！