C＃壓縮字節數組

Question

我對壓縮算法瞭解不多。我正在尋找一種簡單的壓縮算法（或代碼片段），它可以減小字節[,,]或字節[]的大小。我無法使用System.IO.Compression。此外，數據有很多重複。

我試着實現RLE算法（下面貼出來供您檢查）。但是，它會產生1.2到1.8倍的數組。

public static class RLE 
{ 
    public static byte[] Encode(byte[] source) 
    { 
     List<byte> dest = new List<byte>(); 
     byte runLength; 

     for (int i = 0; i < source.Length; i++) 
     { 
      runLength = 1; 
      while (runLength < byte.MaxValue 
       && i + 1 < source.Length 
       && source[i] == source[i + 1]) 
      { 
       runLength++; 
       i++; 
      } 
      dest.Add(runLength); 
      dest.Add(source[i]); 
     } 

     return dest.ToArray(); 
    } 

    public static byte[] Decode(byte[] source) 
    { 
     List<byte> dest = new List<byte>(); 
     byte runLength; 

     for (int i = 1; i < source.Length; i+=2) 
     { 
      runLength = source[i - 1]; 

      while (runLength > 0) 
      { 
       dest.Add(source[i]); 
       runLength--; 
      } 
     } 
     return dest.ToArray(); 
    } 

} 

我還發現了一個基於java，string和integer的LZW實現。我已將其轉換爲C＃，結果看起來不錯（代碼如下）。但是，我不確定它是如何工作的，也不知道如何使它與字節而不是字符串和整數一起工作。

public class LZW 
{ 
    /* Compress a string to a list of output symbols. */ 
    public static int[] compress(string uncompressed) 
    { 
     // Build the dictionary. 
     int dictSize = 256; 
     Dictionary<string, int> dictionary = new Dictionary<string, int>(); 
     for (int i = 0; i < dictSize; i++) 
      dictionary.Add("" + (char)i, i); 

     string w = ""; 
     List<int> result = new List<int>(); 

     for (int i = 0; i < uncompressed.Length; i++) 
     { 
      char c = uncompressed[i]; 
      string wc = w + c; 
      if (dictionary.ContainsKey(wc)) 
       w = wc; 
      else 
      { 
       result.Add(dictionary[w]); 
       // Add wc to the dictionary. 
       dictionary.Add(wc, dictSize++); 
       w = "" + c; 
      } 
     } 

     // Output the code for w. 
     if (w != "") 
      result.Add(dictionary[w]); 
     return result.ToArray(); 
    } 

    /* Decompress a list of output ks to a string. */ 
    public static string decompress(int[] compressed) 
    { 
     int dictSize = 256; 
     Dictionary<int, string> dictionary = new Dictionary<int, string>(); 
     for (int i = 0; i < dictSize; i++) 
      dictionary.Add(i, "" + (char)i); 

     string w = "" + (char)compressed[0]; 
     string result = w; 
     for (int i = 1; i < compressed.Length; i++) 
     { 
      int k = compressed[i]; 
      string entry = ""; 
      if (dictionary.ContainsKey(k)) 
       entry = dictionary[k]; 
      else if (k == dictSize) 
       entry = w + w[0]; 

      result += entry; 

      // Add w+entry[0] to the dictionary. 
      dictionary.Add(dictSize++, w + entry[0]); 

      w = entry; 
     } 

     return result; 
    } 
} 

Answer 1

調查霍夫曼代碼，這是一個非常簡單的算法。基本上，對於更頻繁出現的模式，使用更少的位，並且保留一個表格來表示它的編碼方式。而且您必須在您的代碼字中註明沒有分隔符來幫助您解碼。

Answer 2

看一看here。我使用此代碼作爲壓縮我的一個工作項目的基礎。不確定在Xbox 360 SDK中有多少.NET Framework是可訪問的，因此不確定這對您有多好。

Answer 3

RLE算法的問題在於它太簡單了。它在每個字節前加以及重複多少次，但這確實意味着在非重複字節的長範圍內，每個單字節前綴爲「1」。關於數據沒有任何重複，這將雙的文件大小。

這可以通過使用Code-type RLE來避免; 'Code'（也稱爲'Token'）將是一個可以有兩個含義的字節;要麼表示單個後面的字節重複了多少次，要麼表示有多少非重複字節應該按原樣複製。這兩個代碼之間的區別是通過啓用最高位來實現的，這意味着該值仍然有7位可用，這意味着每個這樣的代碼的複製或重複的數量可以高達127.

這意味着即使在在最壞的情況下，最終尺寸只能比原始文件尺寸大1/127。

整個概念的一個很好的解釋，再加上完整的工作（而且，事實上，大量優化）C＃代碼，可以在這裏找到：

http://www.shikadi.net/moddingwiki/RLE_Compression

注意，有時，這些數據將結束原因是大大小於，只是因爲沒有足夠的重複字節讓RLE工作。處理這種壓縮失敗的一個好方法是在最終數據中添加一個頭部。如果您只是在開始處添加一個額外的字節，其值爲0表示未壓縮的數據，而另一個表示RLE壓縮數據的值，則當RLE未能提供較小的結果時，您只需將其保存爲未壓縮的數據，並將0放在前面，並將最終數據將比原來的大一個字節。然後在另一側的系統可以讀取該起始字節，並使用它來確定下列數據是否應該解壓縮或者只是複製。