2008-04-03 22:52| 
17 Comments | 本文内容遵从如果你经常使用“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。
我们可以列出一张简单的表格，形象地展示出数字编码后的样子：
n Encode(n)
1 101
2 102
3 103
.. ...
8 108
9 109
10 11010
11 11011
12 11012
... .....
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
沙发一个,一会儿再看
我只想说，你一天想的好多哦...不过这个问题貌似我也想过，不过没这么仔细去研究过勒
!!!!!!!!
i finally understood...<3
有这个必要么……
另外：你觉得这样还能认清文件名么……
就（简单的）文件名排序的实用意义上，一般文件重名个数不会超过9位数，所以位数k前不加1，中间也不要加0间隔。
1位数 1?
2位数 2??
3位数 3???
..
9位数 9???
另外我是通过feedsky订阅您的博客的，但是在G-Reader打开这个主题直接跳转到了http://1985172.anyp.cn/blog/archive/415309/070227201147293.aspx
呵呵
丁
第一次来你的心地方，弄得相当不错啊
话说……为什么我打开你的主页，日志栏会有：
Not Found
Sorry, but you are looking for something that isn't here.
一个问题，假设文件名name的长度为：10^1000000
那么按照你说的最优编码方式结果应该为： 111111101000000name
可是我想能否把前的7个1，再次编码，也就是变成：1071000000name
显然比上面的那个短，所以我认为如果文件名的长度最够长的话，log(log(n))也不是最优的，最优的应该是log(log(...log(n)...)
不知道对否？
回复：不对，只要出现了那个1000000，大O意义上已经是log(log(n))了
以前在想我的$$能否是这样算的，连位数的位数都好几百……
突然想到这个方法处理9位以下的是不是有点大材小用，一般很少见到上亿的文件名（日期除外）……
一个问题，假设文件名name的长度为：10^1000000
那么按照你说的最优编码方式结果应该为： 111111101000000name
可是我想能否把前的7个1，再次编码，也就是变成：1071000000name
显然比上面的那个短，所以我认为如果文件名的长度最够长的话，log(log(n))也不是最优的，最优的应该是log(log(…log(n)…)
不知道对否？
回复：不对，只要出现了那个1000000，大O意义上已经是log(log(n))了
你要是说大O符号，那确实没问题，可是这个界限还可以再压缩，可以认为 O(log(log(log(n)))<O(log(log(n))吧
回复：你还是没明白我的意思。虽然1071000000name更短，但它的冗余长度仍然是log(log(n))。
呵呵，明白了，你说的对：只要出现了那个1000000，大O意义上已经是log(log(n))了
是我太粗心了 ～～
"对于每一个给定的前缀，最多只能产生(10^k-1)/9个数，...."
这里应该是 (10^(k-2))*9 吧.比如10****,当10确定之后,****可以是从1000 - 9999 的.
回复：首先，****允许有前缀0；其次，****的长度可以小于4位
证明里所提到的“编码方式”更一般一些
即是说 (10^k-1)/9 是指 c+1 位中的那个最后一个确定了的话,那么剩下的k-1的部分最多也就是 (10^k-1)/9 是吗?
可以把 楼主的表示法推演一下, 偶得出以下表示法,比楼主的更为简单
由于可以表示很长的数,所以可以理解为没限制
至于算法复杂度 什么的, 这个偶不会算,不知道偶的这个 跟楼主那个证明有没有啥支持或补充的.
用定长数作为前缀, 表示真实数字的位数, 后跟真实数字
比如
1位数 001?
2位数 002??
3位数 003???
....
101位数 101??????????.....
....
999位数 999?????????????????????????....... 一共 999+3位
而按照7楼的表示法,
999位数就表示为 1110999???????????????? 一共是 999+3+4位, 白多出4位.
如果把前缀定为定长 4位, 那么大的数表示为 9999????????...... , 一共9999+4位,
而用通用/(或叫万能吧,不受限制的)表示就得为 111109999??????, 一共是 9999+4+5位
我们追求的不是不通限制, 而是根据自己的需要合用就好, 那么根据需要表达的最大位数,用偶的表示法应该更简单一些.
再进一步,如果使用三段法定义, 最右为原始数, 第二段为中间段,表示原始数的位数,第三段在最左边用定长,表示中间段的位数, 那么容量更大,..
这样
比如左段用两位定长,
一位数 011?
2位数 012??
三位数 013???
....
999位数 03999?????......
99999999位数0899999999??????.......
这样最大可以表示的数字, 它的数字个数是一个99位数的....
以此类推.
-----------
其关键点在于 充分利用 位数 这一数字表示, 取代7楼说的 用 连续的1 填充在前面占用更多长度
Mac OS X和Flash中好像有这样的排序方式。