2008-04-03 22:52| 
18 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中好像有这样的排序方式。
[...] matrix67大牛的blog今天三周年了~~这是他推出的三周年的精选回顾全是精华阿 看看下面的这些文章，谁能看出这是个文科生(传说中去北大中文系泡妞?!)原文的地址: http://www.matrix67.com/blog/archives/5581. 原创科普说明文：递归假期的一篇作文，叫我们写任一说明文。我把这篇作文发到了我的Blog上。这可能是我Blog最早的技术文章，它确定了我以后类似文章的写作风格。2. 非常奇妙的证明：图形必在格点之外翻译的cut-the-knot上的一篇文章。这是我所见到的最elegant的证明之一，在饭桌上提到证明问题时我经常会举这个例子。几个好友很早就开始阅读我的Blog，他们一致认为这是最令人难忘的一篇日志。3. 几个把平面几何问题的辅助线做到空间去的数学趣题也是翻译的cut-the-knot上的系列文章，当时觉得确实非常神奇。后来的学习发现，其实射影几何中有更多有趣的例子。4. 追溯羊与车：Monty Hall Dilemma问题的故事我们数学老师提到了Monty Hall问题，他的说法是错误的，因此才写下这篇文章。当时写这篇文章主要是给我的同学看，因为那时这个Blog几乎只有我们同学才上。5. 几个很强的数列这是我在The On-Line Encyclopedia of Integer Sequences找到的，非常强。不是经常有考什么数列找规律的么？从这里面随便挑一个来，不查数列百科全书的话别人几乎不可能找出规律来。6. 爱的方程式惊奇函数图像系列文章的第一辑。后来渐渐有了3D桃心函数、阴阳图函数、公式生成的色情图片等一系列的东西。7. 什么是P问题、NP问题和NPC问题这可能是我写的最长的一篇原创文章了。很多网友都说，在类似的文章中这一篇是讲解最清楚、最通俗易懂的。8. KMP算法详解可能是这个Blog最经典的文章了。不少朋友最初都是找KMP算法找到这个Blog来的。9. 位运算讲解系列文章应该是这个Blog里第二经典的文章了。10. 无限小却无限大的集合 & 阶梯状的连续函数前段时间我和一帮人在饭桌上提到了诡异的函数，比如处处连续处处不可导的函数、除常函数外没有最小正周期的周期函数、导数为正却找不出单增区间的函数、平面上任意小的范围内均能找到一点的单值函数、在有理点处处不连续在无理点处处连续的函数（俗称爆米花函数）。但处处连续的阶梯函数，很多人可能还是第一次听说。挺好玩的。11. 令人称奇的简单证明：五种方法证明根号2是无理数牛！这个牛！想看一些精妙的证明，体会到数学证明的神奇之处的话，从这里开始是一个不错的选择。12. 从零开始学算法：十种排序算法介绍（上）这个也牛！同样地，如果想看一些精妙的算法和复杂度的分析证明，体会CS的乐趣，从这里开始是一个不错的选择。13. 从零开始学算法：十种排序算法介绍（中）这篇日志里讲了快速排序的平均复杂度的分析和证明，很强大很科学。初学算法的人经常会忽略复杂度分析这一步，学过一段时间后回过头来看看经典算法的复杂度分析是很有益的。14. 从零开始学算法：十种排序算法介绍（下）没啥好介绍的……以后有些没什么特别背景的日志我就不附加文字介绍了，不然写着好累。15. 无题 于2007年5月16日现在我已经很少在自己的Blog里写我的感情生活了。这是我在19岁生日那天写的。16. 数论部分第一节：素数与素性测试17. 神奇的分形艺术（一）：无限长的曲线可能围住一块有限的面积分形艺术系列的开篇。分形这个东西其实挺好玩的。18. 十大另类程序语言（上）19. 十大另类程序语言（下）哈哈，这个好玩！！有几个语言相当搞笑，挺佩服老外的想象力的。20. 令人敬畏的十维空间出人意料的结论。对应的几何图像太难以想像了。我一直想写一篇描述四维几何形状的文章，至今仍未动键盘。21. 十个有趣的英文文字游戏（上）22. 十个有趣的英文文字游戏（下）很早就对英文文字游戏感兴趣，看到过不少，记了各种性质独特的英文句子。有一天突然想整理出来写一下，于是有了这两篇日志。中文其实也有很多好玩的东西，比如对联啊，灯谜啊，拆字啊，断句啊，回文句啊等等。23. 神奇的分形艺术（四）：Julia集和Mandelbrot集还是在饭桌上，每次提到数学神秘得令人恐惧时我都会讲起这个。真是太神奇了，一个如此简单的过程竟然可以生成这般复杂玄妙的分形图形。24. Tupper自我指涉公式：图象里竟然包含式子本身数学中的魔术，非常有意思。本以为非常神奇，揭秘之后恍然大悟——不过如此。25. 编辑距离、拼写检查与度量空间：一个有趣的数据结构26. Poincaré圆盘模型：一个神奇的双曲世界进北大时恰逢数学文化节十周年，数院开了一系列精彩的讲座。我去听了其中三个讲座，这是我听过的最精彩一次。看《什么是数学》时看到了相关的内容，再结合这里的一些东西仔细品味了一下，真是科学得无与伦比。以后我还将引用到这篇日志。27. 等高线模式：解决极大极小问题的另类策略Pólya的《数学与猜想》确实是一本好书。我在这本书里学到了好多东西，其中一个最主要的收获就是这套诡异的极大极小问题解决办法。28. 趣题：直觉 VS 理性思考 经典概率问题29. 另类搞笑：自我指涉例句不完全收集AboutMe里就提到，我喜欢带有递归和自我指涉的句子。一直收集着很多这样的句子，终于决定整理出来和大家分享。30. 物理方法解决数学问题（二）：Archimedes与球体积公式31. 趣题：n为奇数时，正n边形的三角形剖分内有且仅有一个锐角三角形从EagleFantasy那里挖来的，是我目前最喜欢的“一句话证明”。跟别人提到“一句话证明”时我必然会拿它当例子。32. 物理方法解决数学问题（四）：Fermat-Torricelli问题33. 证明实数区间不可数的新方法我喜欢讲课，喜欢听每次揭晓“谜底”后下面的人恍然大悟的感叹声，喜欢从基本结论出发一步步推出不可思议的结论。在所有科学的东西里，我最爱讲的，最具悬念，最有戏剧性，结论最令人惊讶，最能颠覆传统观念就是对无穷集合势的分析了。从有限到无限，从可数到不可数，以及直线和平面上的点一一对应等等，每一个证明都令人拍案叫绝。这里提到了实数区间不可数与博弈游戏的关系，从一个全新的角度来看连续统，分析证明过程实在巧妙。34. 趣题：一个与Hamilton回路有关的问题35. 100囚犯问题、100囚犯问题加强版与选择公理（上）36. 100囚犯问题、100囚犯问题加强版与选择公理（下）37. 趣题：构造函数使得平面上任意小的圆内均包含函数上的点有一天突发奇想，到豆瓣的数学小组去逛了一圈，然后发现了这个神奇的东西。38. 很诡异的博弈问题分析方法39. 趣题：猜帽子游戏与Hamming编码40. 趣题：构造游戏初始状态使得后行者必胜41. 物理方法解决数学问题（五）：一个与椭圆有关的性质42. 趣题：量子计算机、另类编程语言和幂函数的解释43. 趣题：对数字进行编码使其按字典序排列后仍然有序这两篇日志是相当科学的算法题。很长时间没看到这么经典有趣的题目了，特别是前面那篇。44. 神奇的锈规作图：单用一个只能画单位圆的圆规如何作等边三角形这个精彩，强烈推荐一下。45. 矩阵、随机化与分形图形某留学Stetson大学的MM一次在校内上发日志链接到了我的Blog，我回访回去时认识了她。我和Stetson MM网恋了一段时间，发国际短信花了我不少钱。后来Stetson MM有了男朋友了，这段故事就此告终。这告诉我们：建网站来吸引MM终究是不可靠的。Stetson MM是我所见过的最适合我的MM，其思维的相似程度达到了令人惊讶的地步，世界上居然有一个如此像我的异性真是不可思议！这篇日志与Stetson MM在线性代数课上的一个课题研究有关。Stetson MM告诉我，她一个同学看到这篇日志后问她我Blog里的Stetson MM是不是指的她，她惊呼“你也订阅了这个Blog”呀。Small world。当时这篇日志在抓虾上的推荐数很是让我吃惊。46. 分享一些有趣的面试智力题（上）47. 分享一些有趣的面试智力题（下）48. 20年的时间里你可以做些什么？今年我20岁生日时写下的一篇特别的日志。神奇的是，这篇日志的ID正好也是我的生日——516。49. 趣题：空间四边形外切于给定球，求证四切点共面50. 趣题：直尺不够长时如何作出连接两点的直线？《什么是数学》中与射影几何相关的一个习题。当时我曾经在古汉课上大叫“太科学了”。 M12 Puzzle 传Google2亿美元收购Digg [...]