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

    如果你经常使用“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

27 条评论

  • sqybi

    沙发一个,一会儿再看

  • jole

    我只想说,你一天想的好多哦…不过这个问题貌似我也想过,不过没这么仔细去研究过勒

  • eeendless

    !!!!!!!!

    i finally understood…<3

  • yangyanggoods

    有这个必要么……
    另外:你觉得这样还能认清文件名么……

  • 闲耘

    就(简单的)文件名排序的实用意义上,一般文件重名个数不会超过9位数,所以位数k前不加1,中间也不要加0间隔。
    1位数 1?
    2位数 2??
    3位数 3???
    ..
    9位数 9???

    另外我是通过feedsky订阅您的博客的,但是在G-Reader打开这个主题直接跳转到了http://1985172.anyp.cn/blog/archive/415309/070227201147293.aspx

  • Eagle_Fantasy

    第一次来你的心地方,弄得相当不错啊

  • yangyanggoods

    话说……为什么我打开你的主页,日志栏会有:
    Not Found
    Sorry, but you are looking for something that isn’t here.

  • rmq

    一个问题,假设文件名name的长度为:10^1000000
    那么按照你说的最优编码方式结果应该为: 111111101000000name
    可是我想能否把前的7个1,再次编码,也就是变成:1071000000name
    显然比上面的那个短,所以我认为如果文件名的长度最够长的话,log(log(n))也不是最优的,最优的应该是log(log(…log(n)…)
    不知道对否?

    回复:不对,只要出现了那个1000000,大O意义上已经是log(log(n))了

  • Freeze

    以前在想我的$$能否是这样算的,连位数的位数都好几百……
    突然想到这个方法处理9位以下的是不是有点大材小用,一般很少见到上亿的文件名(日期除外)……

  • rmq

    一个问题,假设文件名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))。

  • rmq

    呵呵,明白了,你说的对:只要出现了那个1000000,大O意义上已经是log(log(n))了
    是我太粗心了 ~~

  • jjymhkx0820

    “对于每一个给定的前缀,最多只能产生(10^k-1)/9个数,….”

    这里应该是 (10^(k-2))*9 吧.比如10****,当10确定之后,****可以是从1000 – 9999 的.

    回复:首先,****允许有前缀0;其次,****的长度可以小于4位
    证明里所提到的“编码方式”更一般一些

  • jjymhkx0820

    即是说 (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中好像有这样的排序方式。

  • minglingmaster

    其实实际用,原串长度不超过9位时直接在前面加个位数就行了
    超过9位,撑死也就在前面补一个0,串长总不会超过99位吧
    当然楼主的方法在理论上很好

  • Parisa

    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?

  • minje.idblogmaker.com

    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: 정부지원대출

  • homepage

    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!

发表评论

8  ×  1  =