C中的ASCII字符串的壓縮

Question

我有一些C代碼將ASCII字符串存儲在內存中，其長度爲4個字節，後面跟着字符串。字符串長度在10-250字節範圍內。

爲了減少佔用率，我希望逐個壓縮每個字符串，仍然存儲壓縮字符串的長度（壓縮字符串的長度）。

我不想在比單個字符串更大的範圍壓縮，因爲任何字符串都可以隨時讀取/寫入。

什麼庫/算法可用於做到這一點？

感謝您的幫助。 NickB

Answer 1

ZLib始終爲您服務 - 當字符串包含不可壓縮的數據時，它的開銷很小，它相對快速，免費且可以輕鬆集成到C和C++程序中。

Answer 2

Zlib絕對是您的朋友，但請務必執行一些測試來檢測壓縮開始有益的平均字符串長度，因爲壓縮標題的開銷很小。

例如，您可能會發現，在20個字符以下，壓縮字符串實際上更大，因此只能壓縮更長的字符串。

Answer 3

爲什麼在字符串長度爲10-250字節時使用4字節長度，使用1字節長度可以爲每個字符串單獨保存3個字節。

只是數據文本，即0-9 A-Z或某些子集？如果是這樣的話，重新編碼它以使用該子集並保存每個字符幾位。

現在看看霍夫曼編碼部分和lempel-zev部分中的http://gnosis.cx/publish/programming/compression_primer.html。

這應該讓你開始。

Answer 4

我不確定zlib或LZW壓縮方法在個別壓縮小於250字節的短字符串的情況下可以正常工作。兩者通常都需要創建一個相當大的字典，才能看到顯着的壓縮增益。

也許簡單的霍夫曼編碼與一個固定的編碼樹，或一個字符串的所有實例之間共享？另外，你是否看到過80年代用於在內存受限的微型計算機上壓縮短串的ZSCII編碼？

link text

Answer 5

大多數壓縮算法不短字符串工作得很好。 下面是一些壓縮算法，旨在壓縮短英文文本字符串。 雖然它們可以處理任何明文字符串中的任意字節，但這些字節通常使「壓縮」數據比明文長。 因此，壓縮機不改變地存儲「不可壓縮」數據，並在這些數據上設置一個「文字」標誌（如Steve Jessop建議的）。

• 「基座40編碼」：最大壓縮3:2
• 「的Zork標準信息交換碼」（ZSCII）：最大壓縮3:2
• byte pair compression：最大壓縮2:1
• 所有字符串之間共享的靜態霍夫曼表（如cygil所建議的）。
  • 理想情況下，從您的所有實際數據的確切字符頻率形成。
  • Varicode：最大壓縮2:1
• PalmDoc compression（字節對壓縮+ LZ77的簡單變體）。

Answer 6

當使用多個字符串這樣有可能通過與\0 S（1個字節）一起串接它們並使用查找功能，以避免爲每個串（每個4或8個字節）的指針開銷。

#include <stdio.h> 

static const char strings[]="hello\0world\0test"; 

char * nthstring(const char *s, unsigned n){ 
    while(n--) 
     while(*s++) 
     ; 
    return s; 
} 
int main(void) { 
    printf("%s\n",nthstring(strings,1)); 
    return 0; 
} 

但是如果字符串長度小於UCHAR_MAX您可以用零字節佔位存儲長度（加上開頭加1），這將花費只有1個額外的數據字節優化查找，但節省了大量條件跳轉和增量查找功能。

#include <stdio.h> 
/* each "string" is prefixed with its octal length */ 
static const char lenstrings[]="\05hello\05world\04test"; 

char * ithstring(const char *s, unsigned n){ 
    while(n--){ 
     s+=*s+1; 
    } 
    return s; 
} 
int main(void) { 
    char *s=ithstring(lenstrings,1); 
    /* use the length because we don't have terminating \0 */ 
    printf ("%.*s",(unsigned char)*s,s+1); 
    //write(1,s+1,(unsigned char)*s); //POSIX variation via <unistd.h> 
    return 0; 
} 

對於這兩種變化，最好先保留最常用的字符串;但是，只要將長度分隔符調整爲壓縮長度，第二種方法將允許您使用壓縮數據（挑選最適合您數據的數據 - David Cary's answer包含可行解決方案列表）。

注：爲了獲得最大的壓縮超出標準的壓縮機，你可能會需要修改他們的頭的長度字段是unsigned char（或unsigned short如果字符串長度超過256個，但不是65536字節），因爲大多數人都會嘗試以支持大文件的壓縮（這可以節省每個字符串3-7個字節）