趣题：对数字进行编码使其按字典序排列后仍然有序

如果你经常使用“file5.txt”、“梁静茹23.mp3”、“AdultVideo153.avi”一类的文件名，你会发现在给文件名排序时，这种命名方式存在很大的弊端。很大一部分程序直接用字典序给文件名排序，因此file10.txt会排到file2.txt前面，尽管事实上10比2大。你是否想过，有没有什么办法能给数字编码，使得它们按字典序排序后仍然保持原有的大小顺序，并且编码的方法足够简单，编码之后原来的数字仍可以一目了然？一种简单的方法就是加前缀0，这样就保证了002在010前面，file005.txt也不会排到file100.txt的后面。它有一个缺点就是，你必须预先知道需要编码的数字最多有多少位，否则一旦新添进一个位数更多的数，前面所有的数必需要全部重新编码（加更多的前缀0）。另一个比较明显的缺点就是，这种编码方式过于冗长，添加进去的数字0最多可能与最大数的位数相当，多数情况下都远远超过了待编码的数自身的长度。我们更希望，编码时添加进去的“辅助码”不要超过这个数字本身的长度。由于数字n本身的长度是log(n)，因此我们需要保证冗余部分不超过log(n)。你能找到满足这些条件的一种编码方式吗？

注意到，当数字位数相同时，数值小的数按字典序排列时也排在前面。问题的关键就是，你需要找到一种编码方式，它可以标识出数字的位数，并且这种标识可以保证数字按位数从小到大排序。于是我们想到用“一进制编码”为每一个数加上一个“位数标识”。我们在每个数前面加上和这个数字本身的位数一样多的”1″，中间用一个”0″隔开。这样，所有三位数都是1110???的形式，所有四位数都是11110????的形式，这样按字典序排序时，三位数一定都排在四位数的前面。对应的解码方法也相当简单，只需要取第一个”0″后面的数字就行了。忽略常数的话，这种编码方式的冗余长度为log(n)，和数字本身的长度相当，基本上符合我们的要求。

为了帮助大家理解这种编码方式，我们来举几个例子。比如，下面这串数字（我网站域名的ASCII码）：

779711611410512054554699111109

就可以编码为：

1111111111111111111111111111110779711611410512054554699111109

前面数字1的个数和原始数字的位数一样多，然后中间添一个数字0。

我们可以列出一张简单的表格，形象地展示出数字编码后的样子：

nEncode(n)

1 101

2 102

3 103

..…

8 108

9 109

1011010

1111011

1211012

… …..

100 1110100

101 1110101

102 1110102

… ….

我们所提出的问题已经完美地解决了，但我们不禁会想，还有比O(log(n))更好的算法吗？仔细思考之后，你会想到，为什么不把数字的位数加在前面作为前缀，再用上面的方法把表示位数的那几个数字进行编码？这样就可以保证数字位数从小到大排列了啊！换句还说，如果一个数是k位数，那就在它前面加上一个数k；再在数k前面加上和k的位数同样多的”1″，中间用”0″隔开。这样，前面那个30位数

779711611410512054554699111109

就变成了

11030779711611410512054554699111109

其中，”30″表示这个数有30位，11表示数字30有2位，中间用”0″把这两个标识隔开。解码时，只需要寻找到”0″第一次出现的位置，比如在左起第x位；那么，原数就应该从左起2x的位置上开始算起。我们也简单列一个表格，说明对一个k位数编码之后的样子：

1位数：101?

2位数：102??

3位数：103???

………..

9位数：109?????????

10位数： 11010??????????

11位数： 11011???????????

12位数： 11012????????????

…………..

99位数： 11099????????????????…..?????

100位数：1110100????????????????…..??????

101位数：1110101????????????????…..???????

102位数：1110102????????????????…..????????

这种算法的冗余长度是数n的位数的位数的两倍，忽略常数即为log(log(n))。这个结果已经相当令人满意了。但我们还会想，有没有算法能够比O(log(log(n)))还好呢？下面我们证明，O(log(log(n)))的冗余已经是最好的了。

为了证明这个命题，我们可以这样反过来想：假如你对每个数字编码时只允许使用不超过c个单位的冗余，那么你最多能为多少数进行编码。对于某一个正整数k，k位数一共有9*10^(k-1)个，它们都必需表示成长度在0和k+c之间的数。我们把注意力集中在所有这些编码后的数字串的长为c+1的前缀（如果字串本身的长度小于c+1，定义前缀为它本身）。对于每一个给定的前缀，最多只能产生(10^k-1)/9个数，这小于k位数的总个数，因此这些前缀不可能全部相同。那些字典序较小的前缀已经不能再用于对位数更多的数进行编码了，因此我们说，长度为k的数“消耗了”至少一个长为c+1的前缀。而长度为c+1的前缀一共只有O(10^c)个，因此在冗余长度为c的情况下，我们能够编码的数不超过O(10^(10^c))；反过来，要想给不超过n的自然数进行编码，冗余长度至少为O(log(log(n)))。

题目来源：http://www.brand.site.co.il/riddles/200803q.html