压缩方法

Question

我知道大多数压缩方法都依赖一些重复的数据才能生效。例如，刺痛的“AAAAAaaaQWERTY”可以被表示为“5A3aQWERTY”用于无损和诸如“8aqwerty”用于有损（这些仅仅是例如，不是实际的工作方法）。据我所知，所有的压缩算法都依赖于 - >常量< - 字符串的重复。

这里带有字符串“ABCDEFGHIJKLMNOPQRSTUVWXYZ”的问题。这里没有什么重复，但正如你可能看到的字符串中的信息可以用更短的方式表示。在类似正则表达式的str中。将会是“[a-z]”，或者可能是“for（x = 0; x < 25; ++）{ascii（97 + x）}”。

也考虑字符串“0149162536496481100121” - 它可以用“for（x = 0; x <11; ++）{x * x}”表示。

字符串 “ABEJQZer” 可表示为 “为（X = 0; 8; ++）{ASCII（64 + X * X）}”

最后两个是知道的算法的例子，它可以重现原始字符串。我知道一般算法（如果它们是高效的）比它们可以产生的数据占用的空间要小得多。

像在svg图像（它只有在文件中的算法）的大小小于jpeg。

我的问题是有压缩的一种方式，这需要数据和tryes找到高效的算法，可以代表它。像向量化光栅图像（如http://vectormagic.com/），也可以与其他数据一起使用。考虑音频数据（因为它可以压缩有损） - 一些音频编辑器（例如，大胆度）项目文件包含诸如“从时间0到时间2分钟45.6秒产生具有0.8幅度的120Hz恒定频率”的信息（大胆性商店信息以xml格式）。这个元数据占用的内存非常少，当项目导出为wav或mp3时，程序会将信息“呈现”为导出格式的实际样本。

在这种情况下，压缩机应该反转渲染过程。它应该采用wav或mp3文件，找出哪些算法可以表示样本（如果它是有损的，则算法必须产生样本的一些近似值 - 就像vectormagic.com合成图像一样）并生成压缩文件。

据我所知，压缩时间将是令人难以置信的长，但是否有这样的（或类似）的压缩算法？

Answer 1

所有压缩方法是这样的：输出是一组用于呈现所述输入，或类似的东西的输入的一组算法参数。

例如，MP3音频编解码器将输入分成576个采样块，并将每个块转换为频率幅度空间，并且修剪人类听不到的音频。输出相当于“在接下来的13毫秒播放频率x，y，z中振幅为a，b，c”。这对于音频数据非常有用，JPEG中使用的类似方法适用于照片图像。

类似的方法可以应用于您提到的情况。例如987654或010409162536等序列由多项式的连续值生成，可以表示为多项式的系数，第一个为9-x的（9，-1），第二个为（1， 2,1）为1 + 2x + x 2。

为简单起见，用于生成输入的算法的选择往往是固定的，并且为用户量身定制。例如，如果您正在处理使用数码相机拍摄的照片图像，则甚至无法尝试生成矢量输出。

Answer 2

当试图无损压缩一些数据，你总是以压缩在人类语言中的一些文本时创建的模型，例如启动，您认为，这实际上有没有那么多的话，它重复一遍又一遍。但是，很多算法试图在旅途中学习模型的参数。就像它不依赖于这些单词实际会是什么一样，它会尝试为给定的输入找到它们。所以算法不依赖于实际使用的语言，但它确实依赖于事实，即它实际上是一种人类语言，它遵循一些模式。

一般情况下，没有任何完美的算法，它可以无损压缩什么，它是数学上的证明。对于任何算法，都存在一些压缩结果比数据本身更大的数据。

Answer 3

您可以尝试重复数据删除：http://en.m.wikipedia.org/wiki/Data_deduplication。这是一个有点不同，更智能的数据压缩。