这是一个创建于 3368 天前的主题，其中的信息可能已经有所发展或是发生改变。
假设这样一个字典（二进制串）A(n)，使得任意长度为n的二进制串b都是A(n)的一个字串。以b在A(n)第一次出现的位置为p(b)。
是否可以证明，无论怎样优化A(n),都有对于任意b，p(b)的平均二进制长度大于n？
 |
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里面包含了所有可能的数字组合”，更不能用似是而非的推论来支持这个说法。经验、审美甚至信仰，在数学里，都敌不过薄薄的一纸证明。 其实死理性派也有情怀，只不过往往用在了奇怪的地方。（编辑：球藻怪） |
 |
11
c742435 OP @ryd994 注意我说的“平均” 这个字。
如果一个n位的串b在字典中的起始位置超过 2^n，意味着其索引长度将大于原始值长度，这样压缩就是没有意义的。 针对于任何字典集合，反复多次压缩之后肯定会有一些值因为上述原因而没有意义。 |
 |
12
stupidcat 2015-08-12 16:50:30 +08:00 1
|
 |
13
Xs0ul 2015-08-12 17:11:07 +08:00
对给定的n，一共有2^n种字符串需要编码，在假设这些字符串等概率出现的情况下，哈夫曼编码可以得出等长编码是最优的，也就是照原样不压缩（或者互相对应，但是这对降低长度没有帮助）。
lz说的p(b)，最后都会对应成一种编码，也就不可能达到压缩的要求，只能和原来一致。 所以追求平均意义下的无损压缩是不可能的。可行的比如：1、根据字符串出现概率不同，用更优的编码压缩；2、有损压缩。 更高层次的解释，还是看信息论比较好。 |
|
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 OP |
 |
19
RqPS6rhmP3Nyn3Tm 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文件，得不偿失。 |
Select Language