blocks|key|1198842|text|这是Kolmogorov+complexity，你是对的，它是not+computable。如果是这样的话，您可以创建一个长度为n的矛盾程序，打印一个Kolmogorov复杂度为m>n的字符串。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1198843|显然，您可以为给定的输入绑定b_min_s。然而，据我所知，大多数这样做的努力都是存在的证据。例如，压缩English+Wikipedia的竞争正在进行中。|style|CODE|1198844|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Kolmogorov_complexity|1|http://en.wikipedia.org/wiki/Kolmogorov_complexity#Incomputability_of_Kolmogorov_complexity|2|http://prize.hutter1.net/^0|2|L|0|V|E|1|0|E|7|1G|H|2|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@$A|U|B|V|1|W]|$A|X|B|Y|1|Z]]|C|$]]|$1|D|3|E|5|6|7|10|8|@$A|11|B|12|F|G]]|9|@$A|13|B|14|1|15]]|C|$]]|$1|H|3|-4|5|6|7|16|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]|P|$5|K|L|M|C|$N|Q]]|R|$5|K|L|M|C|$N|S]]]]

This is <a href="http://en.wikipedia.org/wiki/Kolmogorov_complexity" rel="noreferrer">Kolmogorov complexity</a>, and you are correct that it's <a href="http://en.wikipedia.org/wiki/Kolmogorov_complexity#Incomputability_of_Kolmogorov_complexity" rel="noreferrer">not computable</a>. If it were, you could create a paradoxical program of length n that printed a string with Kolmogorov complexity m > n.

Clearly, you can bound <code>b_min_s</code> for given inputs. However, as far as I know most of the efforts to do so have been existence proofs. For instance, there is an ongoing competition to compress <a href="http://prize.hutter1.net/" rel="noreferrer">English Wikipedia</a>.

blocks|key|1198881|text|最大(平均)压缩率可能是1:1。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1198882|可能输入的数量等于输出的数量。|1198883|它必须能够将输出映射回输入。|1198884|为了能够存储输出，您需要与输入的最小容器大小相同的容器，从而提供1:1的压缩比。|1198885|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

The maximal (avarage) compression rate possible is 1:1. 
The number of possible inputs is equal to the number of outputs. 
It has to be to be able to map the output back to the input. 
To be able to store the output you need container at the same size as the minimal container for the input - giving 1:1 compression rate.

blocks|key|1198925|text|基本上，你需要足够的信息来重建你的原始信息。我猜其他答案对你的理论讨论更有帮助，但请记住这一点。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1198926|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Basically, you need enough information to rebuild your original information. I guess the other answers are more helpful for your theoretical discussion, but just keep this in mind.

This is a theoretical question, so expect that many details here are not computable in practice or even in theory.

Let's say I have a string <code>s</code> that I want to compress. The result should be a self-extracting binary (can be x86 assembler, but it can also be some other hypothetical Turing-complete low level language) which outputs <code>s</code>.

Now, we can easily iterate through all possible such binaries and programs, ordered by size. Let <code>B_s</code> be the sub-list of these binaries who output <code>s</code> (of course <code>B_s</code> is uncomputable).

As every set of positive integers must have a minimum, there must be a smallest program <code>b_min_s</code> in <code>B_s</code>.

For what languages (i.e. set of strings) do we know something about the size of <code>b_min_s</code>? Maybe only an estimation. (I can construct some trivial examples where I can always even calculate <code>B_s</code> and also <code>b_min_s</code>, but I am interested in more interesting languages.)

What is the maximum theoretically possible compression rate?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋 

腾讯云代码助手

CODING DevOps

Cloud Studio

SDK中心

API中心

命令行工具

这是一个理论问题，所以这里的许多细节在实践中甚至在理论上都是无法计算的。假设我有一个想要压缩的字符串s。结果应该是输出s的自解压二进制文件(可以是图灵汇编程序，也可以是其他假设的图灵完全低级语言)。现在，我们可以很容易地迭代所有可能的二进制文件和程序，按大小排序。让B_s是这些输出s的二进制文件的子列表(当然，B_s是...

问理论上可能的最大压缩率是多少？
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问理论上可能的最大压缩率是多少？EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问理论上可能的最大压缩率是多少？
EN