序列壓縮？

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壓縮算法來壓縮文本通過高效，快速文件利用哈希表。