在C中压缩ASCII字符串
我有一些C代码在内存中存储ASCII字符串作为四字节长度后跟字符串。 字符串长度在10-250字节范围内。
为了减少占用，我想在运行中单独压缩每个字符串，仍然存储（压缩字符串的）长度，然后是压缩字符串。
我不想在比单个字符串更大的范围内进行压缩，因为任何字符串都可以随时读/写。
有哪些库/算法可用于此操作？
谢谢你的帮助。 NickB
ZLib始终在为您服务 – 当字符串包含不可压缩的数据时，它的开销非常小，它相对快速，免费且可以轻松集成到C和C ++程序中。
对于短字符串，大多数压缩算法都不能很好地工作。 以下是一些压缩算法，旨在压缩简短的英文文本字符串。 虽然它们可以处理明文字符串中的任意字节，但这些字节通常会使“压缩”数据长于明文。 所以压缩器存储“不可压缩”数据是一个好主意，并在这些数据上设置“文字”标志（正如Steve Jessop建议的那样）。
- “base 40 encoding”：最大压缩3：2
- “Zork标准信息交换规范”（ZSCII）：最大压缩比为3：2
- 字节对压缩 ：最大压缩2：1
- 所有字符串共享的静态霍夫曼表（由cygil建议）。
- 理想情况下，由您所有实际数据的确切字符频率组成。
- Varicode：最大压缩比为2：1
- PalmDoc压缩 （字节对压缩+ LZ77的简单变体）。
我不确定zlib或LZW压缩方法在单独压缩小于250字节的短字符串的情况下是否能正常工作。 两者通常都需要在看到显着的压缩增益之前创建一个相当大的字典。
也许简单的霍夫曼编码使用固定的编码树，或者在所有字符串实例之间共享？ 另外，你有没有看过用于在80年代压缩内存受限的微型计算机上的短字符串的ZSCII编码？
链接文字
Zlib绝对是你的朋友，但是一定要执行一些测试来检测压缩开始有利的平均字符串长度，因为压缩头的开销很小。
例如，您可能会发现在20个字符以下，压缩字符串实际上更大，因此只压缩更长的字符串。
当字符串长度为10-250字节时，为什么使用4字节长度，使用1字节长度，每个字符串只能节省3个字节。
数据是否只是文本，即0-9 Az或某些子集？ 如果是这样重新编码它以使用该子集并为每个字符保存几位。
现在看看Huffman编码部分和lempel-zev部分中的http://gnosis.cx/publish/programming/compression_primer.html 。
这应该让你开始。
当使用这样的多个字符串时，可以通过将它们与\0 s（1个字节）连接在一起并使用查找函数来避免每个字符串的指针开销（每个字符串4或8个字节）。
#include 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个额外的数据字节，但可以节省大量的条件跳转和增量。查找function。
#include /* 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 return 0; }
对于这两种变体，最好先保留最常用的字符串; 但是，第二种方法将允许您使用压缩数据（选择最适合您数据的数据–David Cary的答案有一个可行解决方案列表），只要您将长度分隔符调整为压缩长度即可。
注意：要从标准压缩器中获得最大压缩，您可能希望将其标头的长度字段修改为unsigned char （如果字符串长度超过256但不是65536字节，则为unsigned short ），因为它们中的大多数将尝试支持压缩大文件（这可以为每个字符串节省3-7个字节）