a,a,a,b --> a,b
a,b,a,a,c --> a,b,a,a,c(不能压缩成a,b,a,c,因为这样会丢失a,a)
有没有算法可以完成这样的事情?这个问题叫什么名字?是压缩吗?还是其他什么? 我真的很感激任何帮助 提前致谢
任何能够将数据压缩以占用更少内存的算法都被称为压缩算法,无论是有损还是无损。
例如(“举个例子”的压缩形式 :-))
以下是我认为最简单的形式,称为运行长度编码,简称RLE:
a,a,a,b,c -> 3a,1b,1c
正如您所看到的,所有后续相同的字符都被压缩成一个。
您还可以搜索后续的模式,这要困难得多:
a,b,a,b,a,c --> 2(a,b),1(a),1(c)
关于压缩算法有很多文献和网络资源,你应该使用它们来获得更深入的了解。
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.
}
是的,压缩。一个简单的算法可以是游程编码。还有信息论,它是压缩算法的基础。
信息理论:常见的输入应该更短,从而使句子长度更短。
所以,如果您正在编码二进制数字,其中序列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位。
一个重要的教训:压缩算法的选择完全取决于输入。选择错误的算法可能会使数据变得更长。
我们可以利用哈希表使用LZW压缩算法高效快速地压缩文本文件。
除非你必须亲自编写某些解决方案,否则你可以使用一些适用于你所使用的编程语言的ZIP压缩库。
是的,这是数据压缩。
一个序列的压缩极限是什么意思?
对于这个问题可以给出两个答案:
一个序列的压缩极限是一个未解决的问题。此外,已经证明这个极限是无法计算的。
香农定义了一个与实际相关性很大的子问题,在这个子问题中可以定义一个理论上的极限(源编码定理)。这个子问题是纯粹概率性的,被称为源编码。
要理解这两个答案,必须介绍信息传输问题在其最一般形式下的问题。为了在两个点之间进行信息传输,两个主体必须共享一种通信语言。这个要求是必要的,没有通信语言,传输的消息就无法理解,因此也不携带任何信息。因此,信息传输问题在其最一般形式下研究的是在共享通信语言的两个点之间以任何形式传输信息。
这个定义的问题在于“以任何形式的信息”这个概念在数学上很难形式化。因此,有必要首先简化问题,将信息定义为一个数字序列。通过这种方式,得到了一个子问题,其中信息的概念是明确定义的,并且可以从数学角度进行形式化。其中最重要的方面之一是了解源编码是最一般形式下的信息传输问题的子问题。因此,当源未知时,只能计算零阶经验熵,这个参数的价值比源熵受到更多限制。实际上,将零阶经验熵乘以消息长度NH0(m)得到的值并不代表压缩后的消息。在这种情况下,编码方案也必须包含在压缩的消息中,在生成消息后定义,因此不能包含在通信语言中。这种方法代表了一个重要的视角变化。事实上,即使源未知,仅将压缩的消息NH0(m)视为与源编码一样,在过去也是绝对正常的。
随着一种新理论的出现,改变视角变得必要,这种理论可以在字母表大于或等于3时应用,以减少源未知时产生的冗余。这个理论的目的是使编码序列NH0(m)和编码方案更有效地相互作用。
现在,我将解释这个理论的基础。如果我们需要对一个长度为N且字母表为A的序列进行熵编码,而我们并不知道其源头,我们唯一拥有的信息是该序列将是可能序列中的一部分,可能序列的数量为|A|^N。零阶经验熵的平均值乘以消息m的字符串长度N=3为: Avg(NH0(m))=2.893 其中N=3。 零阶经验熵乘以转换后的消息f(m)的字符串长度Nt=4的平均值为: Avg(NtH0(f(m))=2.884 其中Nt=4。 因此,尽管转换后的消息更长,但平均而言,应用转换后零阶经验熵乘以消息长度的值较小。因此,即使我们不知道源数据,通过应用转换,我们平均而言可以获得零阶经验熵乘以消息长度值的减少。因此,编码消息的长度(符号被码字替代)减小。
现在,让我们来看一下编码方案,在这种情况下,进行评估更加困难,因为编码方案的长度取决于所使用的压缩方法。但是,从理论上讲,最影响编码方案长度的参数是字母表的大小。因此,我们计算两个集合中字母表A的平均大小。 在表格的第一列中,字母表大小|A|的平均值为: Avg(|A|) = 2.1 在表格的第三列中,转换后的消息f(m)的字母表大小|A|的平均值为: Avg(|A|) = 1.89 所得结果仅对报告的情况有效。实际上,无论字母表的大小如何,由较长序列组成的转换集始终具有比|A|少的符号数的类型类别更多。通过类型类别,我们指的是具有相同符号频率的字符串集合,例如,字符串113和字符串131实际上属于同一个类型类别,因为它们都具有符号频率1=2/3和3=1/4。
因此,平均而言,NH0(f(m)) < NH0(m)且编码方案f(m) < 编码方案m,我们通过实验证明了以下不等式: