序列压缩？

Question

最近我遇到了一个让我很困惑的问题 问题是： 我想压缩一个序列，这样就不会丢失任何信息，例如：

a,a,a,b --> a,b

a,b,a,a,c --> a,b,a,a,c（它不能压缩为a,b,a,c，因为这样我们就失去了a,a）

有没有算法可以做这样的事情？这个问题的名称是什么？是压缩吗？或者其他什么？ 我真的很感激任何帮助 提前致谢

Answer 1

另一个好的算法是 Lempel–Ziv–Welch

我发现这个简单的 Javascript LZW 函数非常棒，来自 140 字节的 javascript 的魔术师：

function (
    a // String to compress and placeholder for 'wc'.
){

    for (
        var b = a + "Ā", // Append first "illegal" character (charCode === 256).
            c = [], // dictionary
            d = 0, // dictionary size
            e = d, // iterator
            f = c, // w
            g = c, // result
            h; // c

        h = b.charAt(e++);
    )

        c[h] = h.charCodeAt(), // Fill in the dictionary ...
        f = 1 + c[a = f + h] ? a : (g[d++] = c[f], c[a] = d + 255, h); // ... and use it to compress data.

    return g // Array of compressed data.

}

Answer 2

每种能够以占用更少内存的方式转换数据的算法称为压缩。可能是无损的，也可能是有损的。

例如（“给定示例”的压缩形式 :-) ）

以下是恕我直言最简单的形式，称为游程长度编码，简称 RLE：

a,a,a,b,c -> 3a,1b,1c

正如您所见，所有相同的后续字符都被压缩为一。

您还可以搜索后续模式，这要困难得多：

a,b,a,b,a,c --> 2(a,b),1(a),1(c)

有很多关于压缩算法的文献和网络资源，您应该使用它们来获得更深入的了解。

Answer 3

RLE

Answer 4

是的，压缩。一个简单的算法是游程编码。还有信息论，它是压缩算法的基础。

信息论：更常见的输入应该更短，从而使句子长度更短。

因此，如果您要编码二进制，其中序列 0101 非常常见（大约占输入的 25%），那么简单的压缩将是：

0101 = 0
anything else = 1[original 4 bits]

因此输入：0101 1100 0101 0101 1010 0101 1111 0101
将被压缩为： 0 11100 0 0 11010 0 11111 0

这是 32 位的压缩 -> 20 位。

一个重要的教训：压缩算法的选择完全取决于输入。错误的算法可能会使数据变得更长。

Answer 5

除非您必须自己编写一些解决方案，否则您可以使用一些适合您正在使用的编程语言的 ZIP 压缩库。

是的，这就是数据压缩。

Answer 6

我们可以利用哈希表，使用LZW压缩算法来高效、快速地压缩文本文件。

Answer 7

单个序列的压缩限制

序列的压缩限制是多少？

这个问题可以给出两个答案：

1. 序列的压缩极限是一个未解决的问题。此外，已经表明这个极限无法计算。

2. 香农定义了一个具有很大实际意义的子问题，其中可以定义理论极限（源编码定理）。这个子问题是纯粹的概率问题，称为源编码。

最一般形式的信息传输问题的定义

为了理解这两个答案，有必要介绍最一般形式的信息传输问题。为了在两点之间进行信息传输，两个主体必须​​共享一种交流语言。这个要求是必要的，没有通信语言，传输的消息无法被理解，因此不携带任何信息。 因此，信息传输问题以其最一般的形式，研究共享通信语言的两点之间任何形式的信息传输。

这个定义的问题在于“信息”的概念以任何形式”很难用数学形式化。 因此，有必要对问题进行第一次简化，其中信息被定义为一个数值序列。这样就得到了一个子问题，其中信息的概念是定义明确并且可以从数学角度形式化。

因此，信息传输所需的两个元素是：携带信息的压缩序列以及编码器和解码器都已知的通信语言。

压缩序列：表示从要传输的序列导出的任何信息。从实际的角度来看，从序列中获得的任何对解码器返回原始消息有用的信息都必须被视为压缩消息的一部分。

通信语言：代表一组允许通信并因此在两个主体之间传输信息的规则。从实践的角度来看，在消息生成之前存在的任何信息都可以被视为通信语言的一部分。

源编码

