如果你经常使用“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)))。
沙发一个,一会儿再看
我只想说,你一天想的好多哦…不过这个问题貌似我也想过,不过没这么仔细去研究过勒
!!!!!!!!
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中好像有这样的排序方式。
其实实际用,原串长度不超过9位时直接在前面加个位数就行了
超过9位,撑死也就在前面补一个0,串长总不会超过99位吧
当然楼主的方法在理论上很好
Thank you for the auspicious writeup. It in fact was once a enjoyment account it.
Glance complex to more introduced agreeable from you!
By the way, how can we be in contact?
Due to their safety, far more and additional users opted for this strategy of remote gambling.
Also visit my web log :: minje.idblogmaker.com
The Chinese economy grew just .four% in the second quarter, as tthe country’s strict zero-Covid policy takes a toll.
Heree is my web blog 마사지 알바
They both got jobs at big law firms, the tyupe thazt reward people today who make companion with seven-figure spend
packages.
Also visit my blog post 마사지 알바
Your subsequent two month-to-month payments will be due
on that simiar day off the month.
my web site: 정부지원대출
If the initial free bet is a winner, the player keepps all the income.
Feel free to surf tto my blog post :: homepage
Therefore, you require to know how long it requires for a loan request to
get authorized.
Here is myy webpage; 소액대출
bookmarked!!, I really like your web site!