序列压缩？

Question

最近我遇到这让我很困惑的一个问题， 问题是： 我要压缩一个序列，以便不丢失任何信息，例如：

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

有没有任何算法来做这样的事情？这个问题的名称是什么？它是压缩吗？还是其他什么？ 我真的很感激任何帮助 在此先感谢

Answer 1

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

是的，这是数据压缩。

Answer 2

RLE

Answer 3

是的，压缩。一个简单的算法就是runlength编码。还有信息论，这是压缩算法的基础。

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

所以，如果你是二进制编码，其中顺序0101是非常commmon（输入的约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 4

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

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

以下是IMHO的simples形式，称为游程长度编码，短RLE：

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

正如你可以看到所有后续字符，而它们相同的被压缩成一个。

您也可以搜索为后续的图案是困难得多：

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

有许多关于压缩算法文献和网络资源，你应该使用它们来获得更深的看法。

Answer 5

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

我发现奇妙的这个简单的Javascript LZW功能，从魔术师在140 bytes of 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 6

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