香农在他的著名文章《通信的数学理论》中引入了对信息传输问题的进一步修改，这使他能够获得一个可以定义理论压缩极限的子问题。为此，香农介绍了生成消息的源。此外，将符号转换为码字的编码方案是根据源的信息生成的，而不是根据从消息获得的信息生成的。 因此，在消息生成之前定义的编码方案可以被视为通信语言的组成部分。然后，香农形式化了信息的概念，为此他开发了一个唯一的变量定义在存在编码方案的情况下传输的消息。香农提出的解决方案是将信息视为变异的度量。执行此测量所生成的函数称为熵 H。以下句子取自文章“通信的数学理论”，使我们了解香农的熵概念。

“在一个概率为 1 的极限情况下（确定性）而其他所有为零（不可能），则 H 为零（完全没有不确定性 - 没有选择自由 - 没有信息）。”

关于他定义的子问题，香农设法定义了通过开发源编码定理，得出理论压缩极限。该定理证明，熵定义了替换压缩消息中符号的码字的最小平均长度。因此，给定随机变量 iid 的源 X，它生成长度为 N 的消息 压缩消息不能长于 NH(X) 消息生成之前定义的编码方案不是压缩消息的一部分，

当源未知时应用香农开发的理论。
当源未知时，可以计算零阶经验熵H0(m)，其中频率是从要传输的消息m获得的。在这种情况下，使用序列中符号的频率，在生成消息之后开发编码方案，因此它必须是压缩消息的一部分。因此，压缩消息由NH0(M)+编码方案定义。当H0(m)的值非常接近H(X)的值时，编码方案表示冗余，这也称为熵编码的低效率。 实际上，对生成消息的源的不了解决定了压缩消息中是否存在冗余。
此外，编码方案的长度取决于所使用的语言，因此不可能精确地定义它。因此，无法定义压缩消息的长度限制。 因此，利用香农引入的形式主义，我们证明了源未知序列的压缩极限是不可计算的。

源熵 H(X) 与零阶经验熵 H0 之间的差异(m)

NH(X)的值代表压缩消息。 因此，在这种情况下，熵定义了更一般意义上的消息信息，而不仅仅是香农信息。不幸的是，这种方法并不代表信息传输的一般情况，而是代表一个子问题，其中编码器和解码器知道生成消息的源。

NH0(m)的值并不代表压缩消息。 因此，零阶经验熵仅代表单个符号的香农信息的平均值。因此，零阶经验熵的一般意义不如源熵。然而，在这种情况下，信息传输的问题正在以比源编码的情况更一般的方式得到解决。

为了证明刚才所说的内容，给出下面的例子：让我们采用随机变量iid的统一源X，它生成长度为N的消息。当然，这个序列不能被压缩。因此，平均而言，压缩消息的长度必须大于或等于 N。在第一种情况下，编码器和解码器知道源，因此我们可以应用源编码。获得的结果是所有消息的长度为 NH(X)，并且由于 H(X)=1（我们使用字母表的维度作为熵的基础），压缩消息的长度为 N。因此，在这种情况下，我们达到了理论压缩极限。在第二种情况下，编码器和解码器都不知道源。因此，编码器必须使用消息中符号的频率值来计算熵。这样就得到了零阶经验熵H0(m)。来源是统一的，但只有少量生成的消息具有统一的符号分布。因此，消息的零阶经验熵H0(m)的平均值将小于H(X)。因此，如果我们不将编码方案视为压缩消息的一部分，我们会得到不合逻辑的结果，事实上，我们有NH0(m)＜N。在实践中，我们设法压缩随机序列。 错误取决于这样一个事实：在第二种情况下，我们在生成消息后获得了编码方案，因此它必须是压缩消息的一部分。总之，要获得正确的结果，压缩字符串必须由长度大于N的NH0(m)+编码方案定义。因此，由于不知道源，我们有冗余。

信息论的现代方法

所涵盖的最重要的方面之一是理解源编码是最一般形式的信息传输问题的子问题。 因此，当源未知时，只能计算零阶经验熵，该参数的值比源的熵要有限得多。事实上，将消息长度NH0(m)的零阶经验熵并不代表压缩消息。在这种情况下，编码方案也必须是压缩消息的一部分，在消息生成之后定义，因此不能包含在通信语言中。这种方法代表了观点的重要转变。事实上，即使源未知，也可以将压缩消息仅视为 NH0(m)，而不像源编码那样考虑编码方案，这是绝对正常的。

随着新理论的出现，这种观点的改变是必要的，新理论可以减少在来源未知时产生的冗余。该理论仅适用于字母表大于等于3的情况。 该理论的目的是让编码序列NH0(m)和编码方案更有效地交互。

现在，我将解释这个理论的基础。如果我们必须对长度为 N 且字母为 A 的序列执行熵编码，而我们不知道其来源，则我们拥有的唯一信息是该序列将是 |A|^N 可能序列之一的一部分。因此，使用熵编码来平均提高压缩序列（编码序列+编码方案）长度的变换的唯一可能方法是将所有可能序列的集合变换为一组新的序列相同大小的序列组成，平均可以在更小的空间中压缩。这样，即使我们不知道生成序列的源，我们也知道如果应用此变换，我们可以，平均而言，获得比未变换序列的压缩消息长度更小的压缩消息。

具有这些特征的集合是由长度为N+K的序列组成的维度|A|^N的集合。增加序列的长度也会增加包含所有可能序列的集合的大小，该集合变为|A|^N+K。因此，从该集合中可以选择由具有最小零阶经验熵值的序列组成的大小|A|^N的子集。

这样，我们得到以下结果：给定由随机变量 iid 的源 X（未知）生成的长度为 N 的消息 m，应用所描述的变换 f(m)，我们平均得到：

NH(X )< Avg(NtH0(f(m)+编码方案)

其中Nt>N

Avg(NH0(m)+编码方案)=编码序列m的平均值+编码方案

Avg(NtH0(f(m)+编码方案)=编码变换序列f(m)的均值+编码方案

NH(X)是未知的压缩极限，实际上，我们设定了源未知的条件。正如一开始提到的，当源未知时，在目前的知识水平下，不可能定义压缩极限。

现在，我们证明实验得出的结果是，我们取一个长度为 3、字母为 3 的序列，则可能的序列为 27 个。如果我们将长度增加到 4 并保持字母为 3，则可能的序列将变为 81 个。在这 81 个中，我们选择了 27 个H0(m) 的最小值。这样，两个集合的元素数量相同，因此，我们可以定义两个集合的序列之间的一一对应关系。两组中的。在第一列中，我们有消息 m，在第二列中，我们有 NH0(m)，在第三列中，我们有转换后的消息 f(m)，在第四列中，我们有 NtH0(f(m) ) 变换后的消息 f(m)。

在此处输入图像描述

零阶经验熵平均值乘以字符串长度 N=3消息 m 为：
平均值(NH0(m))=2.893
其中N=3。
零阶经验熵的平均值乘以变换后的消息f(m)的字符串长度Nt=4为：
平均值(NtH0(f(m))=2.884
常数Nt=4
因此，您可以看到，虽然变换后的消息较长，但应用变换时，零阶经验熵乘以消息长度的平均值平均较小。 因此，即使我们不知道来源，我们也知道通过应用变换，我们平均会得到零阶经验熵乘以消息长度的值的减少。 因此，编码消息的长度（由码字替换的符号）减少。

现在，让我们看看编码方案，在这种情况下进行评估会更加困难，因为编码方案的长度取决于所使用的压缩方法。但是，我们知道，从理论角度来看，对编码方案长度影响最大的参数是字母表的大小。因此，我们计算两组字母A的平均大小。
对于表第一列中的消息，字母大小 |A| 的平均值为：
平均值(|A|)=2.1
在表的第三列中转换消息 f(m) 的情况下，字母大小的平均值 |A| 为：
平均值(|A|)=1.89
获得的结果不仅仅对报告的病例有效。 事实上，无论字母表的大小如何，由较长序列组成的转换集总是具有更多数量的类型类，其符号数量小于|A|。对于类型类，我们指的是具有相同符号频率的字符串集合，例如字符串 113 和字符串 131 实际上属于同一类型类，两者的符号频率分别为 1=2/3 和 3=1/ 4。

因此，平均为 NH0 (f(m))＜NH0(m)并且编码方案f(m)＜NH0(m)编码方案 m 中，我们通过实验证明了以下不等式：

NH(X)< Avg(NH0(f(m)+编码方案)< Avg(NtH0(m)+编码方案)

这样，变换后的消息集合具有平均压缩消息长度，使用熵编码，小于因此，当源未知时，如果应用所描述的变换，则平均会获得压缩消息的减少，因此，我们能够减少由于不知道源而导致的低效率

。结论是，我们在开始时提出的关于序列的最小压缩长度是否存在的问题代表了一个尚未解决的问题，但是，信息理论的新发展设法减少了所产生的低效率。当我们不知道来源时，就可以在这个主题上迈出重要的一步。