首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
V2EX  ›  问与答

从“利用 pi 压缩文件”想到的

  •  
  •   c742435 · 2015-08-12 13:41:59 +08:00 · 3395 次点击
    这是一个创建于 1576 天前的主题,其中的信息可能已经有所发展或是发生改变。

    假设这样一个字典(二进制串)A(n),使得任意长度为n的二进制串b都是A(n)的一个字串。以b在A(n)第一次出现的位置为p(b)。

    是否可以证明,无论怎样优化A(n),都有对于任意b,p(b)的平均二进制长度大于n?

    20 回复  |  直到 2015-08-13 06:01:01 +08:00
        1
    LU35   2015-08-12 14:05:37 +08:00 via Android
    云压缩?服务器存储pi的无限多位,客户上传任何文件转换成十进制并在pi序列中查找最匹配位置,然后在服务器中保存这些位置来标记文件序列所在pi中的位置,任何文件压缩到1kb?
        2
    X_Del   2015-08-12 14:36:29 +08:00
    E2DK,各种离线下载不就是这样……任何文件都压缩成了一个地址。
        3
    skydiver   2015-08-12 14:40:49 +08:00
    一会儿任意,一会儿平均,是闹哪样
        4
    ryd994   2015-08-12 14:48:38 +08:00   ♥ 1
    反证:如果对于某消息,不存在一下限,则我们可以反复使用该压缩算法,最终的压缩结果可为0或1bit。显然不可能
    https://zh.wikipedia.org/zh/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA)
        5
    picasso250   2015-08-12 15:42:50 +08:00
    是A(n)的一个字串

    是A(n)的一个子串

    ??
        6
    aheadlead   2015-08-12 15:55:23 +08:00
    这个类似的思路我问过我们老师… 老师让我去看信息论……
        7
    tabris17   2015-08-12 15:57:43 +08:00
    这不是扯淡么?

    PI只是个超越数,并不是合取数
        8
    xenme   2015-08-12 15:58:33 +08:00
    既然pi是无限不循环,觉得任何一个序列都有肯呢个是pi的子串。
    只要记录该子串的位置和长度就可以了。

    但是,找到这个子串需要用时多久(压缩)?算出pi的指定长度又要多久?(解压)
    其实就是无限大字典~
        9
    tabris17   2015-08-12 16:01:17 +08:00   ♥ 3
    http://www.guokr.com/article/439682/

    “π,圆周长与其直径之比,这是开始。后面一直有,无穷无尽。永不重复。就是说在这串数字中,包含每种可能的组合。你的生日,储物柜密码,你的社保号码,都在其中某处。如果把这些数字转换为字母,就能得到所有的单词,无数种组合。你婴儿时发出的第一个音节,你心上人的名字,你一辈子从始至终的故事,我们做过或说过的每件事,宇宙中所有无限的可能,都在这个简单的圆中。用这些信息做什么,它有什么用,取决于你们。”

    很多观众看到这一段之后十分感动,还有人感慨:为什么我们的数学老师没有这么教我们呢?

    之所以我们的老师不讲,是因为这段话在数学上是不对的。

    无理

    宅总的前两句话正确地描述了π的一个属性:无穷无尽且永不重复——换句话说,π是个“无限不循环小数”,也就是“无理数”。

    但是,一个无理数并不一定能包含“每种可能的数字组合”。

    举个简单的反例:0.909009000900009000009……

    (除非特别声明,所有数字都是10进制的,下同。)

    这个数的特点是,两个“9”之间的距离会越来越长,每次多一个0,直到无限。它是无穷无尽的,也是不循环的,因此是无理的;但别说“每种可能的数字组合”了,它连0到9这十个数字都凑不齐呢!

    合取

    包含所有数字组合的数,叫做“合取数”。无理数并不都是合取数。

    一个典型的合取数是这样的:0.10200300040000500000600……000110000000000012000……

    在越来越长的0串中间,夹杂着从1开始的所有自然数,直到无限。既然包含了所有自然数,当然也就包含了所有的数字组合。

    正规

    但是写这么多0,多费纸费电啊。如果把这些零去掉呢?

    得到的数就是这样:0.123456789101112131415……

    这个数不但是合取的,还是“正规”的——从0到9的每一个数字,出现的频率都趋向于一样的值。

    随机

    如果我们再进一步,连生成规律都不要了,而是用某种真随机生成器(比如哥本哈根解释下的量子随机性)造出一个每位都随机的数,那么它当然就是“随机”的了——不光每一个数字的长期频率趋于一致,任何位置出现的概率也都一样。

    那pi是什么?

    非常遗憾的是,目前为止我们只证明了pi是个无理数。pi是合取(包含所有可能)的吗?是正规(所有数字出现频率趋于一致)的吗?是随机(每一位上的数字都随机)的吗?

    答案是:全都不知道。

    我们很容易构造出一个合取数或者正规数,甚至能证明“几乎所有”实数都是合取而且正规的,但是随便拿一个具体的数字,要想判断它是否合取、是否正规,却极其困难。我们甚至都不知道pi里面是不是有无限个数字2。至于随机?别跟我提什么随机。

    合取数和正规数有另一个有趣的性质:和进制有关。有个常数叫斯通汉姆数(Stoneham number),在二进制、四进制、八进制……下已经证明全都是正规的了,可是在六进制下却能证明它不是正规的。如果一个数在任何进制下都正规,可以称之为“绝对正规”。不幸的是,pi在任何进制下都没能证明正规——离得最近的是2,有论文证明,假如某个猜想是对的,那么pi就是二进制正规;但那个猜想本身也只是“很可能正确”,还没有得到严格证明。

    当然,我们都已经计算出pi的几百亿位了,可以看看它们的分布来猜规律;也可以通过一些其他数学方法拐弯抹角地试图推断。从已知事实来看,pi和正规性吻合得非常之好,换做任何别的人文、社科、自然科学,都可以当做定论来用了,因此几乎所有人都“觉得”它该是正规的。可惜,这是数学,数学是靠证明说话的,只要拿不出证明,数学家就不能安心睡好觉。

    为什么要在乎这些细节呢?

    这篇文章不是为了批评《疑犯追踪》这部剧,事实上看到这一幕的时候我还非常高兴:影视剧里到处都是坏掉的理化生,而坏掉的人文社科干脆就是某些作品的主干——但现在终于出现了(哪怕是坏掉的)数学了!数学至少有了存在感!

    但是这文章又必须要写,因为编剧在写这个段子的时候违反了基本的数学精神。其一,数学靠证明说话,哪怕pi距离“包含所有可能序列”离得再近,哪怕每一个人试过的每一个数字序列都能在它里面找到,在得到证明之前你也不能这么说;其二,数学是一个严密的逻辑体系,就算pi真的包含了所有可能性,你也不能说“因为它是无理数所以它是合取数”,这个推论本身的逻辑是错的。哪怕结果蒙对了,也不能为此放过错误的过程,否则整个数学体系就无法存在。

    目前看来,pi“应该”是正规和合取的。如果让我打赌,我当然押“包含所有序列”一边;如果我在现实生活中用到了pi,我也会把它当做合取数和正规数那样用。甚至可以说,我“相信”pi是正规的:如果有人告诉我它不正规,我第一反应肯定是不接受;如果计算发现pi从第一万亿位开始变成了9090090009……,我没准都会开始怀疑宇宙的真实性——但是,只要没有出现证明,我就不能言之凿凿对你说:“pi里面包含了所有可能的数字组合”,更不能用似是而非的推论来支持这个说法。经验、审美甚至信仰,在数学里,都敌不过薄薄的一纸证明。

    其实死理性派也有情怀,只不过往往用在了奇怪的地方。(编辑:球藻怪)
        10
    c742435   2015-08-12 16:16:13 +08:00
    @tabris17 问题里有任何提到PI的部分吗?
        11
    c742435   2015-08-12 16:26:45 +08:00
    @ryd994 注意我说的“平均” 这个字。
    如果一个n位的串b在字典中的起始位置超过 2^n,意味着其索引长度将大于原始值长度,这样压缩就是没有意义的。


    针对于任何字典集合,反复多次压缩之后肯定会有一些值因为上述原因而没有意义。
        12
    stupidcat   2015-08-12 16:50:30 +08:00   ♥ 1
    @skydiver
    @c742435
    不知道题意是不是下面这个

    是否可以证明:
    无论怎样优化A(n),都有:对于所有长度为n的二进制串b,p(b)的平均值大于n
        13
    Xs0ul   2015-08-12 17:11:07 +08:00
    对给定的n,一共有2^n种字符串需要编码,在假设这些字符串等概率出现的情况下,哈夫曼编码可以得出等长编码是最优的,也就是照原样不压缩(或者互相对应,但是这对降低长度没有帮助)。
    lz说的p(b),最后都会对应成一种编码,也就不可能达到压缩的要求,只能和原来一致。

    所以追求平均意义下的无损压缩是不可能的。可行的比如:1、根据字符串出现概率不同,用更优的编码压缩;2、有损压缩。

    更高层次的解释,还是看信息论比较好。
        14
    liboyue   2015-08-12 17:14:43 +08:00 via Android
    @Xs0ul 楼主大概是希望你把这个编码构造出来:)

    如果是“所有序列”,那确实没法压缩
        15
    stupidcat   2015-08-12 17:21:43 +08:00
    假设存在这样一些最优的A(n):对于它们的前2^n位,从这些位中的每一位开始,包括该位自身,往后数n位,都是一个不同的二进制串b
    比如:
    A(2) 00110
    A(3) 0001011100

    p(b)的平均值 = ((1+2+...+2^n) / 2) / n > n
        16
    Xs0ul   2015-08-12 17:48:54 +08:00
    @liboyue 嗯,我要表达的是,假设这样的序列存在,那么它就会对应一种编码,然而不可能有这么好的编码。
    具体举例来说,比如给定n=3,那么一共有8种序列需要编码,这个数字序列再好,这8个的位置也只能是0~7(1~8),仍然需要3位来表示。之所以全都需要3位,而不把000简写为0,是为了避免歧义,否则没法知道010是01 0还是0 10。当然又要缩短,又要避免歧义的方法也有,比如哈夫曼编码,代价是也会出现一些比3位更长的编码,在平均的意义下会比3位更长。
        17
    ho121   2015-08-12 18:36:40 +08:00 via Android
    不一定就是压缩
    3.14159265358.....
    比如我要压缩8,嗯,结果是11,还比以前多一位
        18
    c742435   2015-08-12 20:42:29 +08:00
    @Xs0ul
    @stupidcat

    @Xs0ul 说的很清楚,我明白啦!所以那个用pi压缩任意文件的问题,与pi是否具有某种特性毫无关系,而是根本起不到压缩效果。
        19
    BXIA   2015-08-12 23:00:58 +08:00 via iPad
    在数学上,目前只能证明 Pi 是无理数,虽然长得和正轨的合取数几乎一模一样……
        20
    msg7086   2015-08-13 06:01:01 +08:00
    其实是可行的。只不过没有必要去用pi,而是可以去构造更有用的字典文件。
    预定义字典本身属于信息,所以理论上可以减少字典以外部分的存储空间。
    你为了压缩一个1KB的文件,得生成至少数TB的pi文件,得不偿失。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   982 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 25ms · UTC 21:57 · PVG 05:57 · LAX 13:57 · JFK 16:57
    ♥ Do have faith in what you're doing.